python - 순열 (permutation) - 리스트의 각 항목이 중복 되지 않게 모든 경우 구하기

알고리즘 문제 풀기에서 단골로 나오는 것중 하나가 순열입니. 리스트가 있을 때 서로 겹치지 않게 모든 경우로 표현하는 것입니다.

 

예들 들어 1과 2가 있으면 다음과 같은 조합을 만들 수 있습니다.

1 2
2 1

 

만약 1, 2, 3이 있다면 다음과 같은 조합을 만들 수 있겠죠?

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

 

순열은 factorial 로 경우가 수의 늘어납니다.

1! = 1
2! = 1 x 2 = 2
3! = 1 x 2 x 3 = 6
4! = 1 x 2 x 3 x 4 = 24

순열을 직접 구현 할 수도 있겠지만, 빠르게 해답을 찾으려면 itertools 를 사용할 수 있습니다. (python 만세)

import itertools

for perm in itertools.permutations([1, 2, 3]):
    print(perm)

코드를 실행 하면 결과는 다음과 같이 나옵니다.

(1, 2, 3)
(1, 3, 2)
(2, 1, 3)
(2, 3, 1)
(3, 1, 2)
(3, 2, 1)

2017년 카카오 코드페스티벌의 단체사진 찍기 문제에서도 응용 가능합니다.

import itertools

for perm in itertools.permutations("ACFJMNRT"):
    print(perm)

 

가장 효율 적인 방법은 아닐 수 있겠지만 일단 이해하기는 쉽습니다. 전체 순열에서 조건에 맞는 것들의 갯수를 세면 되니까 말이죠.

...
('T', 'R', 'N', 'M', 'J', 'A', 'C', 'F')
('T', 'R', 'N', 'M', 'J', 'A', 'F', 'C')
('T', 'R', 'N', 'M', 'J', 'C', 'A', 'F')
('T', 'R', 'N', 'M', 'J', 'C', 'F', 'A')
('T', 'R', 'N', 'M', 'J', 'F', 'A', 'C')
('T', 'R', 'N', 'M', 'J', 'F', 'C', 'A')

참고

• https://docs.python.org/3/library/itertools.html
• 순열과 조합 - 순열2. 팩토리얼(factorial), 계승
• 카카오코드 본선 - 단체사진 찍기