0

Without using any fancy library function (so let's use JavaScript), what is a way to get all combinations of picking k items from an n-item array of distinct values? (0 <= k <= n)

That is, if the array is [1,2,3], then the result should be:

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

Note the size of the given array is not fixed. So it can be [1,2,3,4] or [1,"a","b","c",5,100]

I could think of a way which is to use a binary number with n digits, for example, with n = 3, starting with 

000

and adding 1 to it, and repeat until 111, and 000 means no element get in, and 001 means the last element gets in, and 011 means the last 2 elements get in, and we would get all the possibilities, but it is a pretty strange way to solve it and it seems there should be a more elegant solution.

nonopolarity
  • 146,324
  • 131
  • 460
  • 740
  • "*but it is a pretty strange way to solve it*" - no, the binary number solution would be totally fine. See [here](https://stackoverflow.com/a/15649645/1048572) for an example – Bergi Jul 27 '19 at 13:00
  • now I remember why it seems strange: I noticed the similar patterns in binary numbers, but it actually is whether a number participates or not, so it is either a true or false, and we really can form an array:[false, false, false] and "loop" through the last false to true, and then the middle false to true, and loop through the last entry from false to true again. It is like 2 x 2 x 2 possibilities. And this is exactly how a binary number increases (1 as true and 0 as false). But in a language that doesn't have infinite precision integer numbers, then we need to use something like that array – nonopolarity Jul 27 '19 at 23:24
  • You will run out of memory long before creating an array of all combinations that a JS number can represent, so I wouldn't worry about that. Sure, it's a limitation that you should check against in the code for due diligence, but you'll never hit it. – Bergi Jul 28 '19 at 09:53
  • good point. By the way it seems once in a while I run into the requirements of given n, k, loop through all possibilities of n entries and k items. For example, 20 dice, n = 20, k = 6: `[[0,0,...,0], ... to [5,5, ..., 5]]` Or n = 3, k = 32... I never learned that pattern before and it seems I can just create an array of initial values and increment each time and if overflow, carry to the next entry, etc. But now that I think about it, it seems like it is "permutations with repetitions" and I probably can look for an iterator for it and it'd work such as in Rosetta code – nonopolarity Jul 29 '19 at 10:32
  • Nah, that has nothing to do with permutations. Incrementing and carrying over is just the right solution for that, or maybe doing it with `n` recursions - similar to [the cartesian product](https://stackoverflow.com/a/15310051/1048572) but using the same `[0...k]` every time. – Bergi Jul 29 '19 at 10:43
  • that's because today I was looking for alternative ways to do permutations and combinations (by using no recursion) and I ran into this page: rosettacode.org/wiki/Permutations_with_repetitions and its permutations with repetitions is exactly `n ^ k` possibilities too... just that their n and k are swapped (n choose k... for example 6 choose 20 , order important, with repetitions). Isn't permutations with repetitions just a special case of cartesian product when { ... } x { ... } x { ... } where each entry is exactly the same? – nonopolarity Jul 29 '19 at 11:06
  • "*Isn't permutations with repetitions just a special case of cartesian product*" - yes, precisely, and given that the code is very much unlike of that generating permutations I think that name is not chosen well. Even [on rosettacode they mention](https://rosettacode.org/wiki/Talk:Permutations_with_repetitions#Isn.27t_it_just_similar_to_.22Increment_a_numerical_string.22) that it's much more like incrementing a digit sequence. – Bergi Jul 29 '19 at 11:10

0 Answers0