生成非连续组合

Question

我正在尝试创建一个生成器(迭代器支持执行下一个,也许在python中使用yield),它给出了来自{1,2,... n}(n和r是参数)的r个元素的所有组合,以便在选中的r元素,没有两个是连续的.

例如,对于r = 2且n = 4

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

我可以生成所有组合(作为迭代器)并过滤那些不符合标准的组合,但我们将做不必要的工作.

是否存在一些生成算法,即nextO(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

这个很有趣！这个怎么样：

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为结果集一部分的条件：

1. 元组中的任何元素至少与前一个元素加 2 一样大。 ( c[x] >= c[x-1] + 2)
2. 所有元素都小于或等于n。因为 1. 说最后一个元素小于或等于 就足够了n。( c[r-1] <= n)

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

As Blckknght is pointing out, even the smallest possible tuple may be to large to satisfy condition 2.

The function above contains two while loops:

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

  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）迭代结果元组的项目。最初，我们想要向最后一项添加 1 (a = 1)，但是当单步执行元组时，我们实际上想要将最后一项替换为前一项的值 plus 2*x，其中x是两项之间的距离。(a += 2, 组合[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，所以这些都不重要。