세트의 서브 세트의 비 반복 그룹을 찾는 쉬운 방법이 있습니까?

Question

집합이 있다고 가정 해 봅시다 : {1,2,...,N}, 그리고 각 하위 집합의 특정 수의 요소를 가진 K 개의 비어 있지 않은 부분 집합의 비 반복적 인 그룹을 찾고 싶습니다.

예 : 세트 : {1,2,3,4,5,6,7} 서브 세트 수 3, 요소 수 3,3,1. 이 같은 기 생성 것이다 : I가 제 조합 한 후 두 번째 생성한다면 {{1,2,3},{4,5,6},{7}} or {{5,7,2},{4,3,1},{6}} 등

모든 가능한 그룹의 수,이 경우에 있어서는, 동일한

C(7,3)*C(4,3)*C(1,1)*1/(2!) = 35*4/2 = 70로를 I (140)을 얻을 것 결과는 계승에 영향을 미치지 않기 때문에

내 질문은 : 그룹이 이미 나타나는지 확인하는 쉬운 방법이 있습니까? 이전에 계산 된 모든 그룹으로 배열을 만들고 새로운 그룹이 이미 생성되었는지 확인해야합니까?

Answer 1

동등한 크기의 부분 집합이 lexicographical order 인 경우 모든 그룹을 생성하고 그룹 만 유지하십시오.

예를 들어, {1,2,3}이 사전 식 {4,5,6}보다 앞에 있기 때문에 그룹 {{1,2,3},{4,5,6},{7}}을 유지합니다.

그러나 {5,7,2}이 {4,3,1}을 따라야하므로 {{5,7,2},{4,3,1},{6}} 그룹을 삭제합니다. 이 이론은 어느 시점에서 올바른 순서로 그룹 {{4,3,1},{5,7,2},{6}}을 생성하므로 보관됩니다.

---

최적화의 다음 단계는이 모든 그룹 생성,하지만 전적으로 올바른 그룹을 생성하지 이다. 예를 들어, 첫 번째 하위 집합이 {5,7,2} 인 경우 두 번째 하위 집합의 형식은 {6,x,y}이어야하며 6은 5보다 큰 사용되지 않은 유일한 숫자입니다.