récursif

Le
cf29
Bonjour,

Je suis nouveau venu dans le monde de Python.

Comment écrire une fonction qui remplirait une liste par une liste de
nombres en examinant toutes les possibilités ?
Par exemple dans le cas d'une liste de 3 nombres choisis parmi 4
[0,1,2,3], sans doublons, le résultat serait :
[0,1,2]
[0,1,3]
[0,2,3]
[1,2,3]
Vidéos High-Tech et Jeu Vidéo
Téléchargements
Vos réponses
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
Méta-MCI \(MVP\)
Le #663110
Bonsoir !

Tu as oublié quelques combinaisons, liées à la permutation des éléments.
Voici un code qui corrige cela :

def moins(l,*v):
import copy
lret=copy.copy(l)
for i in v:
lret.remove(i)
return lret

l=[0,1,2,3]
print [[a,b,c] for a in l for b in moins(l,a) for c in moins(l,a,b)]


@-salutations
--
Michel Claveau
Pierre Maurette
Le #663109
Bonjour,


Bonjour,

Je suis nouveau venu dans le monde de Python.

Comment écrire une fonction qui remplirait une liste par une liste de
nombres en examinant toutes les possibilités ?
Par exemple dans le cas d'une liste de 3 nombres choisis parmi 4
[0,1,2,3], sans doublons, le résultat serait :
[0,1,2]
[0,1,3]
[0,2,3]
[1,2,3]


Malgré le titre, la récursivité ne me semble pas s'imposer. Mais elle
est facile à introduire. Voilà un bout de code qui semble fonctionner.
Modifiez origListe (non trié et avec doublons, pour voir le
comportement). Et subListSize, entre 1 et len(origListe), la taille des
"sous-listes".


def minusOneListe(listes):
return [x for L in listes for x in [L[:i] + L[i + 1:] for i in
range(0, len(L))] if x not in locals()['_[1]']]

origListe = [10,11,13,15]
subListSize = 2

nIters = len(origListe) - subListSize
assert nIters >= 0 and subListSize > 0
print eval('sorted(' + 'minusOneListe(' * nIters + '[origListe])' + ')'
* nIters)

--
Pierre Maurette

cf29
Le #663108
print eval('sorted(' + 'minusOneListe(' * nIters + '[origListe])' + ')'
* nIters)


Merci Pierre mais j'apprends que sorted n'est pas défini.

Michel écrit: "Tu as oublié quelques combinaisons, liées à la
permutation des éléments."

Non, je n'ai rien oublié, c'est bien le résultat que je recherche
c'est une fonction différente.
Il s'agit en fait de :

def combinations(seq, n):
if n == 0:
yield []
else:
for i in xrange(len(seq)):
for cc in combinations(seq[i+1:], n-1):
yield [seq[i]]+cc

for c in combinations(range(4), 3):
print c

Cette fonction m'a été donnée mais je ne comprends pas vraiment la
syntaxe pour la modifier de façon à l'adapter à ma recherche.

Le problème de 5 dames que j'ai réalisé à http://www.cf29.com/design /dame5.php
Je voudrais trouver toutes les solutions possibles (il ne s'agit pas
du problème célèbre des 8 dames).
J'ai déjà fait une grosse partie du travail mais je n'arrive pas à
finaliser.

Comment vous y prendriez-vous ?
Voulez-vous voir mon code et me dire ce que je dois ajouter?

Pierre Maurette
Le #662891
print eval('sorted(' + 'minusOneListe(' * nIters + '[origListe])' + ')'
* nIters)


Merci Pierre mais j'apprends que sorted n'est pas défini.


A partir de 2.4
Vous pouvez remplacer la ligne du print par:

L = eval('minusOneListe(' * nIters + '[origListe]' + ')' * nIters)
L.sort()
print L

Attention, je me suis amusé à faire un truc "compact", mais ça peut
être calamiteux en performace. Pour des listes de N - 1 dans une liste
de N, c'est correct, pour des listes de 1 (ou 2, plutôt) dans une liste
de N, c'est très caca. Il faudrait changer d'approche pour des listes
en dessous de N / 2 dans une liste de N.

--
Pierre Maurette


Publicité
Poster une réponse
Anonyme