python - 生成非连续组合

Question

我正在尝试创建一个生成器(支持执行 next 的迭代器，可能在 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 的答案。

以下是一些原因

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

这是可以预见的。我们确切地知道生成组合的顺序(词典)。

这两个属性使生成并行化(在可预测点和委托(delegate)处拆分)变得容易，并且具有容错性(如果 CPU/机器出现故障，可以从最后生成的组合中提取)!

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

Answer 1

这很好玩!这个怎么样:

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)]

让我尝试解释这是如何工作的。

元组的条件 c与 r要成为结果集一部分的元素:

元组的任何元素至少与前一个元素加 2 一样大。
( c[x] >= c[x-1] + 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，我们将增加前面的元素并相应地调整最后一个元素。这有点像以 10 为基数计算整数:“如果最后一位数字大于 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, 组合[p] + a)

最后，我们找到了要递增的项，并用从递增项开始的序列填充元组的其余部分，步长为 2:

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

就是这样。当我第一次想到它时，它似乎很容易，但是整个函数中的所有算术都为逐一错误提供了一个很好的地方，并且描述它比应该的更难。当我添加那个内循环时，我应该知道我遇到了麻烦:)

在性能上..

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

另一方面，我很确定如果这是 C，我的解决方案会比大多数解决方案执行得更好。内部 while 循环是 O(log r) 并且它就地改变结果和相同的 O(log r) )。它不消耗额外的堆栈帧，并且除了结果和两个变量之外不消耗任何内存。但显然这不是 C，所以这些都不重要。