RError.com

RError.com Logo RError.com Logo

RError.com Navigation

  • 主页

Mobile menu

Close
  • 主页
  • 系统&网络
    • 热门问题
    • 最新问题
    • 标签
  • Ubuntu
    • 热门问题
    • 最新问题
    • 标签
  • 帮助
主页 / 问题 / 1566009
Accepted
Aycon
Aycon
Asked:2024-02-12 21:38:08 +0000 UTC2024-02-12 21:38:08 +0000 UTC 2024-02-12 21:38:08 +0000 UTC

标志子集的所有排列

  • 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 2 个回答
  • 126 Views

2 个回答

  • Voted
  1. MBo
    2024-02-12T22:20:01Z2024-02-12T22:20:01Z

    子掩码枚举:

    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
    Stanislav Volodarskiy
    2024-02-12T23:04:58Z2024-02-12T23:04:58Z

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

    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

相关问题

  • 是否可以以某种方式自定义 QTabWidget?

  • telebot.anihelper.ApiException 错误

  • Python。检查一个数字是否是 3 的幂。输出 无

  • 解析多个响应

  • 交换两个数组的元素,以便它们的新内容也反转

Sidebar

Stats

  • 问题 10021
  • Answers 30001
  • 最佳答案 8000
  • 用户 6900
  • 常问
  • 回答
  • Marko Smith

    我看不懂措辞

    • 1 个回答
  • Marko Smith

    请求的模块“del”不提供名为“default”的导出

    • 3 个回答
  • Marko Smith

    "!+tab" 在 HTML 的 vs 代码中不起作用

    • 5 个回答
  • Marko Smith

    我正在尝试解决“猜词”的问题。Python

    • 2 个回答
  • Marko Smith

    可以使用哪些命令将当前指针移动到指定的提交而不更改工作目录中的文件?

    • 1 个回答
  • Marko Smith

    Python解析野莓

    • 1 个回答
  • Marko Smith

    问题:“警告:检查最新版本的 pip 时出错。”

    • 2 个回答
  • Marko Smith

    帮助编写一个用值填充变量的循环。解决这个问题

    • 2 个回答
  • Marko Smith

    尽管依赖数组为空,但在渲染上调用了 2 次 useEffect

    • 2 个回答
  • Marko Smith

    数据不通过 Telegram.WebApp.sendData 发送

    • 1 个回答
  • Martin Hope
    Alexandr_TT 2020年新年大赛! 2020-12-20 18:20:21 +0000 UTC
  • Martin Hope
    Alexandr_TT 圣诞树动画 2020-12-23 00:38:08 +0000 UTC
  • Martin Hope
    Air 究竟是什么标识了网站访问者? 2020-11-03 15:49:20 +0000 UTC
  • Martin Hope
    Qwertiy 号码显示 9223372036854775807 2020-07-11 18:16:49 +0000 UTC
  • Martin Hope
    user216109 如何为黑客设下陷阱,或充分击退攻击? 2020-05-10 02:22:52 +0000 UTC
  • Martin Hope
    Qwertiy 并变成3个无穷大 2020-11-06 07:15:57 +0000 UTC
  • Martin Hope
    koks_rs 什么是样板代码? 2020-10-27 15:43:19 +0000 UTC
  • Martin Hope
    Sirop4ik 向 git 提交发布的正确方法是什么? 2020-10-05 00:02:00 +0000 UTC
  • Martin Hope
    faoxis 为什么在这么多示例中函数都称为 foo? 2020-08-15 04:42:49 +0000 UTC
  • Martin Hope
    Pavel Mayorov 如何从事件或回调函数中返回值?或者至少等他们完成。 2020-08-11 16:49:28 +0000 UTC

热门标签

javascript python java php c# c++ html android jquery mysql

Explore

  • 主页
  • 问题
    • 热门问题
    • 最新问题
  • 标签
  • 帮助

Footer

RError.com

关于我们

  • 关于我们
  • 联系我们

Legal Stuff

  • Privacy Policy

帮助

© 2023 RError.com All Rights Reserve   沪ICP备12040472号-5