순열까지 서브 세트의 컬렉션을 비교하십시오.

Question

저는 a [i] [j]라는 배열을 가지고 있습니다. 요소는 char이며 집합 {1, ..., 8}의 하위 집합으로 해석됩니다 (k 번째 비트가 1이면 요소 k가 하위 집합에 있음). 나는 그것이 적절하다고 생각하지 않지만, 모든 요소는 정확히 4 비트가 설정되어있다.

모든 행 a [1] [j] .. a [n] [j]는 {1, ..., 8}의 부분 집합입니다. {1, ..., 8}의 순열에 의해 다른 행을 얻을 수있는 경우 두 행이 중복으로 간주되는 중복 행을 제거해야합니다.

예 (0bxxxxxxxx는 이진수를 의미한다) 전자는 전치

8->8, 7->7, 6->1, 5->4, 4->3, 3->2, 2->5, 1->6 

적용하여 후자로부터 획득 될 수 있기 때문에

0b11000000, 0b01100000, 0b00110000 

는

0b00110000, 0b00011000, 0b00100100 

의 중복 결과를 재정렬하는 것.

성능을 고려하여 배열에는 약 20 개의 요소로 구성된 약 2000 개의 행이 포함되어 있습니다. 각 행은 이미 순서가 정해져 있으며, 행이 사전 순으로 늘어나는 순서로되어있어 도움이 될 수 있습니다. 나머지 알고리즘은 C로 작성되었으므로 C 솔루션이 선호됩니다.

도움 주셔서 감사합니다.

Answer 1

모든 하위 집합에 2 개의 요소가있는 경우이 값은 graph isomorphism이고 그래프 집합을 나타내는 부분 집합입니다. 이것은 훨씬 더 일반적이고 (따라서 더 힘들 수 있습니다.) 그래프 동형을 해결하고 여기에 적용되는지 확인하는 데 사용되는 경험적 방법을 살펴 보겠습니다.

동형 이성을 값 싸게 제외 할 수있는 많은 그래프 - 유사 동질성 발견법이 있습니다. 특정 컬렉션의 경우 각 요소가 속하는 하위 집합의 수를 계산 한 다음이를 정렬 할 수 있습니다. 귀하의 예제에서 두 컬렉션 모두 [2,2,1,1,0,0,0,0]이됩니다. 두 컬렉션에 대한 정렬 된 시퀀스가 ​​다르면 동형이 존재하지 않습니다. 물론 평등이 있다고 보장 할 수는 없습니다.

비 이형 그래프를 체로 훑어 볼 때 훨씬 더 유사한 유사한 휴리스틱이 많이 있습니다 (여기에 적용될 수 있음).

또한, 8! 오직 40320이므로, 모든 순열을 무차별 적으로 강제하는 것은 완전히 불가능하지 않습니다.