python - 从两个列表中创建所有可能的项目组合的元组，而不在元组中复制项目

Question

我希望能够获取一系列数字并返回一个包含没有重复的三元组的列表。 x 的每个元素都应该在三元组的每个位置出现一次。目标是获得如下内容:

get_combinations_without_duplicates(3) = [(0, 1, 2), (1, 2, 0), (2, 0, 1)]

对于 range(3) 这只是一个列表旋转，但对于更高的范围，有更多可能的组合。我希望能够随机生成满足这些约束的三元组列表。

假设我们首先为 n=4 的情况指定每个三元组的第一个元素:

[(0,), (1,), (2,), (3,)]

第一个三元组的第二个元素可以是 0 以外的任何元素。一旦选择了其中一个，就会限制下一个三元组的选项，依此类推。目标是让函数接受一个数字并以这种方式创建三元组，但并不总是创建相同的三元组。也就是说，最终结果可能是轮换:

[(0, 1, 2), (1, 2, 3), (2, 3, 0), (3, 0, 1),]

或

[(0, 2, 3), (1, 3, 0), (2, 0, 1), (3, 1, 2)]

下面是这个函数的一个实现:

def get_combinations_without_duplicates(n):
    output = []
    second = range(n)
     third = range(n)
for i in range(n):
    triple = [i]
    #Get the second value of the triple, but make sure that it isn't a 
    #duplicate of the first value
    #in the triple or any value that has appeared in the second position of any triple
    choices_for_second = [number for number in second if number not in triple]
    #Randomly select a number from the allowed possibilities
    n_second = random.choice(choices_for_second) 
    #Append it to the triple
    triple.append(n_second)
    #Remove that value from second so that it won't be chosen for other triples
    second = [number for number in second if number != n_second]
    #Do the same for the third value
    choices_for_third = [number for number in third if number not in triple]
    n_third = random.choice(choices_for_third)
    triple.append(n_third)
    third = [number for number in third if number != n_third]
    output.append(tuple(triple))
return output

正如下面所指出的，这个过程有时会随机选择不起作用的组合。如果您执行以下操作，则可以处理:

def keep_trying(n):
    try:
        return get_combinations_without_duplicates(n)
    except IndexError:
        return keep_trying(n)

但是，我想知道是否有更好的方法来做到这一点。

Answer 1

让我们再试一次。

一些观察。

在元组的排序数组中，第一个值将始终为零。

数组的长度将始终与数组中存在的元组数一样长。

您希望这些随机生成。

元组按“排序”顺序生成。

基于这些规范，我们可以提出一个程序方法；

生成 2 个序列整数列表，一个用于选择，另一个用于种子。

对于种子列表中的每个数字，[0, 1, 2, 3] , 随机附加和删除元素中不存在的数字。 [01, 13, 20, 32]

生成另一个序列整数列表，然后重复。 [012, 130, 203, 321]

但是，这行不通。对于某些迭代，它会将自己退回到角落并且无法生成数字。例如， [01, 13, 20, 32].. appending [3, 0, 1... crap, I'm stuck.
解决此问题的唯一方法是对整行进行真正的洗牌，然后重新洗牌直到适合为止。这可能需要相当长的时间，而且随着时间的推移，只会变得更加痛苦。

所以，从程序上来说:

解决方案1:随机生成

用您的范围填充列表。 [0, 1, 2, 3]

创建另一个列表。 [0, 1, 2, 3]

洗牌列表。 [1, 0, 2, 3]

随机播放，直到找到一个适合... [1, 2, 3, 0]

重复第三个元素。

通过此过程，虽然计算机可以非常快速地验证解决方案，但它无法非常快速地生成解决方案。然而，这只是生成真正随机答案的两种方法之一。

因此，最快的保证方法将使用验证程序，而不是生成程序。首先，生成所有可能的排列。

from itertools import permutations

n = 4
candidates = [i for i in permutations(xrange(n),3)]

然后。

解决方案2:随机验证

选择一个以 0 开头的三元组。

随机弹出一个不以 0 开头的三元组。

验证随机选择的三元组是否是中间解决方案。

如果没有，请弹出另一个三元组。

如果是，追加三元组，并重新填充三元组队列。

重复n次。 # 或者直到排完队列，此时重复 n 次自然变为 TRUE

下一个三元组的解在数学上保证在解集中，所以如果你让它自己耗尽，随机解应该出现。这种方法的问题在于不能保证每个可能的结果都有相等的概率。

解决方案 3:迭代验证

对于等概率结果，摆脱随机化，并生成每个可能的 3 元组组合，n 列长——并验证每个候选解决方案。

编写一个函数来验证候选解决方案列表以生成每个解决方案，然后从该列表中随机弹出一个解决方案。

from itertools import combinations

results = [verify(i) for i in combinations(candidates, n)]
# this is 10626 calls to verify for n=4, 5 million for n=5 
# this is not an acceptable solution.  

解决方案 1 或 3 都不是非常快，O(n**2)，但是根据您的标准，如果您想要一个真正随机的解决方案，这可能是最快的。解决方案 2 将保证是这三个中最快的，通常显着击败 1 或 3，解决方案 3 的结果最稳定。您选择这些方法中的哪一种取决于您想对输出做什么。

之后:

最终，代码的速度将取决于您希望代码的随机程度。吐出满足您要求的元组系列的第一个(也是第一个)实例的算法可以非常快地运行，因为它只是按顺序攻击排列一次，并且它将在 O(n) 时间内运行.但是，它不会随机做任何事情......

另外，这里有一些用于 verify(i) 的快速代码。它基于观察到两个元组在同一索引中可能不具有相同的数字。

def verify(t):
    """ Verifies that a set of tuples satisfies the combinations without duplicates condition. """
    zipt = zip(*t)
    return all([len(i) == len(set(i)) for i in zipt])

n = 4 完整解决方案集

((0, 1, 2), (1, 0, 3), (2, 3, 0), (3, 2, 1))
((0, 1, 2), (1, 0, 3), (2, 3, 1), (3, 2, 0))
((0, 1, 2), (1, 2, 3), (2, 3, 0), (3, 0, 1))
((0, 1, 2), (1, 3, 0), (2, 0, 3), (3, 2, 1))
((0, 1, 3), (1, 0, 2), (2, 3, 0), (3, 2, 1))
((0, 1, 3), (1, 0, 2), (2, 3, 1), (3, 2, 0))
((0, 1, 3), (1, 2, 0), (2, 3, 1), (3, 0, 2))
((0, 1, 3), (1, 3, 2), (2, 0, 1), (3, 2, 0))
((0, 2, 1), (1, 0, 3), (2, 3, 0), (3, 1, 2))
((0, 2, 1), (1, 3, 0), (2, 0, 3), (3, 1, 2))
((0, 2, 1), (1, 3, 0), (2, 1, 3), (3, 0, 2))
((0, 2, 1), (1, 3, 2), (2, 0, 3), (3, 1, 0))
((0, 2, 3), (1, 0, 2), (2, 3, 1), (3, 1, 0))
((0, 2, 3), (1, 3, 0), (2, 0, 1), (3, 1, 2))
((0, 2, 3), (1, 3, 2), (2, 0, 1), (3, 1, 0))
((0, 2, 3), (1, 3, 2), (2, 1, 0), (3, 0, 1))
((0, 3, 1), (1, 0, 2), (2, 1, 3), (3, 2, 0))
((0, 3, 1), (1, 2, 0), (2, 0, 3), (3, 1, 2))
((0, 3, 1), (1, 2, 0), (2, 1, 3), (3, 0, 2))
((0, 3, 1), (1, 2, 3), (2, 1, 0), (3, 0, 2))
((0, 3, 2), (1, 0, 3), (2, 1, 0), (3, 2, 1))
((0, 3, 2), (1, 2, 0), (2, 1, 3), (3, 0, 1))
((0, 3, 2), (1, 2, 3), (2, 0, 1), (3, 1, 0))
((0, 3, 2), (1, 2, 3), (2, 1, 0), (3, 0, 1))

n = 5 有 552 个唯一解。这是前20个。

((0, 1, 2), (1, 0, 3), (2, 3, 4), (3, 4, 0), (4, 2, 1))
((0, 1, 2), (1, 0, 3), (2, 3, 4), (3, 4, 1), (4, 2, 0))
((0, 1, 2), (1, 0, 3), (2, 4, 0), (3, 2, 4), (4, 3, 1))
((0, 1, 2), (1, 0, 3), (2, 4, 1), (3, 2, 4), (4, 3, 0))
((0, 1, 2), (1, 0, 4), (2, 3, 0), (3, 4, 1), (4, 2, 3))
((0, 1, 2), (1, 0, 4), (2, 3, 1), (3, 4, 0), (4, 2, 3))
((0, 1, 2), (1, 0, 4), (2, 4, 3), (3, 2, 0), (4, 3, 1))
((0, 1, 2), (1, 0, 4), (2, 4, 3), (3, 2, 1), (4, 3, 0))
((0, 1, 2), (1, 2, 0), (2, 3, 4), (3, 4, 1), (4, 0, 3))
((0, 1, 2), (1, 2, 0), (2, 4, 3), (3, 0, 4), (4, 3, 1))
((0, 1, 2), (1, 2, 3), (2, 0, 4), (3, 4, 0), (4, 3, 1))
((0, 1, 2), (1, 2, 3), (2, 0, 4), (3, 4, 1), (4, 3, 0))
((0, 1, 2), (1, 2, 3), (2, 3, 4), (3, 4, 0), (4, 0, 1))
((0, 1, 2), (1, 2, 3), (2, 4, 0), (3, 0, 4), (4, 3, 1))
((0, 1, 2), (1, 2, 3), (2, 4, 1), (3, 0, 4), (4, 3, 0))
((0, 1, 2), (1, 2, 4), (2, 0, 3), (3, 4, 0), (4, 3, 1))
((0, 1, 2), (1, 2, 4), (2, 0, 3), (3, 4, 1), (4, 3, 0))
((0, 1, 2), (1, 2, 4), (2, 3, 0), (3, 4, 1), (4, 0, 3))
((0, 1, 2), (1, 2, 4), (2, 3, 1), (3, 4, 0), (4, 0, 3))
((0, 1, 2), (1, 2, 4), (2, 4, 3), (3, 0, 1), (4, 3, 0))

因此，您可以生成这样的解决方案，但这需要时间。如果您打算使用它，我将按原样缓存生成的解决方案，然后在您需要它们时随机从它们中提取任何数量 n。顺便说一下，n=5 用了不到一分钟的时间来完成，蛮力。由于解决方案是 O(n**2)，我预计 n=6 需要一个多小时，n=7 需要一天。您可以通过这种方式返回真正的随机解决方案的唯一方法。

已编辑:不均匀分布的随机解:

以下是我为解决这个问题而写的代码，一个 的实现解决方案 2 .我想我会发布它，因为它是一个部分的、非等分分布的解决方案，并且在有足够的时间保证的情况下生成所有可能的解决方案。

def seeder(n):
    """ Randomly generates the first element in a solution. """
    seed = [0]
    a = range(1, n)
    for i in range(1, 3):
        seed.append(a.pop(random.randint(0,len(a)-1)))
    return [seed]

def extend_seed(seed, n):
    """ Semi-Randomly generates the next element in a solution. """
    next_seed = [seed[-1][0] + 1]
    candidates = range(0, n)
    for i in range(1, 3):
        c = candidates[:]
        for s in next_seed:
            c.remove(s)
        for s in seed:
            try:
                c.remove(s[i])
            except ValueError:
                pass
        next_seed.append(c.pop(random.randint(0,len(c)-1)))
    seed.append(next_seed)
    return seed

def combo(n):
    """ Extends seed until exhausted. 
    Some random generations return results shorter than n. """
    seed = seeder(n)
    while True:
        try:
            extend_seed(seed, n)
        except (ValueError, IndexError):
            return seed

def combos(n):
    """ Ensures that the final return is of length n. """
    while True:
        result = combo(n)
        if len(result) == n:
            return result