다른 그룹의 순열이 필요합니다

Question

저는 1에서 36까지의 숫자를 가지고 있습니다. 제가하려는 것은 그룹에 3 개의 그룹에 모든 숫자를 넣고 그룹의 모든 순열을 계산하는 것입니다.

각 그룹 .... 여기

이 예는 순열에 따라 하나 개 이상의 그룹으로 나타날 수 1 내지 36

개수에 12 수를 포함해야

Permutation 1 
Group 1: 1,2,3,4,5,6,7,8,9,10,11,12 
Group 2: 13,14,15,16,17,18,19,20,21,22,23,24 
Group 3: 25,26,27,28,29,30,31,32,33,34,35,36 

Permutation 2 
Group 1: 1,2,3,4,5,6,7,8,9,10,11,13 
Group 2: 12,14,15,16,17,18,19,20,21,22,23,24 
Group 3: 25,26,27,28,29,30,31,32,33,34,35,36 

Permutation 3 
Group 1: 1,2,3,4,5,6,7,8,9,10,11,14 
Group 2: 12,11,15,16,17,18,19,20,21,22,23,24 
Group 3: 25,26,27,28,29,30,31,32,33,34,35,36 

그것들은 세 가지 예입니다. 나는 수백만/수십억이 더 많을 것으로 기대합니다.

Answer 1

다음 분석은 그룹의 순서가 중요하다고 가정합니다. 즉, 숫자가 1, 2, 3이면 그룹화 [{1}, {2}, {3}]은 그룹화 [{3}, {2}, {1}]과 다릅니다 (사실, 이 숫자 세트).

귀하의 경우 어떻게 진행합니까? 먼저, 첫 번째 그룹을 선택해야합니다. 36 가지가 있는데 12 가지 방법이 있습니다. (36!)/[(12!) (24!)] = 1,251,677,700 가지가 있습니다. 그런 다음 두 번째 그룹을 선택해야합니다. 이것을 할 수있는 방법은 24 가지가 있으며, (24!)/[(12!) (12!)] = 2,704,156 방식이 있습니다. 두 번째 선택은 이미 첫 번째 조건에 맞추어 졌기 때문에 세 그룹에 숫자를 곱하여 총 수를 얻을 수 있습니다. 36 풀에서 12 개의 3 개의 동등한 그룹을 선택하는 방법의 총 수는 3,384,731,762,521,200입니다. 8 비트 바이트를 사용하여 숫자를 표현한 경우 모든 목록을 저장하려면 적어도 3 ~ 5 기가 바이트가 필요합니다 (음, 목록의 크기는 36 바이트가 될 것이므로 ~ 108 펜타 바이트 정도가 될 것입니다). 이것은 많은 양의 데이터를 생성하는 데 약간의 시간이 걸리므로 저장할 디스크 공간이 적기 때문에이 사실을 알고 있어야합니다.

실제로 이것을 구현하는 것은 그리 심각하지 않습니다. 그러나, 나는 그것이 가능하다면 당신이 SQL에서 이것을 구현하는 데 과도한 어려움을 겪을 것이라고 생각한다. Pure SQL에는 n^2 개 항목 이상을 반환하는 연산 (간단한 크로스 조인)이 없으므로 엄청난 수의 결과를 얻으려면 많은 수의 조인이 필요합니다. 게다가 순수 SQL은 일반적인 재귀를 수행 할 능력이 없으므로 다양한 수의 조인을 수행 할 수 없으므로 가능한 한 프로 시저를 일반화하지 않습니다.

절차 언어를 사용하여 그룹을 생성 한 다음 그룹화를 데이터베이스에 쓸 수 있습니다. 이것이 당신이 무엇인지 알지 못합니다.

n = 36 

group1[1...12] = [] 
group2[1...12] = [] 
group3[1...12] = [] 

function Choose(input[1...n], m, minIndex, group) 

    if minIndex + m > n + 1 then 
     return 

    if m = 0 then 

     if group = group1 then 
      Choose(input[1...n], 12, 1, group2) 

     else if group = group2 then 
      group3[1...12] = input[1...12] 
      print group1, group2, group3 

    for i = i to n do 

     group[12 - m + 1] = input[i] 
     Choose(input[1 ... i - 1].input[i + 1 ... n], m - 1, i, group) 

당신이 호출 할 때이 같은 Choose([1...36], 12, 1, group1) 그것이 무엇을하는 것은 그 시점에서 길이 (12)의 가능한 모든 명령 시퀀스, m = 0 및 그룹 = 그룹 1과 그룹 1을 작성, 그래서 전화 Choose([?], 12, 1, group2) 모든 위해 (만들어 가능한 그룹 1 선택, 따라서 ?). 그러면 group2에 대해 길이가 12 인 나머지 모든 순서가 지정된 하위 시퀀스가 ​​선택되며,이 시점에서 m = 0이고 이제 group = group2가됩니다. 이제 나머지 항목에 group3을 안전하게 할당 할 수 있습니다 (group1 및 group2를 선택한 후에 group3을 선택하는 방법은 하나뿐입니다).

우리는 재귀 호출 (minIdx)을 찾기 시작할 색인을 전파함으로써 만 순서화 된 하위 시퀀스를 가져옵니다. 그룹 내에서 순서가 중요하지 않으므로 동일한 12 개 항목의 순열을 피하기 위해 순서가 지정된 하위 시퀀스를 가져옵니다.

루프에서 Choose에 대한 각 재귀 호출은 하나의 요소가 제거 된 input을 전달합니다. 즉, 고려중인 그룹에 방금 추가 된 요소입니다.

우리는 minIndex + m > n + 1을 확인하고,이 경우 입력에 너무 많은 항목을 건너 뛰었으므로 현재 그룹에 12 개의 항목을 채울 수 있기 때문에 재귀를 일찍 중단합니다 (순서 지정 할 하위 순서 선택). .

12/36/3 그룹의 가정을 프로그램의 논리에 하드 코딩 한 것을 알 수 있습니다. 이는 간결하고 명료하게하기 위해서였습니다. 입력 크기 N과 양식 할 그룹 수 k에서 매개 변수화 할 수 없기 때문이 아닙니다. 이렇게하려면 그룹 배열 (각각 N/k 크기의 k 그룹)을 만든 다음 12 대신 N/k로 Choose을 호출하고 if/then/else 대신 select/switch case 문을 사용해야합니다 다시 Choose 여부를 결정하거나 인쇄하십시오. 그러나 그러한 세부 사항은 운동으로 남겨 둘 수 있습니다.