python包含多个元组的元组_python – 创建来自两个列表的项目的所有可能组合的元组,而不会在元组内重复项目...

让我们再试一次.

几点意见

>元组的排序数组中的第一个值始终为零.

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

>你希望这些随机生成.

>元组按照“排序”顺序生成.

根据这些规范,我们可以提出一个程序性的方法;

>生成2个串行整数列表,一个从中选择,另一个从中选择.

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

>生成另一个串行整数列表,并重复. [012,130,203,321]

但是,这不行.对于一些迭代,它将自己变成一个角落,不能生成一个数字.例如,[01,13,20,32] ..附加[3,0,1 …废话,我被卡住了.

解决这个问题的唯一方法是在整个行中进行真正的洗牌,并重新洗牌,直到适合.这可能需要相当多的时间,并且只会变得更痛苦,因为集合变得更长.

所以在程序上呢

解决方案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开头的三元组.

> Pop,随机,三进制,不以0开头.

>验证随机选择的三元组是否是中间解.

>如果没有,弹出另一个三元组.

>如果是,请附加三元组,然后REPOPULATE TRIPLET QUEUE.

>重复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)时间内运行.但是,它不会随便做任何事情

另外,这里有一些快速的验证码(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