All unique combinations for n objects of group size m without repetition or remainders.

combinatorics

I'm trying to determine if there is a formula/algorithm for generating all unique combinations of n objects of group size m without any repetition or remainders.

Consider a list of 4 numbers [1, 2, 3, 4]

Using the combinations formula $C(n,r)$ we can find the number of unique combinations for a given group size. For example, the number of possible combinations for 4 objects of group size 3 is 4.

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

However, I only want to view a combination as valid if there are no repetitions. If at least two or more numbers of the combination have been grouped together before, I consider this a repetition.

For example, [1, 2, 3] and [1, 2, 4] has a repetition of the pair [1, 2].

Therefore, we would only be able to pick one of the potential combinations of size 3, leaving one number from the list leftover as a remainder. For example, If I chose [1, 2, 3] the remainder would be 4.

Given the constraints of the problem, the only valid group size of 4 objects is 1, 2, and 4.

Although there are a few exceptions involving the numbers 1 and 2, we can check whether a m and n are viable options by checking whether the following equations are evenly divisible:

  • $m/n$
  • $m-1/n-1$

Unfortunately, this doesn't account for repetitions. Is there a way to find all m group sizes that don't contain remainders or repetitions for n objects?

I considered using a binary counter as was suggested in this post here. While this could work in theory, this solution doesn't seem very scalable for larger numbers of objects.

Larger Example:

$n = 16$

$m = 4$

items = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]

possible combinations: $C(16,4) = 1820$

valid combinations: $20$

[1, 2, 3, 4]
[1, 5, 9, 13]
[1, 6, 11, 16]
[1, 7, 12, 14]
[1, 8, 10, 15]
[2, 5, 12, 15]
[2, 6, 10, 14]
[2, 7, 9, 16]
[2, 8, 11, 13]
[3, 5, 10, 16]
[3, 6, 12, 13]
[3, 7, 11, 15]
[3, 8, 9, 14]
[4, 5, 11, 14]
[4, 6, 9, 15]
[4, 7, 10, 13]
[4, 8, 12, 16]
[5, 6, 7, 8]
[9, 10, 11, 12]
[13, 14, 15, 16]

EDIT:

  • Reworded the explanation of repetitions for clarity.
  • Provided a larger example at the bottom

Best Answer

EDIT

This is the exact problem answered by Stiener systems. More information can be found here.

ORIGINAL ANSWER

After taking a step back over the holidays, I came up with this equation to determine the number of possible combinations. I'm not sure of a way to prove this works for all cases, but at least for the ones I've checked it holds true.

I simply multiplied the two equations I listed before to check for divisibility together. This results in the following equation:

$m^2-m/n^2-n$

If we only take answers result in whole numbers, this gives the number of valid combinations without repetitions or remainders. Currently, I am unsure of a way to generate the combinations themselves. I'm attempting to write some code in python that does this for me.

Example 1:

$m = 3$

$n = 2$

$3^2-3/2^2-2$

$9-3/4-2$

$6/2 = 3$

[1, 2]
[2, 3]
[1, 3]

Example 2:

$m = 7$

$n = 3$

$7^2-7/3^2-3$

$49-7/9-3$

$42/6 = 7$

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

Example 3:

$m = 16$

$n = 4$

$16^2-16/4^2-4$

$256-16/16-4$

$240/12 = 20$

[1, 2, 3, 4]
[1, 5, 9, 13]
[1, 6, 11, 16]
[1, 7, 12, 14]
[1, 8, 10, 15]
[2, 5, 12, 15]
[2, 6, 10, 14]
[2, 7, 9, 16]
[2, 8, 11, 13]
[3, 5, 10, 16]
[3, 6, 12, 13]
[3, 7, 11, 15]
[3, 8, 9, 14]
[4, 5, 11, 14]
[4, 6, 9, 15]
[4, 7, 10, 13]
[4, 8, 12, 16]
[5, 6, 7, 8]
[9, 10, 11, 12]
[13, 14, 15, 16]
Related Question