200506_순열&조합&부분집합.md

순열( Permutation )

• nPr

• 단순하게 순열을 생성하는 방법
  • 반복문을 활용한 순열 생성 알고리즘

# {1, 2, 3} 을 포함하는 모든 순열을 생성하는 함수

for i1 in range(1, 4):
    for i2 in range(1, 4):
        if i2 != i1:
            for i3 in range(1, 4):
                if i3 != i1 and i3 != i2:
                    print(i1, i2, i3)

# Output
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

• 재귀 호출을 통한 순열 생성 - 1

# arr[] : 데이터가 저장된 배열
# swap(i, j) : arr[i] <--교환--> arr[j]
# n : 원소의 개수
# i : 선택된 원소의 수

def perm(n, k):
    if k == n :
        print_arr()
    else:
        for i in range(k, n-1):
            swap(k, i)
            perm(n, k+1)
            swap(k, i)

• 재귀 호출을 통한 순열 생성 - 2
  • 평소 쓰던 방법 ( visited )
  • 교환에 의한 방법은 아니다.

# arr[] : 데이터가 저장된 배열
# n : 원소의 개수
# i : 선택된 원소의 수
# visited[N-1] : 방문 여부
# t : 결과 저장 배열

def perm(k):
    if n == k:
        print_arr()
    else:
        for i in range(0, N-1):
            if not visited[i]:
                t[k] = arr[i]
                visited[i] = True
                perm(k+1)
                visited[i] = False

• 6자리 숫자에 대해서 완전검색을 적용해서 baby-gin 을 검사해보시오.

# 1 2 2 4 6 5
def perm2(n, k):
    global chk
    
    if chk:
        return
    if k == n:
        t = r = 0
        if ta[0] == ta[1] and ta[1] == ta[2]:
            t += 1
        if ta[3] == ta[4] and ta[4] == ta[5]:
            t += 1
        if ta[0] + 1 == ta[1] and ta[1] + 1 == ta[2]:
            r += 1
        if ta[3] + 1 == ta[4] and ta[4] + 1 == ta[5]:
            r += 1
        if t + r == 2:
            chk = True
    else:
        for i in range(n):
            if not visited[i]:
                ta[k] = arr[i]
                visited[i] = True
                perm2(n, k+1)
                visited[i] = False

T = int(input())
for tc in range(1, T+1):
    data = list(map(int, list(input())))

부분집합 ( subsets )

• 파이썬 재귀를 이용해 부분집합 만들기

include / exclude 가 그림에서 뒤바껴있음!

• 파이썬으로 부분집합 만드는방법 ( 비트 오퍼레이션 활용 )

arr = [3, 6, 7, 1, 5, 4]
n = len(arr)

for i in range(1<<n):
  for j in range(n):
    if i & (1<<j):
      arr[i]
  print()
print()

• 문제로 연습

# 부분집합 합 문제 구현하기
# 아래의 10개 정수 집합에서 모든 부분집합 중 원소의 합이 0 이 되는 부분집합을 모두 출력하시오.
# 비트 오퍼레이션 활용

arr = [-1, 3, -9, 6, 7, -6, 1, 5, 4, -2]
n = len(arr)

for i in range(0, (1<<n)): # 2^n
    tr = []
    for j in range(0, n):
        if i & (1 << j): # i의 j번째 비트가 1인지 아닌지 확인
            tr.append(arr[j])
            #print('%d'%arr[j], end='')
    if sum(tr) == 0:
        print(tr)

조합 ( Combination )

# 재귀 호출을 이용한 조합 생성 알고리즘
an[] : n개의 원소를 가지고 있는 배열
tr[] : r개의 크기의 배열, 조합이 임시 저장될 배열
    
def comb(n, r):
    if r == 0:
        print_arr()
    else:
        if n < r:
            return
        else:
            tr[r-1] = an[n-1]
            comb(n-1, r-1)
            comb(n-1, r)
            
# 재귀 호출 이용한 조합 생성 알고리즘 - 2
an[]
tr[]

def comb(k, s):
    if k == r :
        print_arr()
    else:
        for i in range():
            t[k] = a[i]
            comb(k+1, i+1)