生成无重复无剩余的m元素n大小组唯一组合算法实现求助

编辑记录 #

• 2024年1月5日：补充预期输出说明
• 2024年1月11日：进一步补充预期输出说明
• 2024年1月16日：添加最终更新代码，尝试按Dillon Davis的方案剪枝结果，因需深入研究Steiner Systems，已采纳其方案
• 2024年1月17日：提供已求解Steiner Systems数据库资源

技术问询 #

我需要实现一款算法，用于生成m个元素的所有唯一n大小分组，需满足无重复元素对、无剩余元素的要求——即每个元素与其他所有元素恰好配对一次。

重复指任意两个及以上元素曾被分组在一起，例如[1, 2, 3]与[1, 2, 4]存在重复元素对[1, 2]；无剩余指所有分组大小均为n。

可通过以下函数计算m和n对应的有效组合数，仅部分m、n值满足条件：

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)

例如iterations(9,3)返回12，iterations(6,3)返回False，因6个元素无法通过3大小分组实现所有元素仅配对一次。

当前我实现的代码在(3, 2)、(5, 2)、(7, 3)等组合下有效，但在(9, 3)时会出现路径阻塞：生成部分分组后，后续分组会出现重复元素对，最终触发“list index out of range”错误。

我尝试添加剪枝逻辑更新代码，虽能支持部分组合，但无法覆盖所有有效m、n值，现寻求通用解决方案。

初始实现代码 #

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)

更新后代码 #

首先，更新id类的update_comparisons(self, id_list, mode = 'add')方法，并将iterations(m,n)重命名为valid_comobos(m,n)：

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

其次，添加try:和except:语句剪枝无效结果：

# 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')

部分组合输出示例 #

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]]

更新后的代码可支持部分m、n组合，但无法覆盖所有有效情况，目前尚无通用解决方案。

内容的提问来源于stack exchange，提问作者Carl Lennartson