2

I am looking for a way to get all possible combination with an array intake so if we had [1,2,3] it would return 

[1,1,1],[1,1,2],[1,1,3],[1,2,2],[1,2,3],[1,3,3],[2,2,2],[2,2,3],[2,3,3],[3,3,3].

I have looked at several other posts such as this one here: https://stackoverflow.com/a/9960925/1328107 but they all seem to stop short of all combinations, ie 

[ 1, 2, 3 ], [ 1, 3, 2 ],[ 2, 1, 3 ], [ 2, 3, 1 ], [ 3, 1, 2 ], [ 3, 2, 1 ].

Any help would be greatly appreciated.

Community
  • 1
  • 1
Jarritos
  • 55
  • 6

1 Answers1

10

A backtracking will do the trick:

function combRep(arr, l) {
  if(l === void 0) l = arr.length; // Length of the combinations
  var data = Array(l),             // Used to store state
      results = [];                // Array of results
  (function f(pos, start) {        // Recursive function
    if(pos === l) {                // End reached
      results.push(data.slice());  // Add a copy of data to results
      return;
    }
    for(var i=start; i<arr.length; ++i) {
      data[pos] = arr[i];          // Update data
      f(pos+1, i);                 // Call f recursively
    }
  })(0, 0);                        // Start at index 0
  return results;                  // Return results
}

Some examples:

combRep([1,2,3], 1); /* [
  [1], [2], [3]
] */
combRep([1,2,3], 2); /* [
  [1,1], [1,2], [1,3],
         [2,2], [2,3],
                [3,3]
] */
combRep([1,2,3], 3); /* [
  [1,1,1], [1,1,2], [1,1,3],
           [1,2,2], [1,2,3],
                    [1,3,3],

           [2,2,2], [2,2,3],
                    [2,3,3],

                    [3,3,3],
] */
combRep([1,2,3]); /* Same as above */
Oriol
  • 274,082
  • 63
  • 437
  • 513
  • 1
    @Jarritos Initially this produced variations instead of combinations with repetition, see the fixed version. – Oriol Sep 12 '15 at 22:05
  • Great answer, I upvoted. See the previous edit of this answer if you are looking for variations (where order does matter), vs combinations (where order does *not* matter). Apparently I was looking for "variations", but OP was asking about , and looking for, "combinations". [Here's the difference](https://www.quora.com/What-is-the-difference-between-variation-combination-and-permutations) and [here](https://webpages.charlotte.edu/ghetyei/courses/old/S19.3166/pcv.pdf) – Nate Anderson Jul 11 '23 at 00:09