단일 집합에서 조합 조합 조합을 나열하는 방법

Question

조합 조합 및 열거에 대한 질문이 많다는 것을 알고 있습니다. 그러나 필자는 검색 한 내용과 이후에 수행 한 내용을 구체적으로 찾지 못했습니다. 내가 뭔가를 놓친 경우에는 그 점을 지적 해주십시오. 그러면 질문을 닫을 수 있습니다.

따라서 N 개의 요소 집합이 있다고 가정하고 Sum (k1, ..., kx) < = N 인 x 개의 양의 정수 k1, ..., kx를가집니다. 모든 방법을 열거합니다. 나는 원본 N 세트에서 (교체없이) 주어진 크기의 서브 세트를 선택할 수있다.

나는 그것이 올바르게 표현되기를 바란다. 내가 가지고 있지 않은 경우에, 간단한 예입니다. = 1

우리 열거한다
N = 4, X = 2, K1 = 2, K2

• {1, 2} {3}
• {1, 2} {4}
• {1, 3} {2}
• {1, 3} {4}
• {1,4} {2}
• {1,4} {3}
• {2 3} {1}
• {2, 3} {4}
• {2, 4} {1}
• {2, 4} {3}
• {3, 4} {1}
• {3 4} {2} 일반적인 경우

총 수는 I 일 수 생각 :

C (N, K1) * C (N - K1, K2) * ... * C (N - 합 (k1, ..., kn-1), kn).

초기 생각에 스택을 사용하면 상당히 쉽게 할 수 있습니다. 각 스택 레벨 i에서, 표준 조합 열거를 사용하여 부분 집합 ki를 생성 할 수 있으며, 선택된 요소를 각 레벨에서 소스 집합에서 제거하거나 원래 집합에서 열거하고 요소가 포함 된 경우를 건너 뛸 수 있습니다 .

내 질문에 더 빠르고 우아한 솔루션이 있습니까?

Answer 1

귀하의 질문은 정확하게 멀티 세트의 순열을 열거하는 문제입니다. 귀하의 k _i이 주문되었다고 가정하십시오.

먼저 문제는 정확히 Σ k = 1 인 것과 같습니다. N이면 Σk < N이면 0-k 인 k _{x +1}을 간단하게 추가 할 수 있습니다.

이제 ₂ 2의이 ₃ 3의, ... K k는 어떤 임의의 고정 순서로 원래 세트 S의 요소를 넣고 ₁ 1의, k는 K 이루어진 MULTISET 각각의 순열을 생성 할 _x x 's. 이 다중 집합은 S의 크기 (N)가 같기 때문에 k _i이 N에 더해진다.S 내의 각 요소를 다중 집합의 순열에서 대응하는 값을 갖는 부분 집합에 할당함으로써 S의 분할을 생성합니다.

예 : S = {apple, banana, chirimoya, date} (N = 4). k = 2 및 k = 1을 취하여 합계가 4가되도록 k = 1을 추가합니다 (하위 집합 3에 할당 된 요소는 무시할 것입니다).

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

우리는 이러한 예를 들어 S의 파티션으로 다시 변환 1 3 1 2을 복용 : 이제 우리는 (k 개의의가에 해당하는 두 개의 1의, 하나 둘, 하나 3가)에 MULTISET 1 1 2 3의 순열을 열거 : MULTISET는 중복을 많이 가지고있는 경우가 최적이 아닌 비록

apple  1 -> subset 1 
banana 3 -> unused 
chirimoya 1 -> subset 1 
date  2 -> subset 2 

그래서 우리는 MULTISET에 그냥 잘 작동 일련의 순열을 찾기위한 standard algorithm {{apple, chirimoya}, {date}}

있습니다.