集合的整数表示

摘要

整理一些集合的小操作

对于大小为 的集合,要求我们表示该集合的任意子集,借助于整数的二进制表示,可以按以下方式编码为整数

位运算

借助位运算来进行集合的运算。一系列例子:

意义 表示
空集 0
只有第 i 个元素的集合
含有 元素的集合
第 i 个元素是否选择
添加第 i 个元素 $s
删除第 i 个元素
集合的并集 $s
集合的交集

子集枚举

直接循环即可

FOR i from 0 to (1<<n)-1 :
    do something

子子集枚举

对于全集 U 的一个子集 S,如何枚举 S 的子集(相当于 S 是一个二进制数)。我们倒着循环,每次与 做与运算消除非 S 集合元素的影响:

int i=s
do :
    do something
    i=(i-1)&s
while(i!=s)

可以理解为,每次转移的时候,i 的最低位 1 变成 0,而这个 1 后面的 0 全部变成 1。然后取了与 s 的交集,使得只有子集内的位变换。


  转载请注明: Sshwy's Blog 集合的整数表示

 上一篇
那年 @ 今日 那年 @ 今日
摘要 纪念现役 2 年 OI 本站 @ 碎碎念一路踏着星光走来,2018 四川省选也结束了,奖学金尘埃落定,看到 Siyuan 大佬一式 40 分,LMOliver 怒切 D1T2,XRY 努力学习文化课。看到 Mr_spade《我亲爱的
2019.04.20
下一篇 
Yay 使用小记 Yay 使用小记
摘要 Yay——Yet another Yogurt. Yaourt 已死! 概述作者入坑 linux 以来,从最开始的 Ubuntu,到国产的 Deepin,到现在的 Manjaro Deepin,在 linux 上也是折腾了很久。 U
2019.04.14
  目录