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

by

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);

More Related Contents:

  1. Recursively print all permutations of a string (Javascript)
  2. Permutations without recursive function call
  3. Finding all permutations of array elements as concatenated strings
  4. How do I check if an array includes a value in JavaScript?
  5. How to generate all permutations of a list?
  6. Finding All Combinations (Cartesian product) of JavaScript array values
  7. How do you sort an array on multiple columns?
  8. How might I find the largest number contained in a JavaScript array?
  9. Find all possible subset combos in an array?
  10. JavaScript – get the first day of the week from current date
  11. How to draw sky chart? [closed]
  12. Javascript – Generating all combinations of elements in a single array (in pairs)
  13. Shuffle list, ensuring that no item remains in same position
  14. Fastest way to flatten / un-flatten nested JavaScript objects
  15. Does javascript process using an elastic racetrack algorithm
  16. What’s the algorithm to calculate aspect ratio?
  17. Javascript algorithm to find elements in array that are not in another array
  18. Packing different sized circles into rectangle – d3.js
  19. Using Canvas to animate a sorting algorithm in JS
  20. Calculating the shortest route between two points
  21. Sieve of Eratosthenes algorithm in JavaScript running endless for large number
  22. Find maximum possible time HH:MM by permuting four given digits
  23. Solving TicTacToe with minimax algorithm in Javascript
  24. How to implement a constraint solver for 2-D geometry?
  25. sort outer array based on values in inner array, javascript
  26. Paint algorithm leaving white pixels at the edges when I color [duplicate]
  27. Creating an array consisting of the largest values of each sub-array does not work as expected
  28. Randomizing elements in an array?
  29. Two-sum Leetcode explanation, Hashmap, Javascript
  30. Variable amount of nested for loops

Leave a Comment