Discussion :

[River974]

Bonjour,

je commence à me mettre à Python et j'ai un petit problème algorithmique dont je n'arrive pas à me défaire.
Je dois créer une fonction prenant une liste en argument et un certain nombre de trou possible, le résultat est une liste contenant toutes les listes faisable avec les trous.

Par exemple si la list = [1, 2, 3, 4, 5] et le nombre de trou = 1 le résultat est:
[[1, 2, 3, 4],
[1, 2, 3, 5],
[1, 2, 4, 5],
[1, 3, 4, 5],
[2, 3, 4, 5]]

si le nombre de trou est de 2 alors le résultat est:
[[1, 2, 3],
[1, 2, 4],
[1, 2, 5],
[1, 3, 4],
[1, 3, 5],
[1, 4, 5],
[2, 3, 4],
[2, 3, 5],
[2, 4, 5],
[3, 4, 5]]

J'ai réussi à faire une fonction qui marche de manière récursive mais elle est vraiment lente et contient des doublons que je dois retirer ensuite, ce qui gache encore plus les performances, et je ne vois pas comment le faire de manière itérative.
Ca me semble assez basique mais je n'ai pas trouvé de fonction déjà implémenté et optimisé (car je peux avoir des listes et un nombre de trous très grand).
Connaissez vous un module qui fasse cela ?

[fred1599]

Avec le module itertools et le générateur combinations, ça va tout seul

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
>>> l = list(map(str, [1, 2, 3, 4, 5]))
>>> for val in combinations(l, len(l)-1):
...     print(' '.join(val))
... 
1 2 3 4
1 2 3 5
1 2 4 5
1 3 4 5
2 3 4 5

Il y a plus qu'à créer la fonction pour généraliser ma démonstration, quelque soit la longueur de liste et le nombre de trous.

[River974]

C'est exactement ça, merci beaucoup !
Et pourquoi j'avais lu exactement cette page