Devide N points to S sets (all possible combinations)

Hi all,

My goal is to devide N points (about 100) to S groups (about 5) with all possible combinations. The result should be a 3D matrix A, that will store the indexes of the numbers. A(i,j,k) = j'th index of a number in option k, group i. All groups must be roughly the same size.

function [A] = myfunc (N,S)

For example: N=3,S=2

[A] = myfunc (3,2) % indexes= 1,2,3

A(:,:,1) =

1 2

3

A(:,:,2) =

1 3

2

A(:,:,3) = %option #3

2 3 %group #1

1 %group #2

myfunc (3,2) was easy enough to do by hand, but I need something that will give a result for myfunc (100,5).

I was thinking about somekind of recursive algorithm that uses "combnk" function, but it is not an easy one.

I appreciate your help.

EDIT: Maybe N=20, S=3 will do the job.

Answer 1

[John D'Errico]

All possible combinations? Seriously? 100 numbers, into all possible subgroups of 5 groups, or so? Roughly? Must all groups be the same size?

Lets see, how many ways to do this? Even if we make all subgroups the same size, the number of ways to do this is pretty easy to compute.

Lets see, pick 20 numbers for group 1.

nchoosek(100,20)
Warning: Result may not be exact. Coefficient is greater than 9.007199e+15 and is only accurate to 15 digits 
> In nchoosek (line 92) 
ans =
   5.3598e+20

So there are quite a few ways to do that. It gets worse of course, if we can let the group size vary.

But now, we need to multiply that by the number of ways we can assign group 2.

nchoosek(80,20)
Warning: Result may not be exact. Coefficient is greater than 9.007199e+15 and is only accurate to 15 digits 
> In nchoosek (line 92) 
ans =
   3.5353e+18

Hmm. Still a LOT. Don't forget groups 3 and 4.

nchoosek(60,20)
ans =
   4.1918e+15
>> nchoosek(40,20)
ans =
   1.3785e+11

At least group 5 is now fixed. So we take the product of all those numbers. Then recognize that we need to reduce things by a bit, since we might swap the groups around, and still have effectively the same result.

nchoosek(100,20)*nchoosek(80,20)*nchoosek(60,20)*nchoosek(40,20)/factorial(5)
Warning: Result may not be exact. Coefficient is greater than 9.007199e+15 and is only accurate to 15 digits 
> In nchoosek (line 92) 
Warning: Result may not be exact. Coefficient is greater than 9.007199e+15 and is only accurate to 15 digits 
> In nchoosek (line 92) 
ans =
   9.1243e+63

So only something like 9.1e63 ways to do this choice. Plus or minus a few. Way more if you are willing to vary the sub-group sizes.

Do you have a big computer? No, I mean, a really big computer? No, you don't quite get it yet. A REALLY, REALLY, REALLY, MASSIVELY, HUMONGOUSLY BIG computer? I mean the kind of computer that god would use to simulate the entire universe, down at the elementary particle level? And he would still wish he had more memory and a faster computer.

People think their computer is really big and fast. It is not. It cannot do anything. This is why you use mathematics. You find ways of solving a problem, where a brute force, frontal attack would wither and die at the mere thought. Or, you buy yourself one big honkingly massive computer. I hope you have a good grant.

[Ilya Tcenov]

I could ask god if he could land me his computer (if he is done with universe simulations), but maybe instead I could decrease these numbers.

Maybe N=20, S=3 will do the job.

[John D'Errico]

Even at that, you might be surprised.

nchoosek(20,7)*nchoosek(13,7)
ans =
   133024320

So if we pick groups of size 7, 7, and 6, then there are 133 million ways or so to divvy things up. Nothing stops you from doing this. It is a big problem, even for the really small one you have reduced things to. You might run out of memory even for this small case, to generate all of those combinations, and you would certainly be close.

How might I do this for a sufficiently small problem? Say 3 groups from the numbers 1:9, thus each of size 3?

nchoosek(9,3)*nchoosek(6,3)
ans =
        1680

So 1680 groupings. Pick the 84 possible sets of three numbers to go into the first group.

group1 = nchoosek(1:9,3);

In each case, there are 6 numbers that remain. Pick the members of group 2 from those sets. Of course group 3 is chosen perforce at that point.