부분집합을 비트마스크로 열거하기

원소가 n 개면 부분집합은 2의 n제곱개다. 각 원소를 넣거나 뺀다는 선택이 n 번 있기 때문이다. 이걸 코드로 옮기는 방법을 몇 가지 써봤다.

재귀

def rec(n, cur=''):
    if len(n) == 0:
        print(cur)
    else:
        rec(n[1:], cur + n[0])
        rec(n[1:], cur)

rec('abcde')

선택 자체를 그대로 옮긴 형태다. 첫 글자를 넣는 가지와 빼는 가지로 갈라지고, 남은 것에 대해 같은 일을 한다.

itertools

from itertools import product

n = 'abcd'
for i in product(*[j + ' ' for j in n]):
    print(''.join(i))

각 글자를 ('a', ' ') 처럼 두 개짜리로 만들어 곱집합을 구한다. 빼는 쪽을 빈 문자열이 아니라 공백으로 둔 게 걸리는데, '' 로 만들면 product 에 넘길 때 그 자리가 사라져 버려서 그렇게 한 것으로 보인다. 결과에 공백이 섞여 나온다.

비트마스크

숫자 하나를 부분집합 하나로 본다. 0부터 2의 n제곱까지 세면서 각 비트가 1인 자리의 원소만 고른다.

s = 'abcd'
n = len(s)
r = []
for mask in range(1 << n):
    curr = ''
    for i in range(n):
        if mask & (1 << i):
            curr += s[i]
    r.append(curr)

1 << n 이 2의 n제곱이다. mask & (1 << i) 는 mask 의 i 번째 비트가 켜져 있는지 보는 것이다.

재귀가 없고 순서가 숫자 순으로 고정된다. 부분집합에 번호를 매겨 배열 인덱스로 쓰고 싶을 때 이 형태가 편하다.

2의 n제곱과 n의 2제곱

이 코드 앞에 이렇게 쓴 시도가 남아 있다.

for i in range(n ** 2):
    print(''.join([a if b == '0' else '' for a, b in zip(str, bin(i)[2:].zfill(n))]))

n ** 2 로 돌고 있다. 2의 n제곱이어야 하는 자리다.

그런데 이때 쓴 문자열이 abcd 라서 n 이 4였고, 4의 2제곱과 2의 4제곱이 둘 다 16이라 결과가 맞게 나왔다. 두 값이 같아지는 건 n 이 2와 4일 때뿐이다. 다섯 글자로 바꿨으면 25와 32로 갈렸을 것이다.

부분집합과 부분 문자열은 다르다

같은 파일에 이것도 있다.

def subString(s):
    r = []
    n = len(s)
    for i in range(n):
        for j in range(i, n):
            r.append(s[i:j+1])
    return r

이건 이어져 있는 구간만 뽑는다. 시작과 끝을 정하는 것이라 개수가 n(n+1)/2다.

부분집합은 2의 n제곱, 부분 문자열은 n제곱 규모다. 앞에서 만든 열거를 부분 문자열 문제에 그대로 쓰면 필요 없는 걸 잔뜩 만들게 된다.