Permutations et combinaisons
Faire UN programme itératif seulement qui trouve toutes les permutations d’un ensemble ensemble est impossible. Le nombre de boucles d’itérations dépend de l’ensemble. Mais un programme récursif résout le problème facilement.
####################################################
def perm1(lst):
if len(lst) == 0:
return []
elif len(lst) == 1:
return [lst]
else:
l = []
for i in range(len(lst)):
x = lst[i]
xs = lst[:i] + lst[i+1:]
for p in perm1(xs):
l.append([x] + p)
return l
data = list('abc')
print("perm1")
print("la réponse=",perm1(data))
La sortie :
perm1
la réponse= [['a', 'b', 'c'], ['a', 'c', 'b'], ['b', 'a', 'c'],
['b', 'c', 'a'], ['c', 'a', 'b'], ['c', 'b', 'a']]
####################################################
Pour comprendre ce qui se passe insérons des « print » un peu partout et ajout un « niveau » à chaque appel de la fonction récursive.
####################################################
Même code avec des « print » aux endroits stratégiques et une variable « niv »
def perm1(niv,lst):
print("niv=",niv,"début perm1 de ",lst)
if len(lst) == 0:
print("niv=",niv,"fin perm1 output= []")
return []
elif len(lst) == 1:
print("niv=",niv,"fin perm1 output=",[lst])
return [lst]
else:
l = []
for i in range(len(lst)):
x = lst[i]
xs = lst[:i] + lst[i+1:]
print("niv=",niv,"x=",x," xs=",xs)
for p in perm1(niv+1,xs):
l.append([x] + p)
print("niv=",niv,"fin perm1 output=",l)
return l
Réponse
perm1
niv= 0 début perm1 de ['a', 'b', 'c']
niv= 0 x= a xs= ['b', 'c']
. niv= 1 début perm1 de ['b', 'c']
.
. niv= 1 x= b xs= ['c']
. niv= 2 début perm1 de ['c']
. niv= 2 fin perm1 output= [['c']]
.
. niv= 1 x= c xs= ['b']
. niv= 2 début perm1 de ['b']
. niv= 2 fin perm1 output= [['b']]
. niv= 1 fin perm1 output= [['b', 'c'], ['c', 'b']]
.
niv= 0 x= b xs= ['a', 'c']
. niv= 1 début perm1 de ['a', 'c']
.
. niv= 1 x= a xs= ['c']
. niv= 2 début perm1 de ['c']
. niv= 2 fin perm1 output= [['c']]
.
. niv= 1 x= c xs= ['a']
. niv= 2 début perm1 de ['a']
. niv= 2 fin perm1 output= [['a']]
. niv= 1 fin perm1 output= [['a', 'c'], ['c', 'a']]
.
niv= 0 x= c xs= ['a', 'b']
. niv= 1 début perm1 de ['a', 'b']
.
. niv= 1 x= a xs= ['b']
. niv= 2 début perm1 de ['b']
. niv= 2 fin perm1 output= [['b']]
.
. niv= 1 x= b xs= ['a']
. niv= 2 début perm1 de ['a']
. niv= 2 fin perm1 output= [['a']]
. niv= 1 fin perm1 output= [['a', 'b'], ['b', 'a']]
niv= 0 fin perm1 output= [['a', 'b', 'c'], ['a', 'c', 'b'], ['b', 'a', 'c'], ['b', 'c', 'a'],
['c', 'a', 'b'], ['c', 'b', 'a']]
la réponse= [['a', 'b', 'c'], ['a', 'c', 'b'], ['b', 'a', 'c'], ['b', 'c', 'a'], ['c', 'a', 'b'], ['c', 'b', 'a']]
####################################################
Maintenant pour les combinaisons le code est très court et élusif.
def combinaisons(ensemble):
if len(ensemble) == 0:
return [[]]
combos = []
for combo in combinaisons(ensemble[1:]):
combos += [combo, combo + [ensemble[0]]]
return combos
# test
nombres = [1, 2, 3, 4]
reponse = combinaisons(nombres)
print("Combinaisons de ", nombres)
print("réponse")
print(reponse)
La réponse
Combinaisons de [1, 2, 3, 4]
réponse
[[], [1], [2], [2, 1], [3], [3, 1], [3, 2], [3, 2, 1], [4], [4, 1],
[4, 2], [4, 2, 1], [4, 3], [4, 3, 1], [4, 3, 2], [4, 3, 2, 1]]
Les 16 sous ensembles, comme prévu.
####################################################
Même code avec des « print » aux endroits stratégiques et une variable « niv »
def combinaisons(niv,ensemble):
print("niv=",niv,"début ensemble=",ensemble)
if len(ensemble) == 0:
print("niv=",niv,"sortie: [[]]")
return [[]]
combos = []
appelRecursif = combinaisons(niv+1,ensemble[1:])
for combo in appelRecursif:
combos += [combo, combo + [ensemble[0]]]
print("niv=",niv, "rajoute=",[combo, combo + [ensemble[0]]])
print("niv=", niv, "sortie=", combos)
return combos
# test
nombres = [1, 2, 3, 4]
reponse = combinaisons(0,nombres)
print("Combinaisons de ", nombres)
print("réponse")
print(reponse)
La réponse
niv= 0 début ensemble= [1, 2, 3, 4]
------niv= 1 début ensemble= [2, 3, 4]
------------niv= 2 début ensemble= [3, 4]
------------------niv= 3 début ensemble= [4]
------------------------niv= 4 début ensemble= []
------------------------niv= 4 sortie: [[]]
------------------niv= 3 rajoute= [[], [4]]
------------------niv= 3 sortie= [[], [4]]
------------niv= 2 rajoute= [[], [3]]
------------niv= 2 rajoute= [[4], [4, 3]]
------------niv= 2 sortie= [[], [3], [4], [4, 3]]
------niv= 1 rajoute= [[], [2]]
------niv= 1 rajoute= [[3], [3, 2]]
------niv= 1 rajoute= [[4], [4, 2]]
------niv= 1 rajoute= [[4, 3], [4, 3, 2]]
------niv= 1 sortie= [[], [2], [3], [3, 2], [4], [4, 2], [4, 3], [4, 3, 2]]
niv= 0 rajoute= [[], [1]]
niv= 0 rajoute= [[2], [2, 1]]
niv= 0 rajoute= [[3], [3, 1]]
niv= 0 rajoute= [[3, 2], [3, 2, 1]]
niv= 0 rajoute= [[4], [4, 1]]
niv= 0 rajoute= [[4, 2], [4, 2, 1]]
niv= 0 rajoute= [[4, 3], [4, 3, 1]]
niv= 0 rajoute= [[4, 3, 2], [4, 3, 2, 1]]
niv= 0 sortie= [[], [1], [2], [2, 1], [3], [3, 1], [3, 2], [3, 2, 1], [4], [4, 1], [4, 2],
[4, 2, 1], [4, 3], [4, 3, 1], [4, 3, 2], [4, 3, 2, 1]]
Combinaisons de [1, 2, 3, 4]
réponse
[[], [1], [2], [2, 1], [3], [3, 1], [3, 2], [3, 2, 1], [4], [4, 1],
[4, 2], [4, 2, 1], [4, 3], [4, 3, 1], [4, 3, 2], [4, 3, 2, 1]]
Les 16 sous ensembles, comme prévu.
Process finished with exit code 0
####################################################
####################################################