[알고리즘] 순열 알고리즘 구현

순열(순서 o) vs 조합(순서x)

 

순열(Permutation): 서로 다른 n 개의 대상에서 r 개를 뽑아 일렬로 배열한 것.

순열 알고리즘 구현 방법

1. 파이썬 모듈 사용

2. 재귀

3. 중복 for문 (리스트가 길어지면 너무 비효율적)

 

1. 파이썬 모듈 사용

• 파이썬 내장 itertools 패키지의 permutations 모듈 활용
• 만들어진 순열과 조합은 튜플의 형태로 리스트에 담겨서 반환된다. -> ([(0, 1, 2), ...])

from itertools import permutations

arr = [0, 1, 2, 3, 4, 5]

print(list(permutations(arr, 3)))

https://juhee-maeng.tistory.com/91

→모듈 사용하는 게 대체로 가장 빠르다고 함..

 

2. 재귀

2.1 DFS, 백트래킹과 상당히 유사하다.

• permutation([0,1,2,3], 2)
  = ([0],permutation([1,2,3], 1)) + ([1],permutation([0,2,3], 1)) + ([2],permutation([0,1,3], 1))+ ([3],permutation([0,1,2], 1))
• permutation([0,1,2,3], 3)
  = ([0],permutation([1,2,3], 2)) + ([1],permutation([0,2,3], 2)) + ([2],permutation([0,1,3], 2))+ ([3],permutation([0,1,2], 2))
  = ([0],{([1], permutation([2,3],1)) + ([2], permutation([1,3],1)) + ([3], permutation([1,2],1))}) + ([1]. { ~

def gen_permutations(arr, n):
    result = []

    if n == 0:
        return [[]]

    for i, elem in enumerate(arr): 
        for P in gen_permutations(arr[:i] + arr[i+1:], n-1):
            result += [[elem]+P]
              
    return result

 

2.2

def permutation(arr,r):
    arr = sorted(arr)
    used = [0 for _ in arr]

    def generate(chosen, used):
        if len(chosen) == r:
            print(chosen)
            return #used[i] = 0로 돌아가는데, 다시 for문 거치는 게 아니라, 바로 이어져서 i값이 유지됨.
        
        for i in range(len(arr)): #arr은 함수 외부에 정해져 있음(상수수)
            if not used[i]:
                chosen.append(arr[i])
                used[i] = 1
                generate(chosen, used)
                used[i] = 0 #순열 하나 만들고 나서, 다시 0으로 initialize
                chosen.pop() #return이 없으므로 for문이 끝난 후에도 if문 다시 돌고, if문 만족 못하므로 for문 새로 시작됨

    generate([], used)

 

좋은 코드라고는 하나 개인적으로 이해하는 데 시간이 걸렸음. 

arr: 리스트
r: 리스트 중 뽑을 개수

[for문 안에서]
chosen: 순열 구성하는 원소 리스트
used: chosen에 들어간 원소 index 위치에 해당 원소의 사용 여부를 0/1로 알려주는 리스트(즉 arr와 연동됨) (*디폴트는 0으로 채워짐)

 

• 함수 정의문에는 return의 위치가 중요함. for문이 모두 종료되었대도 return이 다른 곳에 있다면 다시 iteration 거침.
  • 여기도 for문의 상단 if문을 거쳐야 return되는데, for문이 종료되고 if문으로 돌아갔을 때 if문 조건이 성립되지 않으므로 return이 실행되지 않음. 즉, 다시 for문으로 돌아가 처음부터 실행됨. (물론 이 상황에서 used와 chosen은 이전 로그가 반영된 상태이므로 i값이 슉슉 점프하게 됨.
• generate 함수 정의문 내부에 generate가 사용된 재귀형식임.
  • 내부 generate이 실행될 때 if문 만족되면 바로 return 일어나므로, 내부 generate 실행 직전 i값이 그대로 보존된 상태로 used[i]=0 코드로 넘어감.
  • 만약 내부 generate 실행될 때 if문 만족 못 하면 for문으로 넘어가고, 결국 내부 generate가 종료되려면 내부 if문이 만족될 때까지 iter iter iter..
• if not False:
  • if not 이하가 False일 때 조건문 시행됨
  • python에서 False에 해당하는 것
    • False (Bool)
    • 0,0L,0.0과 같은 숫자 0 값
    • 다음과 같은 빈 시퀀스 :
      • 빈 목록 []
      • 빈 사전 {}
      • 빈 문자열 ''
      • 빈 튜플
      • 빈 세트
      • None개체
      • [0] 혹은 [0,0,..]은 아님.!!!
• 실행 원리 예시

permutation('ABCD', 3)

>>>

i: 0, chosen: ['A'], used: [1, 0, 0, 0]
i: 1, chosen: ['A', 'B'], used: [1, 1, 0, 0]
i: 2, chosen: ['A', 'B', 'C'], used: [1, 1, 1, 0]
['A', 'B', 'C']
i: 3, chosen: ['A', 'B', 'D'], used: [1, 1, 0, 1]
['A', 'B', 'D']
i: 2, chosen: ['A', 'C'], used: [1, 0, 1, 0]
i: 1, chosen: ['A', 'C', 'B'], used: [1, 1, 1, 0]
['A', 'C', 'B']
i: 3, chosen: ['A', 'C', 'D'], used: [1, 0, 1, 1]
['A', 'C', 'D']
i: 3, chosen: ['A', 'D'], used: [1, 0, 0, 1] ............

 

https://cotak.tistory.com/70

[Python] 순열, 조합 구현하기 - itertools & recursion

https://shoark7.github.io/programming/algorithm/Permutations-and-Combinations

조합과 순열 알고리즘, 파이썬으로 구현하기

https://www.delftstack.com/ko/howto/python/if-not-condition-in-python/

Python에서 if not 조건 사용