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

Question

我希望能够获取一个数字范围，并返回一个包含三元组且没有重复项的列表。x的每个元素应该在三元组的每个位置出现一次。目标是得到如下信息：

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

对于范围（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

让我们再试一次。

一些观察。

1. 在元组的排序数组中，第一个值始终为零。
2. 数组的长度将始终与数组中存在的元组数相同。
3. 你希望这些都是随机生成的。
4. 元组按“排序”顺序生成。

根据这些规范，我们可以提出一个程序方法

1. 生成两个序列整数列表，一个从中挑选，另一个从中播种。
2. 对于种子列表中的每个数字，[0, 1, 2, 3]，随机追加并删除元素中不存在的数字。[01, 13, 20, 32]
3. 生成另一个序列整数列表，然后重复。[012, 130, 203, 321]

但是，这不起作用。在某些迭代中，它会返回到一个角落，无法生成一个数字。例如，[01, 13, 20, 32].. appending [3, 0, 1... crap, I'm stuck.

解决这个问题的唯一方法是对整行进行true洗牌，然后重新洗牌直到合适为止。这可能需要相当长的时间，而且只会随着时间的延长而变得更加痛苦。

所以，从程序上讲：

解决方案1：随机生成

1. 使用范围填充列表。[0，1，2，3]
2. 创建另一个列表。[0，1，2，3]
3. 重新排列列表。[1，0，2，3]
4. 洗牌直到你找到一个适合。。。[1，2，3，0]
5. 重复第三个元素。

使用此过程，计算机可以很快验证解，但不能很快生成解。然而，这仅仅是产生真正随机答案的两种方法之一。

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

from itertools import permutations

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

那么。

解决方案2：随机验证

1. 选择一个以0开头的三元组。
2. 随机弹出一个不以0开头的三元组。
3. 验证随机选取的三元组是否为中间溶液。
4. 如果不是的话，再来一个三胞胎。
5. 如果是，则追加三元组，然后重新填充三元组队列。
6. 重复n次。#或者直到你排完队，在这一点上重复n次自然成为事实

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

解决方案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）时间内运行。但是，它不会随机做任何事情。。。

另外，这里有一些快速验证代码（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