À la recherche d'un algorithme de «combinaison Domino»
-
18-09-2019 - |
Question
Je vais terminer mon apprentissage en tant que codeur et j'ai eu un joli projet J2ME sur lequel travailler, mais je dois admettre que je ne suis pas si bon avec les algorithmes mathématiques que j'aimerais être.
Mon problème est de créer toutes les «paires domino» possibles à partir d'un ensemble donné de valeurs. Par exemple: les valeurs possibles vont de 0 à 6. Imaginez maintenant certains jetons domino avec ces valeurs. La sortie doit alors être quelque chose comme ceci:
00
01
02
03
04
05
06
11
12
13
...
Chaque paire n'apparaît qu'une seule fois mais les paires avec deux valeurs égales sont possibles.
J'ai déjà recherché ce problème, mais soit je n'ai pas trouvé de solution pour ce problème particulier, soit je ne comprenais pas vraiment le fonctionnement des algorithmes.
J'apprécierais vraiment toutes les explications et algorithmes. N'hésitez pas à publier également des solutions alternatives. Je préférerais non seulement avoir une solution, mais aussi le comprendre;)
La solution
Pseudo Code:
for i from 0 to n inclusive
for j from i to n inclusive
output i,j
Le point important est que la deuxième boucle ne commence pas de zéro. Cela signifie que nous n'avons pas à tester si un Domino a déjà été utilisé. Nous savons que tous les dominos produits à l'aide de cet algorithme sont uniques en raison de la façon dont l'algorithme est construit.