준호씨의 블로그

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

개발이야기

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

준호씨 2018.08.01 00:23

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


예들 들어 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 를 사용하자.

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')

참고


0 Comments
댓글쓰기 폼