How can I group the elements of a set into disjoint subsets in javascript?
combinations, javascript, permutation
Solution
If you only need the number of ways a group of 9 people can be divided into 3 subgroups of 2, 3 and 4 people each then that's easy to compute mathematically using `C` (the function to calculate the number of combinations).
- First you have 9 people out of which you need to select 2 people. Hence you do `C(9, 2)`.
- Next you have 7 people out of which you need to select 3 people. Hence you do `C(7, 3)`.
- Finally you have 4 people out of which you need to select 4 people. Hence you do `C(4, 4)`. However `C(n, n)` is always 1.
Hence the number of ways to divide a group of 9 people into 3 subgroups of 2, 3 and 4 people is `C(9, 2) * C(7, 3) * C(4, 4)`. This can be simplified to `C(9, 2) * C(7, 3)`, which is `36 * 35` which is `1260`.
We can write a function to compute this for us:
function ways(n) {
var l = arguments.length, w = 1;
for (var i = 1; i < l; i++) {
var m = arguments[i];
w *= combinations(n, m);
n -= m;
}
return w;
}
To make this function work we need to define the function `combinations`:
function combinations(n, k) {
return factorial(n) / factorial(n - k) / factorial(k);
}
Finally we need to define the function for `factorial`:
function factorial(n) {
var f = n;
while (--n) f *= n;
return f;
}
Then we compute the number of ways as follows:
alert(ways(9, 2, 3)); // 1260
You can see the demo here: http://jsfiddle.net/bHSuh/
Note that we didn't need to specify the last subgroup of 4 people because that is implied.
However I believe that you want to generate each possible way. This is the sort of thing that the `amb` operator is perfect for. So the first thing we'll do is write the `amb` operator in JavaScript:
function amb(options, callback) {
var length = options.length;
for (var i = 0; i < length; i++) {
try {
callback(options[i]); // try the next option
return; // no problem, quit
} catch (e) {
continue; // problem, next
}
}
throw new Error("amb tree exhausted"); // throw a tantrum
}
Next we'll write a function which picks a given set of items from a list of indices:
function pick(list, items) {
var length = list.length, selected = [], rest = [];
for (var i = 0; i < length; i++) {
if (items.indexOf(i) < 0) rest.push(list[i]);
else selected.push(list[i]);
}
return [selected, rest];
}
We also need a function which will generate a list of indices:
function getIndices(length) {
var indices = [];
for (var i = 0; i < length; i++)
indices.push(i);
return indices;
}
Finally we'll implement the `group` function recursively:
function group(options, divisions) {
var subgroup = [], groups = [], n = 0;
var indices = getIndices(options.length);
var division = divisions.shift(), remaining = divisions.length;
try {
amb(indices, select);
} catch (e) {
return groups;
}
function select(index) {
subgroup.push(index);
if (++n < division) {
try { amb(indices.slice(index + 1), select); }
catch (e) { /* we want to continue processing */ }
} else {
var subgroups = pick(options, subgroup);
if (remaining) {
var children = group(subgroups.pop(), divisions.slice());
var length = children.length;
for (var i = 0; i < length; i++)
groups.push(subgroups.concat(children[i]));
} else groups.push(subgroups);
}
n--;
subgroup.pop();
throw new Error;
}
}
Now you can use it as follows:
var groups = group([
"aldo", "beat", "carla",
"david", "evi", "flip",
"gary", "hugo", "ida"
], [2, 3]);
Notice again that you didn't need to specify the last subgroup of 4 people since it's implied.
Now let's see whether the output is as we expected it to be:
console.log(groups.length === ways(9, 2, 3)); // true
There you go. There are exactly 1260 ways that a group of 9 people can be divided into 3 subgroups of 2, 3 and 4 people each.
Now I know that my `group` function looks a little daunting but it's actually really simple. Try to read it and understand what's going on.
Imagine that you're the boss of 9 people. How would you divide them into 3 subgroups of 2, 3 and 4 people? That's exactly the way my `group` function works.
If you still can't understand the logic after a while then I'll update my answer and explain the `group` function in detail. Best of luck.
BTW I just realized that for this problem you don't really need `amb`. You may simply use `forEach` instead. The resulting code would be faster because of the absence of try-catch blocks:
function group(options, divisions) {
var subgroup = [], groups = [], n = 0;
var indices = getIndices(options.length);
var division = divisions.shift(), remaining = divisions.length;
indices.forEach(select);
return groups;
function select(index) {
subgroup.push(index);
if (++n < division) indices.slice(index + 1).forEach(select);
else {
var subgroups = pick(options, subgroup);
if (remaining) {
var children = group(subgroups.pop(), divisions.slice());
var length = children.length;
for (var i = 0; i < length; i++)
groups.push(subgroups.concat(children[i]));
} else groups.push(subgroups);
}
subgroup.pop();
n--;
}
}
Since we don't use `amb` anymore the execution time of the program has decreased tenfold. See the result for yourself: http://jsperf.com/amb-vs-foreach
Also I've finally created a demo fiddle of the above program: http://jsfiddle.net/Ug6Pb/
Problem
In how many ways can a group of 9 people work in 3 disjoint subgroups of 2, 3 and 4 persons? How can I generates all the possibilities via backtracking with javascript. Example: ``` Gs = group([aldo,beat,carla,david,evi,flip,gary,hugo,ida],[2,2,5]); console.log(Gs); // [[aldo,beat],[carla,david],[evi,flip,gary,hugo,ida]], ... ``` Note that I do not want permutations of the group members; i.e. [[aldo,beat],...] is the same solution as [[beat,aldo],...]. However, there's a difference between [[aldo,beat],[carla,david],...] and [[carla,david],[aldo,beat],...]. *No libraries please.