Specific combination algorithm

Question

If I have n balls and k containers then this -> ( (n+k-1)! / n!(k-1)! ) will work out how many combinations there are.

I am having difficulty changing this to produce a list of all combinations in javascript.

In a function taking an array of balls and some amount of containers.

combinations([1,2,3,4,5,6], 3)

Each container can have any number of balls and containers can be empty.

Here is something i attempted but im only getting one ball in each container.

function generateCombinations(array, r, callback) {
 function equal(a, b) {
 for (var i = 0; i < a.length; i++) {
 if (a[i] != b[i]) return false;
 }
 return true;
 }
 function values(i, a) {
 var ret = [];
 for (var j = 0; j < i.length; j++) ret.push(a[i[j]]);
 return ret;
 }
 var n = array.length;
 var indices = [];
 for (var i = 0; i < r; i++) indices.push(i);
 var final = [];
 for (var i = n - r; i < n; i++) final.push(i);
 while (!equal(indices, final)) {
 callback(values(indices, array));
 var i = r - 1;
 while (indices[i] == n - r + i) i -= 1;
 indices[i] += 1;
 for (var j = i + 1; j < r; j++) indices[j] = indices[i] + j - i;
 }
 callback(values(indices, array));
}
count = 0
generateCombinations([1,2,3,4,5,6,7,8,9,1],3,function(first){
 $("#hello").append(first+"<br />")
 count = count +1
})
$("#hello").append(count)

• Ja͢ck: Would it help if I told you there are no practical short cuts you can take to generate it? :)
• Nayuki: You will have to exercise some recursion and good ol' computer science skills to solve this.
• dda: And come back here with whatever you tried.

Answer 1

You can do it in this way:

var containers = [];
// n - number of balls, k - number of containers
function dfs(n, k) {
 // Ending point of recursion, all balls are placed
 if(n == 0) {
 var output = [];
 for(var i = 0; i < k; i++) {
 output.push('{' + containers[i].join(', ') + '}');
 }
 output = '[' + output.join(', ') + ']';
 console.log(output);
 return;
 }
 // Try to put ball #n
 for(var i = 0; i < k; i++) {
 containers[i].push(n);
 // Now we have placed ball #n, so we have 1 .. n - 1 balls only
 dfs(n - 1, k);
 // Remove ball when back to use again
 containers[i].pop();
 }
}
var n = 4;
var k = 3;
for(var i = 0; i < k; i++) {
 containers[i] = [];
}
dfs(n, k);

Answer 2

I initially thought you wanted all the combinations of k elements out of n, but your problem is different, it's partitioning n elements in k parts.

When going through the elements, at each steps, you may choose to put the current element in any container, that's k possibilities. In total, you will have kⁿ possible solutions.

Therefore, it would be faster to iterate through all the solutions, rather than storing them in an array.

You can represent a solution as a unique number in base k, with n digits, and iterate through the solutions by incrementing that number.

In your example, the base is 3, and the number of digits is 6. The first solution is to put all the balls in container 0, ie.

 000000

The next solution is to put all the balls in container 0, excepted the last which goes in container 1.

 000001

... 000002 000010 000011 000020

Hopefully you should get the idea.