Javascript create an array with unique combination of values

Question

Despite reading a lot of Q/A about permutation/combination: Finding All Combinations of JavaScript array values + JavaScript - Generating combinations from n arrays with m elements I have not found the right way to get the kind of result I'm looking for. I got a 10 values array:

var arr = [0,1,2,3,4,5,6,7,8,9];

If I'm right, the number of all possible permuted arrays of unique values (no duplicates):

[5,9,1,8,2,6,7,0,4,3] [4,8,0,2,1,9,7,3,6,5] ...

is 2x3x4x5x6x7x8x9x10 = 3628800

I'm trying to produce a function to dynamically create the 'n' array. For example:

function createArray(0) -> [0,1,2,3,4,5,6,7,8,9]
function createArray(45648) -> [0,1,5,3,2,8,7,9,6] (something like...)
function createArray(3628800) -> [9,8,7,6,5,4,3,2,1,0]

The way I'm figuring to achieve it is:

createArray(1) permutes the 2 last signs (8,9 -> 9,8)
createArray(2->6) permutes the 3 last signs (8,7,9 -> 9,8,7)
createArray(3628800) : all values are permuted (9->0)

Do you think it's possible/easy to do, and if yes how to proceed ?

[EDIT]

Thanks for helpfull answers

function permute(permutation, val) {

  var length = permutation.length,
  result = [permutation.slice()],
  c = new Array(length).fill(0),
  i = 1, k, p,
  n = 0;
  while (i < length) {
  if (c[i] < i) {
  if (n <= val) {   
      k = i % 2 && c[i];
      p = permutation[i];
      permutation[i] = permutation[k];
      permutation[k] = p;
      ++c[i];
      i = 1;
      if (n == val) {   
          arr = permutation.slice();
          console.log("n="+n+"\n"+arr);
          console.log( 'Duration: '+((new Date() - t1)/1000)+'s' );
          break;
      }
      else {  n+=1; }  
     }
   } else {
     c[i] = 0;
     ++i;
   }
  }
}

let t1 = new Date();
permute([0, 1, 2, 3, 4, 5, 6, 7, 8, 9], 100000); // <- array requested

console : n=100000 + 0,5,8,1,7,2,3,6,4,9 + Duration: 0.004s

Do you really need to number the various permutations? Would it suffice to just have a randomly shuffled array? — Tim Biegeleisen, Oct 19 '18 at 06:03
Would you consider to use Node modules like [generatorics](https://www.npmjs.com/package/generatorics) ? — Wong Jia Hau, Oct 19 '18 at 06:16
Hmm, Sounds like CS exercise, perhaps you can show your code so far. — vdj4y, Oct 19 '18 at 06:17
@CertainPerformance Not yet, just starting the job by exploring existing functions on stackoverflow — Wolden, Oct 19 '18 at 06:23
@TimBiegeleisen no random, the use is to define the position of an virtual object in a 3D cube and call the array corresponding to this position x,y,z. — Wolden, Oct 19 '18 at 06:26
@WongJiaHau thanks for link. Pure JS Vanilla will be preferable if possible — Wolden, Oct 19 '18 at 06:28
take a look at https://stackoverflow.com/a/37580979/3090583.. you can break the array to different sizes [1],[2],[3],[..] / [1,2], [2,3], [3,4] .... and then process each with that functions — Raj Nandan Sharma, Oct 19 '18 at 06:29
@CertainPerformance I've try to experiment different functions from linked pages above but some create duplicates values in same array, some other (multi-arrays) dont loop all values, some other create correct arrays but I cant' find the way to programmatically produce the only one I need... — Wolden, Oct 19 '18 at 06:35
btw, the last with `3628800` does not work, because it is one over. — Nina Scholz, Oct 19 '18 at 07:14
@Nina No prob for the last arrays I only need to work in a 100x100x100 (one million) points 3D cube :) — Wolden, Oct 19 '18 at 08:06
what is actually the question about? performance? code? errors? — Nina Scholz, Oct 19 '18 at 08:08
my EDIT is the answer to my question. It seems to work perfectly except for the last (3628800) request as you've notice it. As new user I don't know what I am supposed to do now: close the question? write 'solved' somewhere ? — Wolden, Oct 19 '18 at 08:43

score 0 · Answer 1 · answered Oct 19 '18 at 06:34

As this question doesn't decribe a specific programming problem but rather a task, and at that a rather complex one, you shoulnd't expect a full solution as an answer, but i'll try describing a possible method of doing this:

As you said, the number of permutations is 2x3x4x...

You could check if n > 2, if true, then check if n > 2x3, if true check if n > 2x3x4. That way you would know how many of the tailing array indexes you want to permutate. Then you would have to make sure to calculate the permutations in a sorted linear way that doesn't generate the same permutation twice. Thats a math problem, the coding itself should be rather easy (something along the lines of switch the position n times at changing indexes).

Not sure if this is the answer you're looking for, but making a unique permutation algorithm sounds rather complex (see for example this answer to another question https://stackoverflow.com/a/11425168/9521900) which links to this wikipedia article https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order on generating in lexicographic order.

EDIT: From Raj Sharmas comment on your question, this answer on generating permutations seems valuable too: https://stackoverflow.com/a/37580979/3090583

Javascript create an array with unique combination of values

1 Answers1