Effective algorithm for obtaining combinations of all elements in an object

Question

Given an array or object with n keys, I need to find all combinations with length x .
Given x is a variable. binomial_coefficient(n,x) .

I am currently using this:

 function combine(items) { var result = []; var f = function(prefix, items) { for (var i = 0; i < items.length; i++) { result.push(prefix + items[i]); f(prefix + items[i], items.slice(i + 1)); } } f('', items); return result; } var combinations = combine(["a", "b", "c", "d"]); 

Output:

 ["a", "ab", "abc", "abcd", "abd", "ac", "acd", "ad", "b", "bc", "bcd", "bd", "c", "cd", "d"] 

So, if I need a binomial coefficient x=3 of n=4 , I select all rows with a length of three. {abc, abd, acd, bcd}.

So, I am doing this in two steps.

Is there a more efficient algorithm with less complexity?

Link: Solution Efficiency (JSPerf)

Answer 1

Your algorithm is almost O(2^n) , you can refuse a lot of combinations, but the number of elements will be (n! * (nx)!) / x! .

To discard useless combinations, you can use an indexed array.

  function combine(items, numSubItems) { var result = []; var indexes = new Array(numSubItems); for (var i = 0 ; i < numSubItems; i++) { indexes[i] = i; } while (indexes[0] < (items.length - numSubItems + 1)) { var v = []; for (var i = 0 ; i < numSubItems; i++) { v.push(items[indexes[i]]); } result.push(v); indexes[numSubItems - 1]++; var l = numSubItems - 1; // reference always is the last position at beginning while ( (indexes[numSubItems - 1] >= items.length) && (indexes[0] < items.length - numSubItems + 1)) { l--; // the last position is reached indexes[l]++; for (var i = l +1 ; i < numSubItems; i++) { indexes[i] = indexes[l] + (i - l); } } } return result; } var combinations = combine(["a", "b", "c", "d"], 3); console.log(JSON.stringify(combinations)); 

For example, the first combination has indices: [0, 1, 2] and elements ["a", "b", "c"] . To calculate the next combination, he gets the last index 2 and tries to increase, if the increment is less than the maximum position (in this case 4 ), the next combination will be achieved, but if it is not, it must increase to the previous index.

Answer 2

You can use an iterative and recursive approach with stress along the length of the array and still the necessary elements.

Basically, combine() takes an array with the values ​​to be combined, and the size of the required combination of result sets.

The internal function c() takes an array of previously made combinations and the initial value as the index of the original array for the combination. Return is an array with all the combinations made.

The first call to allways c([], 0) , due to an empty array of results and an initial index of 0.

 function combine(array, size) { function c(part, start) { var result = [], i, l, p; for (i = start, l = array.length; i < l; i++) { p = part.slice(0); // get a copy of part p.push(array[i]); // add the iterated element to p if (p.length < size) { // test if recursion can go on result = result.concat(c(p, i + 1)); // call c again & concat rresult } else { result.push(p); // push p to result, stop recursion } } return result; } return c([], 0); } console.log(combine(["a", "b", "c", "d"], 3)); 

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

Answer 3

We could only create combinations that interest us. In addition, instead of cloning arrays using a slice in each call, we can use a pointer to the original array. Here is one version. Converting it to recursion without an external global variable remains in the form of an exercise.

 function choose(ns,r){ var res = []; function _choose(i,_res){ if (_res.length == r){ res.push(_res); return; } else if (_res.length + ns.length - i == r){ _res = _res.concat(ns.slice(i)); res.push(_res); return } var temp = _res.slice(); temp.push(ns[i]); _choose(i + 1,temp); _choose(i + 1,_res); } _choose(0,[]); return res; } var combinations = choose(["a", "b", "c", "d"], 3); console.log(JSON.stringify(combinations)); 

Answer 4

And here is the real recursion.

 function seq(a,b){ var res = []; for (var i=a; i<=b; i++) res.push(i); return res; } function f(n,k){ if (k === 0) return [[]]; if (n === k) return [seq(1,n)]; let left = f(n - 1, k - 1), right = f(n - 1, k); for (let i=0; i<left.length; i++) left[i].push(n); return left.concat(right); } console.log(JSON.stringify(f(4,3)))