我用整数中的两位表示一个元素。 IE。 3345512
代表四个元素 [3,34,55,12]
。接下来,我反复将整数加一以获得另一个元素序列。当生成这样的序列时,我得到了相同序列的排列,即 3341255 = [3,34,12,55]
,在我的例子中它等同于数字 3345512 = [ 3,34,55,12]
。所以我想避免排列我已经遇到的序列。我不想存储数字,因为它们变得非常大(10^30
和更多)。我尝试使用布隆过滤器,但它无法处理元素的数量。是否有一个简单的解决方案来生成没有排列的序列?
[编辑] 这是一个小的 python 脚本,它应该可以工作。为了更好地理解,我使用单个数字 if s[idx] == 9:
而不是 if s[idx] == 99:
如果您有更简单的解决方案,我会接受它作为答案。
import time
s = [1]
while True:
idx = 0
while not idx+1 == len(s) and not s[idx] < s[idx+1]:
s[idx] = 1
idx += 1
if s[idx] == 9:
s[idx] = 1
s.append(1)
else:
s[idx] += 1
print repr(s)
time.sleep(0.7)
最佳答案
您要的是组合而不是排列。看起来您正在尝试从 100 项列表中获取 4 项的唯一组合。也就是说,您的可能值为 00
到 99
。
您可以使用嵌套循环生成所有组合,如下所示:
for (i = 0 to 96)
for (j = i + 1 to 97)
for (k = j + 1 to 98)
for (l = k + 1 to 99)
write i, j, k, l
这保证您不会得到相同的组合。
您还会注意到在生成的组合中:
i < j < k < l
如果你让你的序列总是满足不等式,那么你就不会得到重复的组合。
因此永远不会生成您的示例 3345512
。它将是 3123455
。
鉴于此,当您从 3123499
递增时,您不会转到 3123500
,而是转到 3123536
。基本上,如果你溢出一个位置,你增加下一个位置,原始位置变成(下一个位置+ 1)。所以 3999999
递增到 4050607
。
显然,您不能使用简单的整数增量来完成此操作。我建议使用 4 字节的值和一点逻辑。
这是另一种方法。
假设您的字母表只有 4 个字符,[0, 1, 2, 3]
。总共有 16 种可能的独特组合。您想要两个项目的独特组合。
现在,考虑一个可以容纳 0 到 15 值的 4 位数字。您可以将该数字映射到唯一组合,以便数字 3(0011 二进制)对应于组合 0、1。也就是说,位设置 0 并设置位 1。应该清楚的是,设置了 2 位的数字对应于唯一的 2 字符组合。对于 4 项字母表中的 2 种组合,我们有:
0, 1 (0011)
0, 2 (0101)
0, 3 (1001)
1, 2 (0110)
1, 3 (1010)
2, 3 (1100)
有了这个,您可以递增一个整数,查看它是否设置了两个位,然后将设置位转换为字母表中的字符。
您可以通过从一组 100 个字符中选择 4 个组合来做完全相同的事情。使用 100 位数有点困难,但并非不可能。由于您只是递增,因此可以使用一对 64 位数字来完成。
确定设置了多少位是很简单的简单方法。 Bit Twiddling Hacks页面显示了几种更快的方法。
有几种方法可以解决这个问题,所有方法都可以参数化以从 n 项列表中选择唯一的 k 组合。
关于algorithm - 生成没有排列的序列,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20521612/