N 选择 r 个可能性作为递增的二进制数

我正在寻找一个输入 (n,r) 并输出我们可以从 n 个对象的字符串中选取 r 个对象的所有方法的函数。此外，我希望这个列表是一个递增的二进制序列。

例如：

(5,2)

将输出：[00011,00101,00110,01001,01010,01100,10001,10010 ,10100,11000]

我尝试通过考虑最右边的 1 并检查它是否可以“向左移动而不碰到另一个 1”来做到这一点。如果不能，那么我会转到下一个并检查同样的事情。如果任何 1 可以“向左移动”，则其右侧的每个 1 都会被“重置”。

尽管我的代码尚未尝试此方法。

def combinations(n, r):
  """
  生成从 n 个对象中选取 r 个对象的所有组合，表示为递增的二进制序列。

  Args:
    n: 对象的数量。
    r: 要选择的元素数量。

  Yields:
    表示组合的二进制序列。
  """

  c = [0] * (n - r) + [1] * r
  yield ''.join(map(str, c))

  while True:
    i = n - 1
    while c[i] == 1 and c[i - 1] == 0:
      i -= 1
    if i == 0:
      break
    c[i - 1], c[i] = c[i], c[i - 1]
    c[i + 1:] = sorted(c[i + 1:])
    yield ''.join(map(str, c))


# 示例用法：
for combo in combinations(5, 2):
  print(combo)

此代码通过将问题简化为生成 n 位长度的二进制字符串，其中恰好有 r 个 1 来工作，代表从 n 个元素中进行的 r 个选择。让我们分解一下代码是如何工作的：

1. 初始化：
2. 它首先创建一个列表 c ，该列表表示初始组合，其中 r 个 1 位于右侧， (n-r) 个 0 位于左侧。这种初始化确保我们从最小的词典组合开始。
3. 生成组合：
4. 它使用 yield 语句，使该函数成为生成器，一次生成一个组合，而无需将所有组合存储在内存中。
5. 查找下一个组合：
6. 该代码迭代当前组合 c ，从右到左（从索引 n-1 开始）。
7. 它寻找一个可以向左移动的 1（表示为 c[i] == 1 和 c[i-1] == 0 的模式）。
8. 当它找到一个可以移动的 1 时，它会将其与其左边的 0 交换。
9. 为了确保我们生成词典顺序，它会对移动的 1 右侧的所有 1 进行排序（ c[i+1:] = sorted(c[i+1:]) ）。这样可以确保新组合始终大于前一个组合。
10. 终止条件：
11. 如果没有 1 可以向左移动（即，我们到达了列表的开头，并且 i == 0 ），这意味着我们已经生成了所有可能的组合，并且循环中断。

此算法可以有效地生成所有组合，并确保它们以递增的二进制顺序生成。

对于输入 (5, 2)，的输出将是：

00011
00101
00110
01001
01010
01100
10001
10010
10100
11000

这与期望的输出完全一致。