我希望能够获取一个数字范围,并返回一个包含三元组且没有重复项的列表。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)
但是,我想知道是否有更好的方法来做这件事。
让我们再试一次。
一些观察。
根据这些规范,我们可以提出一个程序方法
[0, 1, 2, 3]
,随机追加并删除元素中不存在的数字。[01, 13, 20, 32]
[012, 130, 203, 321]
但是,这不起作用。在某些迭代中,它会返回到一个角落,无法生成一个数字。例如,
[01, 13, 20, 32].. appending [3, 0, 1... crap, I'm stuck.
解决这个问题的唯一方法是对整行进行true洗牌,然后重新洗牌直到合适为止。这可能需要相当长的时间,而且只会随着时间的延长而变得更加痛苦。
所以,从程序上讲:
解决方案1:随机生成
使用此过程,计算机可以很快验证解,但不能很快生成解。然而,这仅仅是产生真正随机答案的两种方法之一。
因此,最快的保证方法将使用验证过程,而不是生成过程。首先,生成所有可能的排列。
那么。
解决方案2:随机验证
下一个三元组的解在数学上保证在解集中,所以如果你让它自己耗尽,就会出现一个随机解。这种方法的问题是不能保证每个可能的结果都有相等的概率。
解决方案3:迭代验证
对于等概率结果,去掉随机化,生成每一个可能的三元组组合,n个长列表——并验证每个候选解决方案。
在候选解决方案列表上编写一个函数来验证每个解决方案,然后从该列表中随机弹出一个解决方案。
解决方案1或3都不是很快的,O(n**2),但是考虑到你的标准,如果你想要一个真正随机的解决方案,这可能是最快的。解决方案2将保证是这三个最快的,往往多次显著击败1或3,解决方案3有最稳定的结果。您选择的这些方法中的哪一种取决于您希望对输出执行什么操作。
之后:
最终,代码的速度将完全取决于您希望代码的随机性。吐出满足您的需求的元组序列的第一个(并且只有第一个)实例的算法可以非常快地运行,因为它只是按顺序攻击排列,一次,它将在O(n)时间内运行。但是,它不会随机做任何事情。。。
另外,这里有一些快速验证代码(i)。这是基于两个元组在同一索引中的数目可能不相同的观察结果。
n=4全解集
n=5有552个唯一的解决方案。这是前20个。
因此,您可以生成这样的解决方案,但这需要时间。如果你打算利用这个,我会缓存按原样生成的解决方案,然后在你需要时随机从它们中提取任意数量的n。顺便说一下,n=5需要不到一分钟的时间来完成,蛮力。由于解是O(n**2),我预计n=6需要一个小时,n=7需要一天。唯一能返回真正随机解的方法就是这样做。
编辑:不均匀分布随机解:
下面是我在试图解决这个问题时编写的代码,这是解决方案2的一个实现。我想我会把它贴出来,因为它是一个部分的,不相等的分布解,生成每一个可能的解,有保证,有足够的时间。
实际上,您需要一个Latin square,一个n x n的数字网格,其中每一行和每一列只包含一个数字,除了您只关心每一行中的前三个数字(拉丁矩形)。
更新:
我已经删除了无效的代码样本,因为生成具有相同概率的随机拉丁方是非常重要的,正如前面讨论的in a question on math.stackexchange.com。
SAGE project实现了该问题中提到的算法,因此您可以查看代码以获得灵感。
或者,如果您真的想了解详细信息,请查看this paper以了解生成随机拉丁矩形的具体情况。
实际上,itertools已经为您解决了这个问题。
输出
相关问题 更多 >
编程相关推荐