Je viens de passer un test python, et j’ai échoué du premier coup. J’ai donc décidé de résoudre à nouveau ce défi. Finalement, c’est plus simple que ce à quoi je m’attendais. Pourtant, j’avais bien écrit mon résonnement dans les notes du test. Bon certes cela ne résout pas l’équation, mais l’idée était là.
Voici donc, mon explication pour savoir compter et à construire facilement combien de paires est-il possible de former à partir d’un nombre de participants.
Contexte
Ces derniers jours, j’ai dû répondre à quelques questions techniques pour un travail que je trouvais intéressant. Le problème concernait un outil qui devait former les paires pour les duels d’un tournoi d’échecs, sachant que l’ordre des adversaires dans une paire n’a pas d’importance. L’exemple est le suivant, supposons que vous ayez un tableau avec 4 éléments simples :
["A", "B", "C", "D"]
Le but de l’exercice est de déterminer combien (ou quelles) combinaisons possibles vous pouvez former avec ces éléments sans les répéter, car c’est une caractéristique qui peut être nécessaire pour calculer le nombre de combinaisons possibles que vous pouvez construire pour un jeu comme les échecs, par exemple AC
est identique à CA
, ce serait donc une seule combinaison. L’image suivante représente les combinaisons possibles que vous pouvez construire avec le tableau donné :
Dans ce cas, le nombre de paires possibles avec 4 éléments est de 6. C’est tout ce que nous avons besoin de calculer, juste le nombre de paires possibles à partir d’un seul entier. L’idée serait donc de créer une fonction qui renvoie ce nombre comme suit :
print("count(4) ==> " + str(count(4))) # Return: 6
Implémentation
La logique pour résoudre ce problème est en fait simple (et elle sera plus simple en code) :
- Itérer sur le nombre d’éléments sauf le dernier. Par exemple, avec 4 éléments, la première boucle ne doit être itérée que 3 fois. Dans ce cas, l’indice d’itération commence à 0.
- À l’intérieur de la première boucle, une autre boucle itérera à nouveau sur le nombre d’éléments, mais ignorera tous les éléments dont l’indice est inférieur à l’indice d’itération de la première boucle plus un. Dans cette boucle, vous devriez pouvoir soit construire la paire possible avec les deux index, soit ajouter un nombre à un compteur qui ajoute la nouvelle paire possible.
Si vous avez besoin de savoir quelles sont les paires qui peuvent être formées en utilisant la logique mentionnée, l’extrait de code suivant devrait faire l’affaire :
def possible_player_pairs(array) : results = [] for i in range(0, len(array) - 1): for j in range(i + 1, len(array)): results.append(array[i] + array[j]) return results possible_player_pairs(["A", "B", "C", "D"]); # Returns: ["AB", "AC", "AD", "BC", "BD", "CD"]
Toutefois, si, comme moi, vous avez juste besoin du nombre de combinaisons possibles, le code suivant fonctionne :
def count_player_pairs(n) : count = 0 for i in range(0, n - 1): for j in range(i + 1, n): count = count + 1 return count count_player_pairs(4); # Returns: 6 count_player_pairs(10); # Returns: 45
Logique mathématique
Durant mes recherches, j’ai tapé sur google 0 1 1 3 6 10
pour voir, car il me semblait déjà avoir vu ce nombre quelque part. Et effectivement, En arithmétique, un nombre triangulaire est un cas particulier de nombre polygonal.
J’ai vu cette formule mathématique au secondaire. Il faut dire que cela date quand même un peu. Mais comme quoi, que les mathématiques que nous apprenons à l’école peuvent toujours nous servir durant notre vie, encore plus en programmation. Donc, voilà, le nombre triangulaire pour plus de détail technique au besoin.
Conclusion
Voilà, une solution simple, même si elle est un peu complexe à comprendre au début. Comme on dit, nous devons toujours apprendre chaque jour. C’est pour cela que j’ai créé un petit dossier sur le git avec ces exemples. En plus de mettre quelques petits tests unitaires pour tester cette solution. github.com/alfreddagenais/kilukru-dev-articles/python/players_pairs_counting
Bon codage ❤️ ! Et je vous invite à lire la 2e partie de ce test technique pour un autre algorithme vraiment intéressant.