2. 부분집합, 순열, 조합

부분집합

1. 비트연산자를 이용
   

   # A : 집합A 리스트
   N = len(A)
   
   for i in range(1<<N): # 2^N 만큼 반복
       part = [] # 부분 집합이 들어갈 리스트
       for j in range(N):
       	if i & (1<<j):
               part.append(A[j])
       print(part) # 부분집합 중 하나

2. 깊이 우선 탐색 - 재귀
   

   def subset(a, k, n): # a : 집합에 대한 비트 표현, k : 선택한 횟수, n : 모든 선택수
       if k==n:
       	process_solution(a,n)
       else:
       	a[k] = 0 # 선택안함
           subset(a, k+1, n)
           a[k] = 1 # 선택함
           subset(a, k+1, n)

 

순열 nPr

서로 다른 n개 중에 r개를 뽑아서 한 줄로 나열하는 것 

nPr = n(n-1)(n-2)...(n-r+1)

1. 내꺼
   

   def perm(res, n, r):
       if r == 0:
           print(res)
       else:
           for i in range(n):
               if A[i] not in res:
                   res[r-1] = A[i]
                   perm(copy.deepcopy(res), n, r-1)
   
   n = 4
   r = 3
   res = [-1]*r
   A = [1,2,3,4]
   perm(res, n, r)

2. 교환을 통한 선택 - 재귀
   

   # a[] : 데이터가 저장된 리스트
   # n : 원소의 개수
   # k : 지금까지 선택된 원소의 수
   def perm(n, k):
       if k == n: # 하나의 순열이 생성됨
           print(a)
       else:
       	for i in range(k, n):
               a[k], a[i] = a[i], a[k] # 교환을 통한 선택
               perm(n, k+1) # 재귀호출
               a[k], a[i] = a[i], a[k] # 이전 상태로 복귀

3. 백트래킹 - 재귀
   

   def permutation(order, k, n): # order : 순열의 순서를 저장,  k : 선택한 횟수, n : 모든 선택수
       if k == n:
           print_order_array(order, n)
       else:
           check = [False]*n  # [F, F, F, F]
           for i in range(k):
               check[order[i]] = True
               
           for i in range(n):
               if check[i] == False:
                   order[k] = i
                   permutation(order, k+1, n)

4. itertools
   

   import itertools 
   a = ['A', 'B', 'C'] 
   
   result = itertools.permutations(a) # 순열 nPn 
   result = itertools.permutations(a, r) # 순열 nPr 
   result = itertools.product(a, repeat=r) # 중복순열 n(pi)r 
   
   print(list(result))​

   
   
   

 

조합

서로 다른 n개 중 r개를 순서없이 뽑는 것

nCr = n!/(n-r)!r!

1. 파스칼의 삼각형 원리 - 재귀
   

   

   파스칼의 삼각형

   # a[] : n개의 원소를 가진 리스트
   # res[] : 조합이 임시 저장될 크기 r인 리스트
   
   def comb(res, n, r):
       if r == 0:
       	print(res)
       else:
       	res[r-1] = A[n-1] 
           comb(res, n-1, r-1) # (n-1)C(r-1), A[n-1]을 선택한 경우
           comb(res, n-1, r)   # (n-1)C(r)  , A[n-1]을 선택하지 않은 경우
           
           
   n = 4
   r = 3
   res = [-1]*r
   A = [1,2,3,4]
   comb(res, n, r)

2. itertools
   

   import itertools
   a = ['A','B','C']
   result = itertools.combinations(a, r=2) # 조합 nCr
   result = itertools.combinations_with_replacemnet(a, r=2) # 중복조합 n개 중에 2개
   print(list(result))

 

주의할 점

• itertools는 순열, 조합의 결과만 알려주기 때문에 백트래킹과 같은 중간에 확인할 수 있는 방법이 없음
• 즉, 완전검색에서만 사용이 가능