EDITS
QUESTION
I am trying to create an algorithm that generates all unique combinations of m objects of group size n without repetitions or remainders. The output for this algorithm should result in every object being paired with every other object exactly once.
A repetition is whenever at least two or more numbers have already been grouped together previously.
For example, [1, 2, 3] and [1, 2, 4] has a repetition of the pair [1, 2].
Without remainders means that all groups of size n must be the same size.
The number of possible combinations for m and n can be calculated by using the function below. Additionally, because of the constraints of the problem, not all values of m and n are possible.
def iterations(m,n):
num = (m**2) - m
den = (n**2) - n
if den <= 0 or num <= 0:
return False
if (m - 1) % (n - 1) != 0:
return False
if num % den != 0:
return False
return int(num/den)
For example, iterations(9,3) would return 12. iterations(6,3) would return False. Why? Because there is no way for 6 objects (m) to be paired together only once using groups of 3 (n).
We can show this by attempting to manually construct the combinations for m=6, n=3.
[1, 2, 3]
[1, 4, 5]
[1, 6, _]
If we use the values of m=9, n=3 to generate our combinations, then the expected output would be 12 different groups:
[1, 2, 3]
[1, 4, 5]
[1, 6, 7]
[1, 8, 9]
[2, 4, 9]
[2, 5, 7]
[2, 6, 8]
[3, 4, 6]
[3, 7, 9]
[3, 5, 8]
[4, 7, 8]
[5, 6, 9]
The issue I'm having is with implementing the algorithm to generate the unique combinations. This is the code block I have in place for generating the unique combinations:
import random
class id ():
def __init__(self, name):
self.name = name
self.comparisons = []
def update_comparisons(self, id_list):
for id in id_list:
if id in self.comparisons:
self.comparisons.remove(id)
self.comparisons.extend(id_list)
self.comparisons.sort()
if self.name in self.comparisons:
self.comparisons.remove(self.name)
return self.comparisons
def get_ids(n):
ids = []
for i in range(1,n+1):
ids.append(id(i))
return ids
# Setting the values for m and n
m = 9
n = 3
# Creating list of ids
ids_master = get_ids(m)
ids = ids_master.copy()
comparisons = []
comparison_names = []
# Getting the number of required combinations
iter = iterations(9,3)
#
for i in range(iter):
temp = []
pos = 0
while len(temp) < n:
# Selecting an id
id_a = ids[pos]
"""
Checking if the id within temp have already been compared
or is a duplicate. If yes, add to the counter.
"""
counter = 0
for id_b in temp:
if id_b.name in id_a.comparisons or id_b.name == id_a.name:
counter += 1
"""
Checking if id_a has been compared to all other ids.
If yes, add to the counter.
"""
if len(id_a.comparisons) == m - 1:
counter += 1
"""
If id_a has passed the checks, the counter should be 0.
If the counter is 0, append it to temp_list
"""
if counter == 0:
temp.append(id_a)
pos += 1
"""
Once we've exited the while loop,
append the temp list to the list of comparisons.
"""
comparisons.append(temp)
# Updating the comparison for each id object
for comparison in comparisons:
names = [x.name for x in comparison]
names.sort()
for id in comparison:
id.update_comparisons(names)
comparison_names.append(names)
print(comparison_names)
The above code works for values of (3, 2), (5, 2), and (7, 3). However, (9, 3) comes with complications. The code will generate the following comparisons before running into a roadblock:
[1, 2, 3]
[1, 4, 5]
[1, 6, 7]
[1, 8, 9]
[2, 4, 6]
[2, 5, 7]
In this case, the next combination would be [2, 8, 9]. This doesn't work though since the pair [8, 9] has already been compared in [1, 8, 9]. The code then keeps iterating through the positions until it runs out of items to check in the list and gives the error "list index out of range".
I need a way for the algorithm to anticipate these errors. For example, the if the code generated [2, 4, 9] first instead of [2, 4, 6], the remaining combinations would probably work themselves out as normal. I'm sure there is a way to implement this but I'm not sure how to proceed.
Thanks in advance!
UPDATED CODE
First, I've updated the update_comparisons(self, id_list, mode = 'add') method for the id class as well as renamed the iterations(m,n) function to valid_comobos(m,n) for clarity.
import random
class id ():
def __init__(self, name):
self.name = name
self.comparisons = []
def update_comparisons(self, id_list, mode = 'add'):
# Removing duplicates
for id in id_list:
if id in self.comparisons:
self.comparisons.remove(id)
if mode == 'add':
self.comparisons.extend(id_list)
self.comparisons.sort()
if self.name in self.comparisons:
self.comparisons.remove(self.name)
return self.comparisons
if mode == 'del':
for id in id_list:
if id in self.comparisons:
self.comparisons.remove(id)
self.comparisons.sort()
return self.comparisons
if mode == 'reset':
self.comparisons.clear()
return self.comparisons
Secondly, I've added try: and except: statements to prune invalid results.
# Setting the values for m and n
m = 9
n = 3
# Creating list of ids
ids_master = get_ids(m)
ids = ids_master.copy()
comparisons = []
comparison_names = []
invalid = []
invalid_names = []
# Getting the number of required combinations
combos = valid_combos(m,n)
while len(comparisons) < combos:
temp = []
pos = 0
while len(temp) < n:
try:
if len(comparisons) < (m - 1)/(n - 1):
if len(temp) == 0:
temp.append(ids[0])
else:
id_a = random.choice(ids[1:])
counter = 0
for id_b in temp:
if id_b.name in id_a.comparisons or id_b.name == id_a.name:
counter += 1
if counter == 0:
temp.append(id_a)
else:
id_a = ids[pos]
"""
Checking if the id within temp have already been compared
or is a duplicate. If yes, add to the counter.
"""
counter = 0
for id_b in temp:
if id_b.name in id_a.comparisons or id_b.name == id_a.name:
counter += 1
"""
Checking if id_a has been compared to all other ids.
If yes, add to the counter.
"""
if len(id_a.comparisons) == m - 1:
counter += 1
"""
If the counter is 0 after the first two checks, validate it.
If the the validation check fails, add to the counter.
If the validation check succeeds, the counter will equal 0.
If the counter is 0, append the id to the temp_list
"""
if counter == 0:
v_check = temp.copy()
v_check.append(id_a)
v_names = [x.name for x in v_check]
for iv in invalid:
iv_names = [x.name for x in iv]
if v_names == iv_names:
counter += 1
if counter == 0:
temp.append(id_a)
pos += 1
except Exception as e:
temp.clear()
counter = 0
group_counter = 0
for comparison in comparisons:
id = comparison[0]
if len(id.comparisons) != m - 1:
if counter == 0:
invalid.append(comparison)
counter += 1
if counter == 0:
group_id = comparisons[-1][0]
previous_group_id = group_id.name - 1
for comparison in comparisons:
if comparison[0].name == group_id.name:
group_counter += 1
if comparison[0].name == previous_group_id:
if counter == 0:
invalid.append(comparison)
counter += 1
for i in range(counter + group_counter):
comparisons.remove(comparisons[-1])
for id in ids:
id.update_comparisons([], mode = 'reset')
for comparison in comparisons:
names = [x.name for x in comparison]
comparison_names.append(names)
for id in comparison:
id.update_comparisons(names, mode = 'add')
for iv in invalid:
iv_names = [x.name for x in iv]
break
if len(temp) == n:
comparisons.append(temp)
comparison_names = []
# Updating the comparison for each id object
for comparison in comparisons:
names = [x.name for x in comparison]
comparison_names.append(names)
for id in comparison:
id.update_comparisons(names, mode = 'add')
Some outputs for different values of m and n.
m = 7
n = 3
[[1, 2, 5],
[1, 7, 4],
[1, 3, 6],
[2, 3, 4],
[2, 6, 7],
[3, 5, 7],
[4, 5, 6]]
m = 9
n = 3
[[1, 8, 4],
[1, 3, 2],
[1, 9, 6],
[1, 7, 5],
[2, 4, 7],
[2, 5, 6],
[2, 8, 9],
[3, 4, 6],
[3, 5, 8],
[3, 7, 9],
[4, 5, 9],
[6, 7, 8]]
m = 13
n = 4
[[1, 11, 6, 13],
[1, 5, 8, 12],
[1, 3, 10, 9],
[1, 4, 7, 2],
[2, 3, 5, 11],
[2, 6, 8, 9],
[2, 10, 12, 13],
[3, 4, 6, 12],
[3, 7, 8, 13],
[4, 5, 9, 13],
[4, 8, 10, 11],
[5, 6, 7, 10],
[7, 9, 11, 12]]
While this does provide results for some combinations of m and n, it still does not generalize for all possible combinations of m and n. However, as Dillon Davis has said, there is no known generalized solution yet.
Your problem is exactly that of the construction of Steiner Systems. Unfortunately, there is not a general algorithm for constructing S(2, k, n) for arbitrary k and n. For k=3, the problem has been extensively studied as "Steiner Triple Systems" (STS) and k=4 "Steiner Quadruple Systems" (SQS).
Other than those two fixed k, there's also an approach based in projective geometry that produces a steiner system for k=p^q and n=k^2+k+1, where p is prime. However, this approach is extremely limited.
I also perused the literature for heuristics on constructing steiner systems, but found surprisingly little. Seems that people really just use a tree search with decent pruning rules.
I will also point out that your calculation for the number of groups is correct when a solution exists, but don't not exclude all systems without solutions. The two major rules for admissibility of steiner systems are as follows:
If there exists an S(t, k, v) then there exists an S(t-1, k-1, v-1)
If there exists an S(t, k, v) then C(k, t) divides C(v, t)
Where S(t, k, v) denotes a steiner system of v base elements in groups of k elements where each subset of t elements occurs in exact one group, and C(n, m) is "n choose m".
These two theorems correspond to your 2nd and 3rd conditionals, but these conditions are not sufficient- even if your values satisfy these constraints, there may not be a valid solution to the system. I'm not aware of a better test, but you should still be aware that a solution simply may not exist despite passing these tests.