파이썬, 조합과 순열 구하기 (백트래킹)

파이썬, 조합과 순열 구하기 (백트랙킹)

 

글. 오상문 sualchi@daum.net

(참조: https://skyjwoo.tistory.com/56 )

 

파이썬은 itertools 모듈의 함수를 이용하면 순열이나 조합을 쉽게 구할 수 있지만, 여기에서는 백트랙킹을 이용하여 구현된 예제를 소개합니다.

 

def combination(data, n): # 순서 없는 조합
  ret = []
  if n==0 or n>len(data):
    return ret
  if n==1:
    ret += list(map(lambda x: {x}, data))
  else:
    for i in range(len(data)):
      ret += list(map(lambda x: {data[i]}|x, combination(data[i+1:], n-1)))
  return ret

 

def permutation(data, n):  # 순열: 순서 있는 조합
  ret = []
  if n==0 or n>len(data):
    return ret
  if n==1:
    return list(map(lambda x:(x,), data))
  for i in range(len(data)):
    temp = [] + data
    temp.remove(data[i])
    ret += tuple(map(lambda x: (data[i],)+x, permutation(temp, n-1)))
  return ret

 

#--------- main -----------------
nums = [1,2,3,4]

 

output1 = list(map(list, combination(nums, 3)))
for out in output1:
  print(out)

 

print('-'*40)

 

output2 = list(map(list, permutation(nums, 3)))
for out in output2:
  print(out)

 

[실행 결과]

[1, 2, 3]
[1, 2, 4]
[1, 3, 4]
[2, 3, 4]
----------------------------------------
[1, 2, 3]
[1, 2, 4]
[1, 3, 2]
[1, 3, 4]
[1, 4, 2]
[1, 4, 3]
[2, 1, 3]
[2, 1, 4]
[2, 3, 1]
[2, 3, 4]
[2, 4, 1]
[2, 4, 3]
[3, 1, 2]
[3, 1, 4]
[3, 2, 1]
[3, 2, 4]
[3, 4, 1]
[3, 4, 2]
[4, 1, 2]
[4, 1, 3]
[4, 2, 1]
[4, 2, 3]
[4, 3, 1]
[4, 3, 2]

 

<이상>