生成不连续组合

Question

我正在尝试创建一个生成器（就是一个可以用来逐个获取元素的工具，可能会用到Python中的yield），它可以从{1,2,...n}中生成所有的r个元素的组合（n和r是参数），而且在选中的r个元素中，不能有两个是连续的。

举个例子，当r = 2，n = 4时，

生成的组合是{1,3}, {1,4}, {2, 4}。

我可以生成所有的组合（作为一个迭代器），然后筛选出不符合条件的组合，但这样做会浪费很多不必要的工作。

有没有什么生成算法可以让next的时间复杂度是O(1)（如果不行，O(r)或O(n)也可以）。

返回的组合顺序并不重要（希望这能让算法达到O(1)的复杂度）。

注意：我标记了Python，但一个不依赖于语言的算法也会有帮助。

更新：

我找到了一种方法，可以将其映射到生成纯组合！网上搜索显示，对于组合，O(1)是可能的（虽然看起来有点复杂）。

这里是映射的方式。

假设我们有一个组合x_1, x_2, ... , x_r，满足x_1 + 1 < x_2, x_2 + 1 < x_3, ...

我们可以将其映射到y_1, y_2, ..., y_r，具体如下：

y_1 = x_1

y_2 = x_2 - 1

y_3 = x_3 - 2

...

y_r = x_r - (r-1)

这样我们就得到了y_1 < y_2 < y_3 ...，而不需要考虑非连续的限制！

这基本上就是从n-r+1中选择r个元素。因此，我只需要运行生成（n-r+1选择r）的组合。

对于我们的目的来说，在生成后使用这个映射就足够了。

选择svkcr的答案的原因

所有的答案都很好，但我选择了svkcr的答案。

以下是一些原因：

1. 它实际上是无状态的（或者说是“马尔可夫”的，更准确一点）。下一个排列可以从上一个生成。可以说它几乎是最优的：空间和时间复杂度都是O(r)。

2. 它是可预测的。我们确切知道组合生成的顺序（字典序）。

这两个特性使得生成过程容易并行化（在可预测的点进行拆分并委派），同时还具备容错能力（如果某个CPU或机器失败，可以从最后生成的组合继续进行）！

抱歉，之前没有提到并行化，因为在我写问题时没有想到这个，后来才有了这个想法。

Answer 1

如果有一种方法可以在 O(1) 的时间内生成所有组合，那你就可以通过生成和过滤来在 O(r) 的时间内完成。假设 itertools.combinations 的 next 方法是 O(1)，那么最多需要跳过 r-1 个值，所以最坏情况下是 r-1 次 O(1)，对吧？

为了避免混淆，我先跳到结论：我认为没有 O(1) 的 combinations 实现，因此这并不是 O(r)。但有没有什么可能是 O(r) 的呢？我不太确定。总之……

所以：

def nonconsecutive_combinations(p, r):
    def good(combo):
        return not any(combo[i]+1 == combo[i+1] for i in range(len(combo)-1))
    return filter(good, itertools.combinations(p, r))

r, n = 2, 4
print(list(nonconsecutive_combinations(range(1, n+1), r))

这段代码会打印：

[(1, 3), (1, 4), (2, 4)] 

---

itertools 的文档并没有保证 combinations 的 next 是 O(1)。但我觉得如果有可能的 O(1) 算法，他们肯定会用上，如果没有，你也找不到。

你可以查看 源代码，或者我们可以来测一下时间……不过既然要测，就测整个过程。

http://pastebin.com/ydk1TMbD 上有我的代码、thkang 的代码和一个测试驱动程序。它打印的时间是遍历整个序列的成本，除以序列的长度。

当 n 从 4 增加到 20，而 r 固定为 2 时，我们可以看到两者的时间都在减少。（记住，遍历整个序列的 总 时间当然是增加的。只是相对于 总长度 来说是次线性的）当 n 从 7 增加到 20，而 r 固定为 4 时，情况也是如此。

当 n 固定为 12，而 r 从 2 增加到 5 时，两者的时间是线性增加的，但对于 1 和 6 的时间比你预期的要高得多。

仔细想想，这很有道理——在 924 个值中，只有 6 个是有效的，对吧？这就是为什么随着 n 增加，next 的时间会减少。总时间在增加，但产生的值数量增加得更快。

所以，combinations 并没有 O(1) 的 next；它有的是一些复杂的东西。我的算法也没有 O(r) 的 next；同样是复杂的东西。我认为在整个迭代过程中，性能保证会比每次 next 更容易说明（然后如果你知道如何计算，就很容易除以值的数量）。

无论如何，我测试的两个算法的性能特征完全相同。（奇怪的是，把外层的 return 换成 yield from 让递归的那个更快，而过滤的那个更慢……不过这只是一个小常数因素，所以无所谓？）

Answer 2

这是我的一个递归生成器（如果选择了第 n 个项目，它会跳过第 n+1 个项目）：

def non_consecutive_combinator(rnge, r, prev=[]):
    if r == 0:
        yield prev

    else:
        for i, item in enumerate(rnge):
            for next_comb in non_consecutive_combinator(rnge[i+2:], r-1, prev+[item]):
                yield next_comb

print list(non_consecutive_combinator([1,2,3,4], 2))
#[[1, 3], [1, 4], [2, 4]]
print list(non_consecutive_combinator([1,2,3,4,5], 2))
#[[1, 3], [1, 4], [1, 5], [2, 4], [2, 5], [3, 5]]
print list(non_consecutive_combinator(range(1, 10), 3))
#[[1, 3, 5], [1, 3, 6], [1, 3, 7], [1, 3, 8], [1, 3, 9], [1, 4, 6], [1, 4, 7], [1, 4, 8], [1, 4, 9], [1, 5, 7], [1, 5, 8], [1, 5, 9], [1, 6, 8], [1, 6, 9], [1, 7, 9], [2, 4, 6], [2, 4, 7], [2, 4, 8], [2, 4, 9], [2, 5, 7], [2, 5, 8], [2, 5, 9], [2, 6, 8], [2, 6, 9], [2, 7, 9], [3, 5, 7], [3, 5, 8], [3, 5, 9], [3, 6, 8], [3, 6, 9], [3, 7, 9], [4, 6, 8], [4, 6, 9], [4, 7, 9], [5, 7, 9]]

关于效率：

这段代码不可能是 O(1) 的，因为每次迭代都要遍历堆栈并建立一个新的集合，这样就不能算是 O(1) 了。此外，递归生成器意味着你需要使用最大深度为 r 的堆栈来获取 r 项的组合。这意味着当 r 较小的时候，调用堆栈的成本可能比非递归生成要高。随着 n 和 r 的增大，递归生成器可能会比基于 itertools 的解决方案更有效。

我测试了这个问题中上传的两个代码：

from itertools import ifilter, combinations
import timeit

def filtered_combi(n, r):
    def good(combo):
        return not any(combo[i]+1 == combo[i+1] for i in range(len(combo)-1))
    return ifilter(good, combinations(range(1, n+1), r))

def non_consecutive_combinator(rnge, r, prev=[]):
    if r == 0:
        yield prev

    else:
        for i, item in enumerate(rnge):
            for next_comb in non_consecutive_combinator(rnge[i+2:], r-1, prev+[item]):
                yield next_comb

def wrapper(n, r):
    return non_consecutive_combinator(range(1, n+1), r)   

def consume(f, *args, **kwargs):
    deque(f(*args, **kwargs))

t = timeit.timeit(lambda : consume(wrapper, 30, 4), number=100)
f = timeit.timeit(lambda : consume(filtered_combi, 30, 4), number=100)

结果和更多结果（编辑）（在 Windows 7，Python 64位 2.7.3，Core i5 Ivy Bridge，8GB RAM）：

(n, r)  recursive   itertools
----------------------------------------
(30, 4) 1.6728046   4.0149797   100 times   17550 combinations
(20, 4) 2.6734657   7.0835997   1000 times  2380 combinations
(10, 4) 0.1253318   0.3157737   1000 times  35 combinations
(4, 2)  0.0091073   0.0120918   1000 times  3 combinations
(20, 5) 0.6275073   2.4236898   100 times   4368 combinations
(20, 6) 1.0542227   6.1903468   100 times   5005 combinations
(20, 7) 1.3339530   12.4065561  100 times   3432 combinations
(20, 8) 1.4118724   19.9793801  100 times   1287 combinations
(20, 9) 1.4116702   26.1977839  100 times   220 combinations

正如你所看到的，递归解决方案和 itertools.combination 基于解决方案之间的差距随着 n 的增加而变得更大。

实际上，这两种解决方案之间的差距很大程度上取决于 r - 更大的 r 意味着你需要丢弃更多从 itertools.combinations 生成的组合。例如，在 n=20, r=9 的情况下：我们从 167960（20C9）个组合中筛选并仅取 220 个组合。如果 n 和 r 较小，使用 itertools.combinations 可能会更快，因为在 r 较小的情况下，它更高效，并且不使用堆栈，正如我之前所解释的。（正如你所看到的，itertools 的优化非常好（如果用 for、if、while 和一堆生成器以及列表推导来编写你的逻辑，它不会像用 itertools 抽象出来的那样快），这也是人们喜欢 Python 的原因之一 - 你可以将代码提升到更高的层次，并获得回报。并不是很多语言能做到这一点。）

Answer 3

这真有趣！那我们来看看这个：

def nonconsecutive_combinations(r, n):
  # first combination, startng at 1, step-size 2
  combination = range(1, r*2, 2)
  # as long as all items are less than or equal to n
  while combination[r-1] <= n:
    yield tuple(combination)
    p = r-1 # pointer to the element we will increment
    a = 1   # number that will be added to the last element
    # find the rightmost element we can increment without
    # making the last element bigger than n
    while p > 0 and combination[p] + a > n:
      p -= 1
      a += 2
    # increment the item and
    # fill the tail of the list with increments of two
    combination[p:] = range(combination[p]+1, combination[p] + 2*(r-p), 2)

每次调用 next() 的时间复杂度应该是 O(r) .. 我在思考这个如何转化为自然数的时候得到了这个想法，但花了不少时间才把细节搞清楚。

> list(nonconsecutive_combinations(2, 4))
[(1, 3), (1, 4), (2, 4)]
> list(nonconsecutive_combinations(3, 6))
[(1, 3, 5), (1, 3, 6), (1, 4, 6), (2, 4, 6)]

让我试着解释一下这个是怎么工作的。

一个包含 r 个元素的元组 c 要成为结果集的一部分，需要满足以下条件：

1. 元组中的任何元素都必须至少比前一个元素大 2。 (c[x] >= c[x-1] + 2)
2. 所有元素都必须小于或等于 n。 根据第 1 条，只需要说 最后一个元素 小于或等于 n 就可以了。 (c[r-1] <= n)

可能成为结果集的最小元组是 (1, 3, 5, ..., 2*r-1)。当我说一个元组比另一个“更小”时，我是指字典序。

正如 Blckknght 指出的，即使是最小的元组也可能太大，无法满足条件 2。

上面的函数包含两个 while 循环：

• 外层循环遍历结果，假设它们是按字典序排列并满足条件一。一旦当前元组违反了条件二，我们就知道结果集已经遍历完了，可以结束了：

  combination = range(1, r*2, 2)
  while combination[r-1] <= n:
  

  第一行根据条件一初始化结果元组为第一个可能的结果。第二行直接对应条件二。

• 内层循环找到下一个满足条件一的可能元组。

  yield tuple(combination)
  

  由于 while 条件 (2) 为真，并且我们确保结果满足条件一，所以我们可以返回当前的结果元组。

  接下来，为了找到字典序中的下一个元组，我们会在最后一个元素上加“1”。

  # we don't actually do this:
  combination[r-1] += 1
  

  但是，这可能会过早地违反条件 2。所以，如果这个操作会违反条件 2，我们就增加前一个元素，并相应调整最后一个元素。这有点像十进制数的计数：“如果最后一位数字大于 9，就增加前一位数字，并把最后一位数字变为 0。”但我们不是加零，而是填充元组，以确保条件 1 成立。

  # if above does not work
  combination[r-2] += 1
  combination[r-1]  = combination[r-2] + 2
  

  问题是，第二行可能又会违反条件二。所以我们实际上是跟踪最后一个元素，这就是 a 的作用。同时我们用 p 变量来指代我们正在查看的当前元素的索引。

  p = r-1
  a = 1
  while p > 0 and combination[p] + a > n:
    p -= 1
    a += 2
  

  我们是从右到左（p = r-1, p -= 1）遍历结果元组的元素。最开始我们想在最后一个元素上加一（a = 1），但在遍历元组时，我们实际上想用前一个元素的值加上 2*x 来替换最后一个元素，其中 x 是这两个元素之间的距离。 (a += 2, combination[p] + a)

  最后，我们找到了想要增加的元素，并用一个从增加的元素开始、步长为 2 的序列填充剩下的元组：

  combination[p:] = range(combination[p]+1, combination[p] + 2*(r-p), 2)
  

  就这样。最开始我觉得这很简单，但函数中的所有算术运算都容易出错，描述起来比想象中要复杂。我应该知道当我加上那个内层循环时就麻烦了 :)

关于性能 ..

不幸的是，充满算术运算的 while 循环在 Python 中并不是最有效的写法。其他解决方案接受了这个现实，使用列表推导或过滤将重活交给 Python 的运行时来处理。在我看来，这才是 正确的做法。

另一方面，我很确定如果这是 C 语言，我的解决方案会比大多数表现得更好。内层 while 循环的时间复杂度是 O(log r)，它在原地修改结果，时间复杂度也是 O(log r)。它不消耗额外的栈帧，也不消耗除结果和两个变量之外的任何内存。但显然这不是 C，所以这些都不重要。