Given an array, how to generate all combinations of subset size k?

Question

So given input = [1, 2, 3] and k=2 this would return:

1 2
1 3
2 1
2 3
3 1
3 2

This is the closest to what I am looking for, but not quite: http://algorithms.tutorialhorizon.com/print-all-combinations-of-subset-of-size-k-from-given-array/

function subsetsOfSize(a, used, startIndex, currentSize, k) {
  if (currentSize === k) {
    for (var i = 0; i < a.length; i++) {
      if (used[i])
        console.log(a[i]);
    }
    console.log('-');
    return;
  }
    
  if (startIndex === a.length)
    return;
    
  used[startIndex] = true;
  subsetsOfSize(a, used, startIndex+1, currentSize+1, k);

  used[startIndex] = false;
  subsetsOfSize(a, used, startIndex+1, currentSize, k);
}

var input = [1,2,3];
subsetsOfSize(input, Array(input.length).fill(false), 0, 0, 2);

^ Missing results such as 2 1, 3 1, 3 2, etc.

Secondly, I am not sure if I am naming this problem correctly because solutions to "all combinations of subset of size k" do not give the expected answer.

Answer 1

A recursive solution to find k-subset permutations (in pseudo-code):

kSubsetPermutations(partial, set, k) {
    for (each element in set) {
        if (k equals 1) {
            store partial + element
        }
        else {
            make copy of set
            remove element from copy of set
            recurse with (partial + element, copy of set, k - 1)
        }
    }
}

Here's a run-through for an example:

input: [a,b,c,d,e]
k: 3

partial = [], set = [a,b,c,d,e], k = 3
    partial = [a], set = [b,c,d,e], k = 2
        partial = [a,b], set = [c,d,e], k = 1 -> [a,b,c], [a,b,d], [a,b,e]
        partial = [a,c], set = [b,d,e], k = 1 -> [a,c,b], [a,c,d], [a,c,e]
        partial = [a,d], set = [b,c,e], k = 1 -> [a,d,b], [a,d,c], [a,d,e]
        partial = [a,e], set = [b,c,d], k = 1 -> [a,e,b], [a,e,c], [a,e,d]
    partial = [b], set = [a,c,d,e], k = 2
        partial = [b,a], set = [c,d,e], k = 1 -> [b,a,c], [b,a,d], [b,a,e]
        partial = [b,c], set = [a,d,e], k = 1 -> [b,c,a], [b,c,d], [b,c,e]
        partial = [b,d], set = [a,c,e], k = 1 -> [b,d,a], [b,d,c], [b,d,e]
        partial = [b,e], set = [a,c,d], k = 1 -> [b,e,a], [b,e,c], [b,e,d]
    partial = [c], set = [a,b,d,e], k = 2
        partial = [c,a], set = [b,d,e], k = 1 -> [c,a,b], [c,a,d], [c,a,e]
        partial = [c,b], set = [a,d,e], k = 1 -> [c,b,a], [c,b,d], [c,b,e]
        partial = [c,d], set = [a,b,e], k = 1 -> [c,d,a], [c,d,b], [c,d,e]
        partial = [c,e], set = [a,b,d], k = 1 -> [c,e,a], [c,e,b], [c,e,d]
    partial = [d], set = [a,b,c,e], k = 2
        partial = [d,a], set = [b,c,e], k = 1 -> [d,a,b], [d,a,c], [d,a,e]
        partial = [d,b], set = [a,c,e], k = 1 -> [d,b,a], [d,b,c], [d,b,e]
        partial = [d,c], set = [a,b,e], k = 1 -> [d,c,a], [d,c,b], [d,c,e]
        partial = [d,e], set = [a,b,c], k = 1 -> [d,e,a], [d,e,b], [d,e,c]
    partial = [e], set = [a,b,c,d], k = 2
        partial = [e,a], set = [b,c,d], k = 1 -> [e,a,b], [e,a,c], [e,a,d]
        partial = [e,b], set = [a,c,d], k = 1 -> [e,b,a], [e,b,c], [e,b,d]
        partial = [e,c], set = [a,b,d], k = 1 -> [e,c,a], [e,c,b], [e,c,d]
        partial = [e,d], set = [a,b,c], k = 1 -> [e,d,a], [e,d,b], [e,d,c]

function kSubsetPermutations(set, k, partial) {
    if (!partial) partial = [];                 // set default value on first call
    for (var element in set) {
        if (k > 1) {
            var set_copy = set.slice();         // slice() creates copy of array
            set_copy.splice(element, 1);        // splice() removes element from array
            kSubsetPermutations(set_copy, k - 1, partial.concat([set[element]]));
        }                                       // a.concat(b) appends b to copy of a
        else document.write("[" + partial.concat([set[element]]) + "] ");
    }
}
kSubsetPermutations([1,2,3,4,5], 3);

Answer 2

Instead of combinations, try permutations.

Try generating permutations, then resizing the array.

Here's it implemented, modified from here

var permArr = [],
  usedChars = [];

function permute(input, k) {
  var i, ch;
  for (i = 0; i < input.length; i++) {
    ch = input.splice(i, 1)[0];
    usedChars.push(ch);
    if (input.length == 0) {
      var toadd = usedChars.slice(0,k);
      if(!permArr.includes(toadd)) permArr.push(toadd); // resizing the returned array to size k
    }
    permute(input, k);
    input.splice(i, 0, ch);
    usedChars.pop();
  }
  return permArr
};
console.log(JSON.stringify(permute([1, 2, 3], 2)));

Answer 3

You could take a generator function.

function* permutation(array, k, head = []) {
    if (!k) {
        yield head;
        return;
    };
    for (let i = 0; i < array.length; i++) {
        yield* permutation(array.filter((_, j) => j !== i), k - 1, [...head, array[i]]);
    }
}

// example 1
const p = permutation([1, 2, 3, 4, 5, 6], 4);
console.log(...p.next().value);
console.log(...p.next().value);
console.log(...p.next().value);
console.log(...p.next().value);
console.log(...p.next().value);
console.log(...p.next().value);
console.log(...p.next().value);
console.log(...p.next().value);

// example 2
[...permutation([1, 2, 3, 4], 3)].forEach(a => console.log(...a));

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 4

Here's a version which doesn't try to be too clever, and doesn't exercise any "modern" features of JavaScript other than generator functions (which are not that modern). Unlike most of the solutions here, this one works even if the input has duplicates. (It only produces each unique permutation once.)

It avoids the need for associative datatypes like Sets and Maps by simply never generating the same permutation twice. That, plus the fact that it avoids unnecessary copies of internal structures, does make it reasonably fast; at least, it seems to be measurably faster than any of the other answers to this question. (By fast, I mean "per permutation". JSBench clocked it at 4.3 million 3-permutations per second and about three million 6-permutations per second, running under Chrome on my consumer-level laptop.)

Generators are the most natural way to implement combinatoric enumeration. Trying to accumulate millions of alternatives (or more) in an array is a recipe for memory exhaustion; the size of the search space rapidly gets out of hand. Based on the above numbers, it's reasonable to attempt a search through hundreds of millions of permutations. (That will take a few minutes, maybe more, depending on how fast you can check each permutation. Still, a few minutes is OK for research purposes.) But constructing an array of hundreds of millions of permutations is going to slow things down a lot, if it is even possible on the machine you're using. In the vast majority of combinatoric searches, there is no need for such an array. You can process each candidate as it is generated, or at least filter the generated candidates in order to accumulate a (much) smaller list of feasible candidates for further processing.

If generators make you nervous for some reason, you could use an additional argument specifying a function to be called with each candidate. Or you could use a hybrid, using a check function to decide whether or not to yield the candidate. That might be a better architecture if you can rapidly discard most of the possibilities, since unwinding the yield* through several layers is quite a bit slower than just calling a function.

Parts of the following snippet were borrowed from @NinaScholz. Thanks!

function* kperm(arr, k) {
    let data = arr.slice().sort();
    k = Math.min(k, data.length);

    function* helper(i) {
        if (i == k) 
            yield data.slice(0, k);
        else {
            for (let j = i+1; j < data.length; j++) {
                if (data[j] != data[i]) {
                    yield* helper(i+1);
                    const tmp = data[i];
                    data[i] = data[j];
                    data[j] = tmp;
                }
            }
            yield* helper(i+1);
            const tmp = data[i];
            for (let j = i+1; j < data.length; j++)
                data[j-1] = data[j];
            data[data.length - 1] = tmp;
        }
    }
    yield* helper(0);
}
// example 1
console.log("Example 1, first 8 permutations");
const p = kperm([1, 2, 3, 4, 1, 2, 3, 4], 4);
for (let i = 1; i < 8; ++i) 
    console.log(...p.next().value);

console.log("Example 2");
[...kperm([1, 2, 1, 2, 2], 4)].forEach(a => console.log(...a));

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 5

I don't really see how the newer Set and Map can really help here. But here is a fairly simple recursive version:

const nPermutations = (xs, n) =>
  xs .length < 1 || n < 1
    ? [[]]
    : xs .flatMap (
        (x, i) => nPermutations(
          [...xs .slice (0, i), ...xs .slice (i + 1)],
          n - 1
        ). map (p => [x, ...p])
      )

console .log (nPermutations ([1, 2, 3], 2))

.as-console-wrapper {max-height: 100% !important; top: 0}

In practice, I would probably extract a function that creates a copy of an array excluding one index, like this:

const excluding = (i, xs) =>
  [...xs .slice (0, i), ...xs .slice (i + 1)]

const nPermutations = (xs, n) =>
  xs .length < 1 || n < 1
    ? [[]]
    : xs .flatMap (
        (x, i) => nPermutations (excluding (i, xs), n - 1). map (p => [x, ...p])
      )

Answer 6

I'm a simple person:

make an array M with size k

fill M with zeroes

loop this:

M[0] += 1

loop through M: *if (M[i] >= size of N) then set M[i]=0 and increase M[i+1] += 1

if M has only different numbers then you've find yourself the indices of a subset of n

loop ends when the last element of M reaches size of n - minus one a.k.a. when the * condition would cause an error