主页 / 问题 / 1566009
Accepted
Aycon
Asked:2024-02-12 21:38:08 +0800 CST2024-02-12 21:38:08 +0800 CST

标志子集的所有排列

  • 772

我有一组任意大小的二进制标志作为数字int。

例如，数字“18”< 2**5=> 最少 5 个标志。

我需要使用相当复杂的方案找到设置标志的所有组合。我宁愿举一个例子并展示我想要得到的东西。我想编写一个生成器，它以数字作为输入并仅返回该数字*的设置位的所有组合。例如，考虑数字 18：

>>> bin(18)
'0b10010'

我想制作一个将返回以下内容的生成器：

yield [True, False, False, True, False] # исходное число
yield [False, False, False, True, False] # первый флаг установлен в 'False'
yield [True, False, False, False, False] # только второй флаг установлен в 'False'
yield [False, False, False, False, False] # оба флага установлены в `False`
  1. 只能更改原始数字中的单位。
  2. 标志的排序顺序很重要；标志从左到右排序。
  3. 生成的序列不包含重复。
  4. 两个标志被关闭的组合必须始终出现在仅一个标志被关闭的任何组合之后。那是
[True, True, False, True]

比

[True, False, False, True]

和什么

[True, True, False, False]

因此，生成器必须首先吐出最接近原始序列的组合。

如果返回数字而不是列表，我会很高兴int。以我为例：

yield 18
yield 2
yield 16
yield 0

为什么这是必要的？我正在寻找一组输入数据的最接近的组合（在 Levenshtein 度量中（没有邻居排列））来训练神经网络来预测某个集合。标志指示源数据中是否存在列。我通过谓词运行结果数字来了解它是否适​​合我。

CPU_Bound 算法（要求渐进复杂度）。

最后，根据@MBo 和@Stanislav Volodarskiy 的答案，我使用了以下代码（欢迎批评！）：

from itertools import combinations

def gen_submasks(n:int):
    def gen_bases(n:int):
        while n > 0:
            yield (base := 1 << n.bit_length() - 1)
            n = n ^ base
            
            # alternative syntax:
            # base = 1 << n.bit_length() - 1
            # yield base
            # n ^= base
    
    for count in range(n.bit_count()):
        for combination in combinations(gen_bases(n), count):
            yield n - sum(combination)
    
    yield 0

def main():
    n = 41
    for submask in gen_submasks(n):
        print(bin(submask)[2:].zfill(n.bit_length()))

main()

# 101001
# 001001
# 100001
# 101000
# 000001
# 001000
# 100000
# 000000
python

2 个回答

  1. 子掩码枚举：

    def submasks(mask):
    sub = mask
    while sub:
        yield sub
        sub = (sub-1) & mask

mask = 41 #101001
for s in submasks(mask):
    print(s, bin(s)[2:])

41 101001
40 101000
33 100001
32 100000
9 1001
8 1000
1 1
    • 4
  2. Best Answer

    选择所有设置位作为元组。然后我们对位的子集进行排序，降低它们的功率。子集由位组装而成 - 这是我们需要的掩码：

    def bits(n):
    """ bits of n ascending """
    while n > 0:
        b = n ^ (n & (n - 1))  # least bit of n
        yield b
        n ^= b                 # clear least bit


def masks(n):
    """ n submasks descending bit population, ascending value """
    bs = tuple(bits(n))

    def c_masks(c, i, m):
        if c == 0:
            yield m
        else:
            for j in range(c - 1, i):
                yield from c_masks(c - 1, j, m | bs[j])

    for c in reversed(range(len(bs) + 1)):  # subset cardinality
        yield from c_masks(c, len(bs), 0)


def main():
    n = int(input())
    w = len(f'{n:b}')
    for m in masks(n):
        print(f'{m:0{w}b}')


main()

    $ echo 18 | python masks.py
10010
00010
10000
00000

$ echo 19 | python masks.py
10011
00011
10001
10010
00001
00010
10000
00000
    • 3

相关问题