[Python] 순열 / 조합 제너레이터

새해 복 많이 받으세요

순열/조합 알고리듬 관련해서 검색해보면 거의 대부분의 블로그의 글이 재귀 호출을 통한 구현에 대해 쓰고 있다. 뭐 n개 원소를 가진 집합에 대해서 최대 n회의 깊이를 가지는 재귀라서 안전하긴 하지만… 다만 재귀로 작성하는 경우 yield 구문을 쓸 수 없기 때문에 순열을 찍어보는 거 말고 실제로 구해야 하는 경우라면 스택의 크기와 상관없이 메모리가 문제가 된다. 당장 알파벳 26개로 만들 수 있는 순열의 수만해도 ‘403291461126605635584000000’개가 된다. 따라서 가능하면 재귀를 사용하지 않고, 순열을 매회 계산할 수 있는 로직이 있다면 좋을 것이다.

기본적인 아이디어는 표본 집합을 얼려놓고, 대신 각 원소의 인덱스를 갖는 리스트를 조작하면서 매 순열을 계산하는 것이다.