제약 조건으로 순열 세트를 찾습니다

Question

나는 n^2 숫자와 n bin 세트가 있습니다. 각 빈에는 할당 된 세트에서 N 숫자가 있어야합니다. 내가 직면하고있는 문제는 숫자를 쓰레기에 매핑하고 제약 조건을 만족시키는 일련의 분포 세트를 찾는 것입니다. 각 숫자 쌍은 동일한 빈을 한 번만 공유 할 수 있습니다.

분포는 NXN 행렬로 멋지게 표현 될 수 있으며, 여기서 각 행은 빈을 나타냅니다. 그런 다음 문제는 매트릭스 요소의 순열 세트를 찾는 것입니다. 각 숫자 쌍은 동일한 행을 한 번만 공유합니다. 어떤 행인지는 관련이 없습니다. 두 숫자만이 같은 숫자에 할당되었습니다.

n = 8에 대한 제약 조건을 충족하는 3 개의 순열 세트 세트 :

 0  1  2  3  4  5  6  7
 8  9 10 11 12 13 14 15
16 17 18 19 20 21 22 23
24 25 26 27 28 29 30 31
32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47
48 49 50 51 52 53 54 55
56 57 58 59 60 61 62 63

 0  8 16 24 32 40 48 56
 1  9 17 25 33 41 49 57
 2 10 18 26 34 42 50 58
 3 11 19 27 35 43 51 59
 4 12 20 28 36 44 52 60
 5 13 21 29 37 45 53 61
 6 14 22 30 38 46 54 62
 7 15 23 31 39 47 55 63

 0  9 18 27 36 45 54 63
 1 10 19 28 37 46 55 56
 2 11 20 29 38 47 48 57
 3 12 21 30 39 40 49 58
 4 13 22 31 32 41 50 59
 5 14 23 24 33 42 51 60
 6 15 16 25 34 43 52 61
 7  8 17 26 35 44 53 62

위의 세트에 속하지 않는 순열 :

 0 10 20 30 32 42 52 62
 1 11 21 31 33 43 53 63
 2 12 22 24 34 44 54 56
 3 13 23 25 35 45 55 57
 4 14 16 26 36 46 48 58
 5 15 17 27 37 47 49 59
 6  8 18 28 38 40 50 60
 7  9 19 29 39 41 51 61

예를 들어 두 번째 순열과의 다중 충돌로 인해 예를 들어 숫자 0과 32를 한 행으로 짝을 이루기 때문입니다.

---

3 개의 열거는 쉽고, 임의 순열 1 개, 전달 및 행이 이전 행렬의 대각선으로 만들어지는 행렬로 구성됩니다.

그래도 더 많은 것으로 구성된 세트를 제작하는 방법을 찾을 수 없습니다. 매우 복잡한 문제이거나 끔찍한 솔루션의 간단한 문제인 것 같습니다. 어느 쪽이든 누군가가 n = 8 사례에 대해 합리적인 시간에 그것을 해결하는 방법이 있거나 문제의 적절한 학업 이름을 식별하는 방법이 있으므로 Google에 대해 감사 할 수 있습니다.

유용한 것이 무엇인지 궁금한 경우, 8 개의 버퍼가있는 크로스바 스위치를위한 스케줄링 알고리즘을 찾고 있는데, 이는 64 개의 목적지로 트래픽을 제공합니다. 스케줄링 알고리즘 의이 부분은 입력 트래픽이 불가지론이며, 여러 개의 하드 유용 대상-버퍼 매핑 사이를 주기적으로 전환합니다. 목표는 각 대상 주소 쌍이 사이클링 기간에 한 번만 동일한 버퍼에 대해 경쟁하고 그 기간의 길이를 극대화하는 것입니다. 다시 말해, 각 주소 쌍이 가능한 한 거의 거의 동일한 버퍼와 경쟁하도록합니다.

---

편집하다:

여기에 내가 가진 코드가 있습니다.암호

그것은 탐욕스럽고, 일반적으로 세 번째 순열을 찾은 후에 종료됩니다. 그러나 문제를 만족시키는 적어도 N 순열 세트가 있어야합니다.

대안은 순열 I가 최대 순열 수로 구성된 솔루션의 일부인지 확인하기 위해 순열 (I+1..N)을 찾는 순열을 선택해야합니다. 이는 각 단계에서 확인하기 위해 모든 순열을 열거 해야하는데, 이는 엄청나게 비싸다.

Answer 1

당신이 원하는 것은 a 조합 블록 설계. 링크 된 페이지의 명명법을 사용하면 최대 k의 크기 설계 (n^2, n, 1)를 원합니다. 이것은 명명법을 사용하여 N (n+1) 순열을 제공합니다. 이것은 계산 된 인수에 의해 가능한 최대 이론적으로 가능한 것입니다 (V, K 및 Lambda에서 B를 파생시키는 기사의 설명 참조). 이러한 설계는 아핀 평면을 사용하여 일부 Prime P 및 Integer K의 N = P^K에 대해 존재합니다. 존재하는 유일한 아파트 평면은이 크기입니다. 따라서 N을 선택할 수 있다면이 답변으로 충분할 것입니다.

그러나 이론적으로 가능한 최대 순열 대신에 많은 수를 찾고 싶다면 (주어진 n^2에 대해 가장 많이 할 수있는 것),이 객체에 대한 연구가 무엇인지 잘 모르겠습니다.

Answer 2

64 x 64 x 8 배열 : bool forbidden [i] [j] [k] 쌍 (i, j)이 행 K에 나타 났는지 여부를 나타냅니다. 행 K에서 쌍 (i, j)을 사용할 때 마다이 배열의 관련 값을 하나로 설정합니다. i <j 인이 배열의 절반 만 사용합니다.

새로운 순열을 구성하려면 멤버 0을 시도한 후 시작하여 금지되지 않은 금지 된 [0] [J] [0]의 7 개 이상을 확인하십시오. 7 개의 왼쪽이 없으면 점점을 높이고 다시 시도하십시오. 나머지 행을 작성하려면 반복하십시오. 이 전체 프로세스를 반복하여 전체 NXN 순열을 채우십시오.

이것을 구현할 때 생각 해낼 수 있어야 할 최적화가있을 것입니다. 그러나 이것은 꽤 잘 작동해야합니다.

Answer 3

아마도 문제를 그래프 이론으로 재구성 할 수 있습니다. 예를 들어, N × N 정점이있는 완전한 그래프로 시작합니다. 각 단계에서 그래프를 n-n-cliques로 분할 한 다음 사용 된 모든 모서리를 제거합니다.

이 n = 8의 경우, K64에는 64 × 63/2 = 2016 모서리가 있고 64 명의 K8이 1792 개의 모서리가 있으므로 문제가 있습니다. 5월 불가능하지 않습니다 :-)

Answer 4

숫자가 부족하기 때문에 탐욕스러운 스타일이 작동하지 않습니다.

제약 조건을 위반하기 전에 63 개 이상의 순열이있을 수 없다는 것을 쉽게 알 수 있습니다. 64 일에는 숫자 중 하나 이상을 이미 짝을 이루어 짝을 이루어야합니다. 비둘기 구멍 원리.

실제로, 당신이 앞에서 제안한 금지 된 쌍의 테이블을 사용하는 경우, 당신은 다 떨어지기 전에 최대 N+1 = 9 순열 만 가능하다는 것을 알 수 있습니다. 테이블에는 n^2 x (n^2-1)/2 = 2016 비 중복 제약 조건이 있으며, 각각의 새로운 순열은 n x (n 선택 2) = 28 개의 새로운 페어링을 생성합니다. 따라서 모든 페어링은 2016/28 = 9 순열 후에 사용됩니다. 순열이 거의 없다는 것을 깨닫는 것이 문제를 해결하는 열쇠라는 것을 깨닫는 것 같습니다.

N = 0 ... N-1과 같은 N 순열 목록을 생성 할 수 있습니다.

A_ij = (i * N + j + j * n * N) mod N^2

각 순열의 열을 이동시켜 새로운 순열을 생성합니다. N 번째 순열의 상단 행은 N-1 순열의 대각선입니다. 편집 : 죄송합니다 ... N이 프라임 일 때만 작동하는 것 같습니다.

이것은 매트릭스를 전송하여 얻을 수있는 마지막 순열 하나를 놓치고 있습니다.

A_ij = j * N + i