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

我希望能够获取一系列数字并返回一个包含三元组且不重复的列表。 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),]

or

[(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)

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

让我们再试一次。

一些观察。

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

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

1. 生成 2 个序列整数列表，一个用于选择，另一个用于种子。
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. 用您的范围填充列表。 [0,1,2,3]
2. 创建另一个列表。 [0,1,2,3]
3. 随机排列列表。 [1,0,2,3]
4. 随机播放，直到找到适合的... [1, 2, 3, 0]
5. 对第三个元素重复上述操作。

通过此过程，虽然计算机可以verify解决方案非常快，它不能generate解决方案非常快。然而，它只是生成真正随机答案的两种方法之一。

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

from itertools import permutations

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

Then.

解决方案2：随机验证

1. 选择一个以 0 开头的三元组。
2. 随机弹出一个不以 0 开头的三元组。
3. 验证随机选取的三元组是否是中间解决方案。
4. 如果没有，则弹出另一个三元组。
5. 如果是，则附加三元组，并且重新填充三元组队列.
6. 重复n次。 # 或者直到你耗尽队列，此时repeat n次自然就变为TRUE

下一个三元组的解决方案在数学上保证位于解决方案集中，因此如果您只是让它自行耗尽，那么应该会出现一个随机解决方案。这种方法的问题在于，不能保证每个possible结果有一个equal可能性。

解决方案3：迭代验证

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

编写一个函数verify列出要产生的候选解决方案every解决方案，然后从该列表中随机弹出一个解决方案。

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 需要一天。获得真正的随机解决方案的唯一方法就是这样做。

Edited:无均等分布的随机解：

以下是我在尝试解决此问题时编写的代码，是解决方案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