Besoin d'une permutation différente des groupes de nombres

Question

J'ai des nombres de 1 à 36. Ce que j'essaie de faire est de mettre tous ces nombres dans trois groupes et élabore toutes les différentes permutations de groupes.

Chaque groupe doit contenir 12 numéros, de 1 à 36

Un certain nombre ne peuvent pas apparaître dans plus d'un groupe, par permutation

Voici un exemple ....

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 

Ce sont trois exemples, je m'attendrais à ce qu'il y ait des millions/milliards de plus

Answer 1

L'analyse qui suit suppose que l'ordre des groupes est important - c'est-à-dire, si les nombres étaient 1, 2, 3 alors le groupement [{1}, {2}, {3}] est distinct du groupement [{3}, {2}, {1}] (en effet, il y a six groupements distincts cet ensemble de nombres).

Dans votre cas, comment procédons-nous? Eh bien, nous devons d'abord choisir le premier groupe. Il y a 36 choisir 12 façons de le faire, ou (36!)/[(12!) (24!)] = 1,251,677,700 façons. Nous devons ensuite choisir le deuxième groupe. Il y a 24 choix de 12 manières de faire ceci, ou (24!)/[(12!) (12!)] = 2.704.156 manières. Puisque le second choix est déjà conditionné par le premier, nous pouvons obtenir le nombre total de façons de prendre les trois groupes en multipliant les nombres; le nombre total de façons de choisir trois groupes égaux de 12 parmi un groupe de 36 est de 3 384 731 762 521 200. Si vous représentiez des nombres utilisant des octets de 8 bits alors stocker chaque liste prendrait au moins ~ 3 pentaoctets (bien, je suppose que la taille de la liste serait de 36 octets, donc plus de ~ 108 pentaoctets). C'est beaucoup de données et il faudra un certain temps pour générer et pas peu d'espace disque pour stocker, alors soyez conscient de cela.

Pour réellement mettre en œuvre ce n'est pas si terrible. Cependant, je pense que vous allez avoir des difficultés indues à implémenter ceci en SQL, si c'est possible du tout. Pure SQL n'a pas d'opérations qui renvoient plus de n^2 entrées (pour une simple jointure croisée) et donc obtenir un tel nombre de résultats nécessiterait un grand nombre de jointures. De plus, il ne me semble pas possible de généraliser la procédure puisque le SQL pur n'a pas la capacité de faire de la récursion générale et ne peut donc pas faire un nombre variable de jointures.

Vous pouvez utiliser un langage procédural pour générer les regroupements, puis écrire les regroupements dans une base de données. Je ne sais pas si c'est ce que tu cherches.

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) 

Lorsque vous appelez cela comme Choose([1...36], 12, 1, group1) ce qu'il fait est remplir groupe1 avec toutes les séquences possibles ordonnés de longueur 12. A ce moment-là, m = 0 et le groupe = group1, de sorte que l'appel Choose([?], 12, 1, group2) est fait (pour chaque choix possible de group1, d'où le ?). Cela va choisir toutes les sous-séquences ordonnées restantes de longueur 12 pour group2, à quel point m = 0 et maintenant group = group2. Nous pouvons maintenant attribuer group3 en toute sécurité aux entrées restantes (il n'y a qu'une seule façon de choisir group3 après avoir choisi group1 et group2).

Nous prenons des sous-séquences ordonnées uniquement en propageant l'index sur lequel commencer à rechercher l'appel récursif (minIdx). Nous prenons des sous-séquences ordonnées pour éviter d'obtenir des permutations du même ensemble de 12 items (puisque l'ordre n'a pas d'importance au sein d'un groupe).

Chaque appel récursif à Choose dans la boucle passe input avec un élément supprimé: précisément l'élément qui vient d'être ajouté au groupe considéré.

Nous vérifions minIndex + m > n + 1 et arrêtons la récursion anticipée car, dans ce cas, nous avons omis trop d'éléments dans l'entrée pour pouvoir remplir le groupe actuel avec 12 items (en choisissant la sous-séquence à commander) .

Vous remarquerez que j'ai codé en dur l'hypothèse des groupes 12/36/3 dans la logique du programme. Cela a été fait pour la brièveté et la clarté, non pas parce que vous ne pouvez pas le paramétrer dans la taille d'entrée N et le nombre de groupes k à former. Pour ce faire, vous devez créer un tableau de groupes (k groupes de taille N/k chacun), puis appeler Choose avec N/k au lieu de 12 et utiliser une instruction select/switch case au lieu de if/then/else pour déterminer si Choose à nouveau ou imprimer. Mais ces détails peuvent être laissés comme un exercice.