Binomial sub arrays

Question

I have an A array with n length. I want to take all possible k (0

for example, if i have A's length is five:

[1,2,3,4,5]

and if k = 3, algorithm must give me B array.

[1,2,3    ]
[1,2,  4  ]
[1,2,    5]
[1,  3,4  ]
[1,  3,  5]
[1,    4,5]
[  2,3,4  ]
[  2,3,  5]
[  2,  4,5]
[    3,4,5]

Length of B would be equal to n!/k!(n-k)! ('!' means factorial, Newtons method)

I'm using javascript, so in my tags i included it, but it's just algorithm, not necessary written in javascript.

See [Algorithm to return all combinations of k elements from n](http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n) — Marty McVry, Apr 05 '13 at 10:49
Possible duplicate - http://stackoverflow.com/questions/5752002/find-all-possible-subset-combos-in-an-array — ChrisF, Apr 05 '13 at 12:21

score 0 · Answer 1 · answered Apr 05 '13 at 11:58

You could do this via a filter method.

In your example you want to receive all permutations of an array, taking a specific number of elements of that array.

You can easily do that in an iterative manner. Start by taking all permutations of n - 1 elements of an array:

// return all (n - 1) element permutations of an array
var permutations = function(arr) {
  return arr.reduce(function(re, value, i) {
    // add an array for each element in the original array
    return re.concat([arr.filter(function(v, index) {
      // drop each element with the same index
      return index !== i 
    })])
  }, [])
}

Now permutations([1,2,3]) would return [[1,2], [1,3], [2,3]] That's always a disjoint set suppose you're having only unique values in the source array.

To receive all 3-element arrays of a 5-element array, you would first calculate the list of 4-element arrays and transform each of them to a 3-element array.

permutations([1,2,3,4]).map(permutations)
=> [[1,2,3] => [[[1,2], [1,3], [2,3]]
   ,[1,2,4]    ,[[1,2], [1,4], [2,4]]
   ,[1,3,4]    ,[[1,3], [1,4], [3,4]]
   ,[2,3,4]    ,[[2,3], [2,4], [3,4]]
   ]           ]

Obviously the problem here is that there are doubles. That can be solved by dropping all non-unique values.

var unique = function(arr) {
  var s = arr.map(function(v) { return "" + v })
  return arr.filter(function(v, i) { return s.indexOf("" + v) == i })
}

Packing it all into one function could be done like this:

var permutationsWithLength = function(arr, length) {
  var re = [arr]
  for (var i = arr.length; i >= length; i--) {
    re = re.reduce(function(tmp, perms) {
      return unique(temp.concat(permutations(perms)))
    }, [])
  }
  return re
}

I admit that this may not be the fastest approach, especially regarding the unique function, but it's a very generic one and will work for the problem you described even with larger arrays.

Hope it helps ;)

score -1 · Accepted Answer · answered Apr 05 '13 at 11:33

Below is the copy-paste from one of my projects. Don't know if it still works ;)

var choose = function choose_func(elems, len) {
  var result = [];
  for (var i=0; i<elems.length; i++) {
    if (len == 1) {
      result.push([elems[i]]);
    } else {
      var remainingItems = choose_func(elems.slice(i+1, elems.length), len - 1);
      for (var j=0; j<remainingItems.length; j++) 
        result.push([elems[i]].concat(remainingItems[j])); 
    }
  }
  return result;
};

var result = choose([1,2,3,4,5], 3)

/*result  = [[1,2,3],[1,2,4],[1,2,5],[1,3,4],[1,3,5],
             [1,4,5],[2,3,4],[2,3,5],[2,4,5],[3,4,5]] */

not even fast method, but i have no big data, so it's quite enough for me. thanks — , Apr 05 '13 at 14:22

Binomial sub arrays

2 Answers2