Home » 순열

순열

같은 것을 포함하는 순열 생성기 (Python)

OOO, XX 로 만들 수 있는 5글자 문자열을 모두 생성하는 방법을 소개한다. 총 5개의 글자로 만들 수 있는 순열은 5! (120) 가지이다. 그런데 같은 O 끼리와 같은 X 끼리는 구분할 수 없으므로 실제로는 5!/(3! * 2!) 가지로 10가지의 조합만 가능할 것이다. 파이썬의 itertools 에서는 순열, 조합 및 중복 순열과 중복 조합을 만드는 함수가 제공되지만 같은 것을 포함하는 순열을 생성하는 함수는 제공되지 않는다. 중복된 원소가 있을 때, 중복 없는 순열을 만드는 방법은 다음과 같이 생각해 볼 수 있다. OOOXX 의 5글자로… 더 보기 »같은 것을 포함하는 순열 생성기 (Python)

오일러 프로젝트 24

오일러 프로젝트 24 번은 숫자 10개(0~9)로 만들어지는 순열 중에서 백만번째 항을 구하는 문제이다. 어떤 대상을 순서에 따라 배열한 것을 순열이라고 합니다. 예를 들어 3124는 숫자 1, 2, 3, 4로 만들 수 있는 순열 중 하나입니다. 이렇게 만들 수 있는 모든 순열을 숫자나 문자 순으로 늘어놓은 것을 사전식(lexicographic) 순서라고 합니다. 0, 1, 2로 만들 수 있는 사전식 순열은 다음과 같습니다. 012,   021,   102,   120,   201,   210… 0, 1, 2, 3, 4, 5, 6, 7, 8, 9로… 더 보기 »오일러 프로젝트 24

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

새해 복 많이 받으세요

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