非递归实现组合型枚举–python

主要思路

二进制枚举：可以使用n位二进制数表示n个数的不同选择状态，该位为1表示选中该数，为0表示不选。
Gosper’s Hack:利用位运算的特点，快速找到n位二进制数中的每一个有m个1的二进制数，避免挨个遍历和判断

参考文献

参考题解：https://www.acwing.com/solution/content/42544/
Gosper’s Hack：https://zhuanlan.zhihu.com/p/360512296

python 代码

# 非递归实现，利用二进制枚举思想和Gosper's Hack算法

def gosper_hack(n, m):
    if m==0:
        return
    res = []
    # 初始状态：最低位有m个1
    cur = (1<<m) - 1  # 如二进制数0111的值为2^3-1, 1左移m位表示2^m
    limit = 1<<n   # n位二进制数所能表示的最大数为2^n-1，只需要在这个范围内寻找符合条件的二进制数。
    while cur < limit:
        # 存入结果数组
        res.append(cur)
        # 直接寻找到下一个数
        lb = cur & -cur  # 得到最右侧的1：...0001000...
        r = cur + lb  # 加上lb使得cur中的1-bits，进1变0
        cur = ((r ^ cur) >> 2) // lb | r  # 在r中的最右侧补上剩下的1  设lb=2^y，除以2^y相当于右移y位
    # 逆序输出，才能满足字典序
    res.reverse()
    for ele in res:
        for i in range(n-1,-1,-1): # 依次判断每一位的位值
            if ele & (1<<i): # 利用位运算判断位置是否为1
                print(n-i, end=' ')
        print()

n, m = map(int, input().split())
gosper_hack(n, m) # 从n个数中选择m个数