Generate all different available combinations

combinationscombinatoricsextremal-combinatorics

Disclaimer: Sorry in advance if I make stupid mathematic assumptions or no-sense questions

I have a list of 25 numbers (from 1 to 25) and I need to generate 36 different groups/combinations of 4 numbers using exactly 6 times each number.

By my tests so far, only 24 differents combinations are possible, since 24 time you have to repeat at least 2 numbers (if I'm not wrong), so the goal, if this assumption is correct, is to place (repeat) numbers is the same group as less as possible.

I have an algorithm written in JS but I just only been able to generate the groups with some numbers not used 6 times and with more repetitions than desired.

Whith the described conditions, which I repeat:

  • 30 Different groups of 4 numbers and 5 differents groups of 5 numbers
  • No repetitions (or the less possibles): Whenever possible, same numbers MUST no coincide in the same group more than once,
    • e.g: if a group is (1,2,3,4), any of these numbers can coincide in other group again.
  • Related to previous point, when mathematically is not possible (as we have to generate 36 groups), the next aproach is that any number can coincide with only another number (max) that have already coincide.
    • e.g: if a group is (1,2,3,4), another group could be (1,2,X,X), (1,3,X,X), (1,4,X,X), (2,3,X,X), (2,4,X,X), (3,4,X,X), but not, for instance, (1,2,3,X)
  • If we face again into a mathematical limit, the next approach will be 3 repetitions in a group…etc.
  • Use each number 6 times (this is a MUST, no more, no less)

Which would be the better approach taking into account that conditions?

Best Answer

No repeated pairs or trios:

{1,2,6,17,21}
{1,4,7,14,19}
{1,5,8,16}
{1,9,13,24}
{1,10,23,25}
{1,12,15,22}
{2,3,19,23,24}
{2,4,10,15}
{2,5,11,13}
{2,7,22,25}
{2,8,14,18}
{3,4,18,20}
{3,5,7,10}
{3,6,15,25}
{3,9,12,16,21}
{3,13,14,17}
{4,5,9,25}
{4,6,8,13,22}
{4,11,17,24}
{5,12,14,24}
{5,15,17,19}
{6,7,16,24}
{6,9,11,14}
{6,10,12,19,20}
{7,11,12,18}
{7,13,20,23}
{8,9,15,20}
{8,10,11,21}
{8,12,17,23}
{9,18,22,23}
{10,13,16,18}
{11,16,19,22}
{14,15,21,23}
{16,17,20,25}
{18,19,21,25}
{20,21,22,24}

I used integer linear programming with a binary variable for each possible group of 4 or 5 numbers.