순열, 중복순열, 조합, 중복조합 구현하기

순열(permutations)

1. 서로 다른 n개의 원소를 갖고 있는 배열에서 중복을 허용하지 않고(순서 상관 o) r개를 뽑음

2. 재귀 - 백트래킹

   array = [1, 2, 3, 4, 5]
   k = 2
   used = [False for i in range(len(array))]
   
   def permutations(arr):
       if len(arr) == k:
           print(arr, end="")
           return arr
       for i in range(len(array)):
           if used[i] == False:
               used[i] = True
               permutations(arr + [array[i]])
               used[i] = False
   
   permutations([])

   백트래킹 과정을 그림으로 표현하면 아래와 같다.
   
   해당 과정을 array 개수만큼 반복할 것이다. (위 그림은 1로 시작하는 경우만 나타냄)

3. itertools

   from itertools import permutations
   
   for i in permutations([1, 2, 3, 4], 2):
   		print(i, end="")
   
   # 결과 
   # (1,2), (1,3), (1,4), (2,1), (2,3), (2,4), (3,1), (3,2), (3,4), (4,1), (4,2), (4,3), (4,4)

중복 순열(product)

1. 서로 다른 n개의 원소를 갖고 있는 배열에서 중복을 허용하고(순서 상관 o) r개를 뽑음

2. 재귀 - 백트래킹

   array = [1, 2, 3]
   k = 2
   used = [False for i in range(len(array))]
   
   def product(arr):
       if len(arr) == k:
           print(arr, end="")
           return arr
       for i in range(len(array)):
           product(arr + [array[i]])
   
   product([])

3. itertools

   from itertools import product
   
   for i in product([1, 2, 3, 4], 2):
   	print(i, end="")

조합(combinations)

1. 서로 다른 n개의 원소를 갖고 있는 배열에서 중복을 허용하지 않고(순서 상관 x) r개를 뽑음

2. 재귀 - 백트래킹

   array = [1, 2, 3]
   k = 2
   used = [False for i in range(len(array))]
   
   def combination(arr, i):
       if len(arr) == k:
           print(arr, end="")
           return arr
       for i in range(i, len(array)):
           combination(arr + [array[i]], i + 1)
   
   combination([], 0)
   

3. itertools

   from itertools import combinations
   
   for i in combinations([1, 2, 3, 4], 2):
   	print(i, end="")

중복 조합(combinations_with_replacement)

1. 서로 다른 n개의 원소를 갖고 있는 배열에서 중복을 허용하고(순서 상관 x) r개를 뽑음

2. 재귀 - 백트래킹

   array = [1, 2, 3]
   k = 2
   used = [False for i in range(len(array))]
   
   def combination_with_replacement(arr, i):
       if len(arr) == k:
           print(arr, end="")
           return arr
       for i in range(i, len(array)):
           combination_with_replacement(arr + [array[i]], i)
   
   combination_with_replacement([], 0)
   print()

3. itertools

   from itertools import combinations_with_replacement
   
   for i in combinations_with_replacement([1, 2, 3, 4], 2):
   	print(i, end="")