为组大小为 m 的 n 个对象生成没有重复或余数的唯一组合？

Question

我正在尝试创建一种算法，可以生成组大小为 n 的 m 对象的所有唯一组合，而无需重复或余数。

重复是指之前至少有两个或多个数字已经组合在一起。 例如，

[1, 2, 3]

和

[1, 2, 4]

具有重复的

[1, 2]

对。

没有余数意味着所有大小为 n 的组必须具有相同的大小。

以下函数接受输入

(m, n)

，如果

m

和 n 不兼容，则给出 False 的输出。如果 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)

这部分代码工作正常。我遇到的问题是实现算法来生成独特的组合。

这是我用于生成独特组合的代码块：

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

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)

# Checking if m and n are valid values
m = 9
n = 3

if iterations(m, n):
    iter = iterations(m, n)
    print(iter)

#Creating list of ids
ids_master = get_ids(m)
ids = ids_master.copy()

comparison_names = []
ids = ids_master.copy()
comparisons = []

for i in range(iter):
    temp = []
    pos = 0
    while len(temp) < n:
        id_a = ids[pos]

        # Checking if the id within temp have already been compared or is a duplicate
        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 len(id_a.comparisons) == m - 1:
            counter += 1

        # If id_a has passed the checks, append it to temp_list
        if counter == 0:
            temp.append(id_a)
        pos += 1
    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)

# Checking if all ids have been compared
for id in ids_master:
    print(f'ID: {id.name} \n Comparisons: {id.comparisons}')

上述代码适用于 (3, 2)、(5, 2) 和 (7, 3) 的值。然而，(9, 3) 会带来复杂性。

代码将在遇到障碍之前生成以下比较。

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

在这种情况下，下一个组合将是

[2, 8, 9]

。但这不起作用，因为 [8, 9] 已经在

[1, 8, 9]

中进行了比较。然后，代码不断迭代位置，直到用完要在列表中检查的项目并给出错误“列表索引超出范围”。

我需要一种算法来预测这些错误。例如，如果代码生成

[2, 4, 9]

，则其余组合将可能正常工作。我确信有一种方法可以实现这一点，但我不确定如何继续。

提前致谢！

Answer 1

我无法完全按照您代码中的逻辑来查看您做错了什么，但我想出了这个似乎可以满足您的要求：

import itertools

n=3
m=9

# generate a list of all possible combinations for m and n
combos = list(itertools.combinations(range(m), n))

# track a list of valid combinations; a valid combination has
# elements that don't have more than 1 value in common with other
# valid combinations
valid = []

for combo in combos:
    # check each possible combination against every valid combination
    for v in valid:
        if len(set(v) & set(combo)) > 1:
            break  # this combo has more than 1 element in common
    else:
        valid.append(combo)

# (m,n) is valid if all members of m are represented in the list of
# valid combinations
if len(set(itertools.chain(*valid))) == m:
    print(f'({m}, {n}) is valid')
    print(valid)

(9, 3) is valid
[(0, 1, 2), (0, 3, 4), (0, 5, 6), (0, 7, 8), (1, 3, 5), (1, 4, 6), (2, 3, 6), (2, 4, 5)]