サブロウ丸

大学生です

Python 集合と自然数との対応付け

下記のような、集合と自然数の対応付けを考えます。
{0, 1, 2, 3} <—> 15

基本的な考えは2進数表記です。
{0, 1, 2, 3} <—> 20 + 21 + 22 + 23 = 15
{0, 1, 3} <—> 20 + 21 + 23 = 11

これをそのまま関数にすると、

def set2int(_iter):
    res = 0
    for i in _iter:
        res += 2**i    
    return res
def set2int(_iter):
    return sum([2**i for i in _iter])

となります。この関数はビット演算を使って表すことができて、

def set2int(_iter):
    res = 0
    for i in _iter:
        res |= 1 << i        
    return res

こうなります。演算自体はビット演算の方が3倍ほど速い(自分のmac bookで計測)ので、下の関数の方が良いでしょう。
なぜ、こういう関数になるかを下記にまとめました。

f:id:inarizuuuushi:20170116181611j:plain

f:id:inarizuuuushi:20170116181615j:plain

逆に自然数から集合に変換するのもビット演算を用いた方が高速かつ、簡潔に書けます。

def int2list(n):
    res = list()
    elm = 0
    while n != 0:
        if (n ^ 1 << elm) < n:
            res.append(elm)
            n ^= 1 << elm
        elm += 1
    return res


f:id:inarizuuuushi:20170116181619j:plain

f:id:inarizuuuushi:20170116181622j:plain