Assurez-vous que les groupes de quatre 3 tuples ont 9 nombres uniques

Question

Remarque: Je sais que les chiffres sont arbitraires, mais ce problème sur cette taille a des implications pratiques. Il s'agit d'un problème d'algorithme appliqué.

Supposons que vous ayez 200 bacs. Chaque bac serait très heureux d'avoir la séquence entière: 1, 2, 3, 4, 5, 6, 7, 8, 9. Et l'algorithme serait très heureux si tous les bacs l'obtiennent.

L'algorithme est autorisé à choisir quatre 3 tuples parmi une collection de 800 3 toples. Il en affectera 4 à chaque bac. Ainsi, chaque poubelle aura quatre 3 tuples qui leur ont été attribués. Ces 3 toples ont les propriétés suivantes:

1. Ils sont générés par pseudo-aléatoirement en même temps en tant que collection de 800 3 toples.
2. Chaque numéro dans un 3-Tuple généré est unique. Par exemple, (1, 1, 2) et (7, 4, 4) sont impossibles mais (1, 2, 3) et (8, 2, 9) sont possibles.
3. Chaque valeur dans le 3-Tuple ne peut être qu'un nombre de 1 à 9. Par exemple, (10, 3, 15) est un tuple impossible. Le 3 pourrait se produire, mais 10 et 15 ne pouvaient pas.

Un corollaire du point 1 est qu'il pourrait être le cas que certains entiers se produisent moins que la quantité de bacs qui existent. Dans un tel cas, l'application serait très heureuse si de nombreux bacs obtiennent une séquence numérique de 1 à 9 et que les autres bacs se rapprochent le plus possible d'une telle séquence. Par exemple, supposons que le nombre 9 ait été généré au hasard en 180 3-toples, alors au moins 20 bacs n'obtiendront pas le numéro 9, mais ils, espérons-le, devraient pouvoir obtenir les entiers 1 à 8.

Voici un exemple de 2 bacs et 8 3 toples. Les chiffres suivants sont générés par pseudo-aléatoire.

(3, 8, 2) 
(2, 1, 5) 
(2, 7, 8) 
(7, 8, 5)
(7, 8, 4)
(7, 5, 8)
(7, 9, 5)
(4, 7, 3)

Les attribuer à deux bacs aussi optimaux que possible par les exigences donne:

Bin 1 - Sequence: 1, 2, 3, 4, 5, 7, 8, 9
(2, 1, 5)
(4, 7, 3)
(7, 9, 5)
(7, 8, 5)

Bin 2 - Sequence: 2, 3, 4, 5, 7, 8
(2, 7, 8) 
(7, 8, 4)
(7, 5, 8)
(3, 8, 2)

Remarque: Dans cet exemple particulier, il n'y a pas de 6. Il y a un 1 et un 9. Cela signifie que le 1 et le 9 vont automatiquement au bac 1. L'entier 6, eh bien il n'est tout simplement pas là, donc il ne peut pas être attribué à un bac.

Ma première question: Concevez un algorithme qui assure la solution la plus optimale.

Ma deuxième question: Une version généralisée ou analogue est-elle connue comme un certain problème ou un certain domaine en mathématiques?

Je suppose que ce problème est une variante du problème de couverture de set. Cependant, au lieu de couvrir un univers, 200 «univers» doivent être couverts. Ou dit d'une autre manière: l'univers doit être couvert 200 fois de manière à ce que la couverture puisse être divisée en 200 groupes de quatre 3 tuples.