生成不连续的组合

Question

我正在尝试创建一个生成器（iterator，它支持执行next，可能在python中使用yield），它提供来自{1,2，…n}（n和r是参数）的所有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和{}的组合

我们映射到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 choose r）的生成。

就我们的目的而言，在生成事物之后使用映射就足够了。

选择svkcr答案的原因

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

以下是一些原因

1. 它实际上是无状态的（或者更准确地说是“马尔科夫”）。下一个排列可以从上一个排列生成。它在某种程度上几乎是最优的：O（r）空间和时间。

2. 这是可以预测的。我们确切地知道组合产生的顺序（字典）。

这两个属性使得并行生成（在可预测的点上拆分和委托）变得很容易，并引入了容错（如果CPU/机器发生故障，可以从最后生成的组合中选取）！

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

Answer 1

如果有一种方法可以在O（1）中生成所有组合，那么您可以在O（r）中通过生成和过滤来实现这一点。假设itertools.combinations有一个O（1）next，那么最多可以跳过r-1值，所以最坏的情况是r-1乘以O（1），对吗？在

为了避免混淆，我不认为存在combinations的O（1）实现，因此这是而不是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))

打印：

^{pr2}$

---

itertools文档不能保证combinations有一个O（1）next。但在我看来，如果有一个可能的O（1）算法，他们会使用它，如果没有，你就找不到。在

你可以读the source code，或者我们可以计时……但是我们要做的是，让我们来计时。在

http://pastebin.com/ydk1TMbD有我的代码、thkang的代码和一个测试驱动程序。它的打印次数是迭代整个序列的成本除以序列的长度。在

当n从4到20，而r固定为2，我们可以看到两者的时间都在下降。（记住，迭代序列的总时间当然在增加。它只是the total length）中的次线性，n范围从7到20，r固定在4，这也是正确的。在

当n固定为12，而r的范围为2到5，两者的时间从2到5线性增加，但是1和6的时间远高于预期。在

仔细想想，924个值中只有6个是好值，对吧？这就是为什么每next的时间会随着n的上升而下降。总的时间在增加，但是产生的价值的数量增长得更快。在

所以，combinations没有O（1）next；它有一些复杂的东西。我的算法没有O（r）next；这也是一个复杂的问题。我认为在整个迭代过程中指定性能保证比按next要容易得多（如果知道如何计算，就很容易除以值的数目）。在

无论如何，我测试的两种算法的性能特征完全相同。（奇怪的是，将包装器return转换为yield from使得递归的更快，过滤的慢……但是无论如何，这是一个小的常量因子，谁在乎呢？）在

Answer 2

这很有趣！这个怎么样：

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）。。 我在考虑如何将其转换为自然数时产生了这个想法，但花了相当长的时间才把细节弄好。在

^{pr2}$

我来解释一下这是怎么回事

包含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循环：

• 外循环逐步遍历结果，并假设它们按字典顺序出现并满足条件1。一旦有问题的元组违反了条件2，我们就知道我们已经用尽了结果集并完成了：

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

  第一行根据条件1用第一个可能的结果初始化结果元组。第二行直接转换为条件二。

• 内部循环查找满足条件1的下一个可能的元组。在

  yield tuple(combination)
  

  由于while条件（2）为真，并且我们确保结果满足条件1，所以我们可以生成当前的结果元组。在

  下一步，为了找到字典形式的下一个元组，我们将在最后一个元素中添加“1”。在

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

  然而，这可能会过早打破条件2。因此，如果该操作将破坏条件2，我们将增加前面的元素并相应地调整最后一个元素。这有点像计算以10为基数的整数：“如果最后一个数字大于9，则增加前一个数字，并使最后一个数字为0。”但是，我们没有添加零，而是填充元组，以使条件1为真。在

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

  问题是，第二行可能会再次打破条件二。所以我们实际上要做的是，跟踪最后一个元素，这就是使用a所做的工作。我们还使用p变量来引用我们正在查看的index current元素。在

  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，其中{}是两个项之间的距离。（a+=2，组合[p]+a）

  我们从第2项的增量开始，找到了第2项的增量：

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

  就这样。当我第一次想到它的时候，它看起来是那么简单，但是整个函数中的所有算法都是一个很好的地方，因为只有一个错误，而且描述它比它应该是困难的。当我添加内部循环时，我应该知道我有麻烦了：）

性能方面

不幸的是，用Python编写充满算术的循环并不是最有效的方法。其他解决方案接受这种现实，并使用列表理解或过滤将繁重的工作推到Python运行时中。在我看来这是正确的做法。在

另一方面，我很确定如果这是C，我的解决方案会比大多数解决方案的性能好得多。内部while循环是O（logr），它会在适当的位置和相同的O（logr）中改变结果。除了结果和两个变量外，它不消耗额外的堆栈帧，也不消耗任何内存。但显然这不是C，所以不是这真的很重要。在

Answer 3

这是我的递归生成器（如果选择了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和{}，它可能比基于itertools的解决方案更有效。在

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

^{pr2}$

结果和更多结果（编辑）（在windows7上，python 64位2.7.3，带8gb ram的core i5 ivy bridge）：

(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.组合当n向上时，基于的解决方案会变得更宽。在

事实上，由于两个解决方案之间的差距很大程度上依赖于r-更大的r意味着你必须扔掉从itertools.combinations生成的更多组合。例如，在n=20, r=9的情况下：我们在167960（20C9）个组合中过滤并只获取220个组合。如果n和{}都很小，那么使用itertools.combinations会更快，因为它在更少的r下效率更高，而且不会像我解释的那样使用堆栈。（如您所见，itertools是非常优化的（如果用for、if、while和一堆生成器和列表理解编写逻辑，它不会像itertools抽象的那样快），这也是人们喜欢python的原因之一——你把代码带到了更高的层次，你就会得到回报。没有多少语言能做到这一点。在