순열까지 하위 집합 컬렉션 비교

Question

배열 a[i][j]가 있습니다.요소는 char이며 집합 {1,...,8}의 하위 집합으로 해석됩니다(k번째 비트가 1인 경우 요소 k는 하위 집합에 있음).관련성이 없다고 생각하지만 모든 요소에는 정확히 4비트가 설정되어 있습니다.

모든 행 a[1][j]..a[n][j]는 {1,...,8}의 하위 집합 모음입니다.중복 행을 제거해야 합니다. 여기서 {1,...,8}의 순열을 통해 다른 행에서 하나를 얻을 수 있으면 두 행이 중복으로 간주됩니다.

예(0bxxxxxxxx는 이진수를 의미함):

0b11000000, 0b01100000, 0b00110000

다음의 중복입니다

0b00110000, 0b00011000, 0b00100100

전자는 순열을 적용하여 후자로부터 얻을 수 있기 때문입니다.

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

결과를 재정렬합니다.

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

당신의 도움을 주셔서 감사합니다.

Answer 1

모든 하위 집합에 2개의 요소가 있는 경우 이는 다음을 나타냅니다. 그래프 동형성, 그래프 가장자리를 나타내는 하위 집합이 있습니다.이것은 훨씬 더 일반적이므로(아마도 더 어려울 것임) 그래프 동형성을 해결하는 데 사용되는 경험적 방법을 살펴보고 여기에 적용되는지 확인하겠습니다.

동형을 저렴하게 배제할 수 있는 그래프-동형 휴리스틱이 많이 있습니다.특정 컬렉션의 경우 각 요소가 속한 하위 집합 수를 계산한 다음 정렬할 수 있습니다.귀하의 예에서 두 컬렉션 모두 [2,2,1,1,0,0,0,0]을 얻습니다.두 컬렉션의 정렬된 순서가 다르면 동형이 없습니다.물론 평등이 존재한다는 것을 보장하지는 않습니다.

비동형 그래프를 걸러내는 데 훨씬 더 나은 유사한 경험적 방법이 더 많이 있습니다(여기에 적용될 수도 있음).

게다가 8!40320에 불과하므로 모든 순열을 무차별 대입하는 것이 완전히 불가능하지는 않습니다.