Partage
  • Partager sur Facebook
  • Partager sur Twitter

[exercice] Générer tous les anagrammes

zozor rozzo rozoz roozz ...

    19 juillet 2010 à 12:38:33

    Bonjour


    Allez encore un petit, sans doute le dernier pour ces vacances.

    Un exemple d'anagramme du mot ZOZOR est ZROOZ.

    Plus précisément, un anagramme d'un mot consiste à créer un nouveau mot en utilisant les mêmes lettres (y compris les répétitions) mais en les plaçant différemment. Le mot mélangé peut ne pas être dans le dictionnaire, ce n'est pas le problème.

    On vous demande d'écrire un code Python qui soit capable de générer tous les anagrammes d'un "mot" donné. Par exemple, les anagrammes du mot ZOZOR sont les 30 mots suivants :


    RZZOO
    RZOZO
    RZOOZ
    ROZZO
    ROZOZ
    ROOZZ
    ZRZOO
    ZROZO
    ZROOZ
    ZZROO
    ZZORO
    ZZOOR
    ZORZO
    ZOROZ
    ZOZRO
    ZOZOR
    ZOORZ
    ZOOZR
    ORZZO
    ORZOZ
    OROZZ
    OZRZO
    OZROZ
    OZZRO
    OZZOR
    OZORZ
    OZOZR
    OORZZ
    OOZRZ
    OOZZR




    Avant de vous lancer dans du code en dur, assurez-vous que vous savez générer à la main tous les anagrammes de ZOZOR (par exemple), autrement dit que vous avez un "algorithme" (mais l'exercice peut se faire sans jamais avoir fait d'"algorithmique").
    Il existe d'ailleurs sans doute plusieurs algorithmes.


    Si vous connaissez un applet en ligne générant des anagrammes, faites-le savoir.
    • Partager sur Facebook
    • Partager sur Twitter
      19 juillet 2010 à 12:44:56

      Citation : candide


      Si vous connaissez un applet en ligne générant des anagrammes, faites-le savoir.


      http://pages.central.edu/emp/lintont/c [...] /Anagram.html
      • Partager sur Facebook
      • Partager sur Twitter
        19 juillet 2010 à 19:36:18

        Petite version récursive (ou pas ? :p ), j'ai utilisé le type set pour virer les doublons :-°
        def anagrame(x):
        	if len(x) <= 1:
        		return [x]
        	elif len(x) == 2:
        		return list(set([x,x[1]+x[0]]))
        	else:
        		return list(set([x[i] + d for i in range(len(x)) for d in anagrame(x[:i]+x[i+1:])]))
        
        test = ['','a','ab','abc','zozor']
        for a in test:
            print(anagrame(a))
        

        ['']
        ['a']
        ['ab', 'ba']
        ['acb', 'abc', 'bca', 'cba', 'bac', 'cab']
        ['ozroz', 'zrzoo', 'zrozo', 'zoozr', 'orzoz', 'rzzoo', 'ozrzo', 'ozozr', 'zoorz', 'rzozo', 'zrooz', 'ozzro', 'rozoz', 'roozz', 'rozzo', 'rzooz', 'oozzr', 'zzoro', 'ozzor', 'zoroz', 'oozrz', 'zorzo', 'orozz', 'zzroo', 'zozro', 'zozor', 'orzzo', 'oorzz', 'zzoor', 'ozorz']
        • Partager sur Facebook
        • Partager sur Twitter
          19 juillet 2010 à 21:06:11

          Citation : Einstein++


          http://pages.central.edu/emp/lintont/c [...] /Anagram.html



          Merci de ce lien mais il affiche les anagrammes avec des répétitions.

          Citation : Holt

          Petite version récursive



          elle l'est je trouve.



          Citation : Holt


          ['']
          ['a']
          ['ab', 'ba']
          ['acb', 'abc', 'bca', 'cba', 'bac', 'cab']
          ['ozroz', 'zrzoo', 'zrozo', 'zoozr', 'orzoz', 'rzzoo', 'ozrzo', 'ozozr', 'zoorz', 'rzozo', 'zrooz', 'ozzro', 'rozoz', 'roozz', 'rozzo', 'rzooz', 'oozzr', 'zzoro', 'ozzor', 'zoroz', 'oozrz', 'zorzo', 'orozz', 'zzroo', 'zozro', 'zozor', 'orzzo', 'oorzz', 'zzoor', 'ozorz']


          Ton code est très compact, bravo ! Il fonctionne parfaitement sur tous les cas usuels. Toutefois si tu cherches les anagrammes de, par exemple, 'zzzzzzzzzzzzz' (il n'y en a qu'un), ton programme sera très long à s'exécuter.


          Autre problème mais moins ennuyeux : comme les factorielles croissent très vite, utiliser une liste peut s'avérer très couteux en mémoire, chez moi ça prend jusqu'à 260 Mo pour les angrammes de '0123456789', pas négligeable quand même et ce qui veut dire que ton code aura beaucoup de mal avec juste 1 caractère de plus (il utilisera plusieurs gigas).
          • Partager sur Facebook
          • Partager sur Twitter
            19 juillet 2010 à 21:22:32

            Voilà ma solution (récursive), pondue en quelques minutes.

            # -*- coding: utf-8 -*-
            def trouver_anagrammes(base, lettres, mots, n_lettres):
                if n_lettres == 0:
                    mots.append(base)
                else:
                    for l in lettres:
                        if lettres[l] > 0:
                            lettres[l] -= 1
                            trouver_anagrammes(base+l, lettres, mots, n_lettres-1)
                            lettres[l] += 1
            
            def anagrammes(mot):
                lettres = dict([(l, mot.count(l)) for l in set(mot)])
                mots = list()
                trouver_anagrammes('', lettres, mots, len(mot))
                return mots
            


            Elle traduit littéralement l'algo auquel j'ai pensé en premier : "J'ai les lettres ZOZOR au scrabble, pour en trouver les anagrammes, j'isole d'abord le Z et je cherche tous les anagrammes de OZOR, puis j'isole le O et je cherche ceux de ZZOR, puis j'isole le R et je cherche ceux de ZOZO."

            J'ai utilisé un dictionnaire pour isoler les lettres uniques (de manière à éviter d'explorer des solutions qui se répètent). Au final, la pile d'appel ne dépasse pas le nombre de lettres du mot (donc même pour "anticonstitutionnellement" ça ne plante pas...).

            EDIT : en parlant de "anticonstitutionnellement", si on appelle la fonction sur ce mot, c'est évidemment très long (à cause du nombre d'anagrammes) et ça sature la RAM, donc pour voir le résultat, il est préférable de dégager la liste "mots", et de retourner un générateur, comme ceci :

            # -*- coding: utf-8 -*-
            def trouver_anagrammes(base, lettres, n_lettres):
                if n_lettres == 0:
                    yield base
                else:
                    for l in lettres:
                        if lettres[l] > 0:
                            lettres[l] -= 1
                            for an in trouver_anagrammes(base+l, lettres, n_lettres-1):
                                yield an
                            lettres[l] += 1
            
            def anagrammes(mot):
                lettres = dict((l, mot.count(l)) for l in set(mot))
                for anagramme in trouver_anagrammes('', lettres, len(mot)):
                    yield anagramme
            


            Du coup, on peut voir le code à l'œuvre en console, comme cela :

            >>> from anagrammes import *
            >>> for a in anagrammes("anticonstitutionnel"):
            ...     print a
            ... 
            aceiiiloonnnnsutttt
            aceiiiloonnnnstuttt
            aceiiiloonnnnsttutt
            aceiiiloonnnnstttut
            aceiiiloonnnnsttttu
            aceiiiloonnnnustttt
            aceiiiloonnnnutsttt
            aceiiiloonnnnuttstt
            aceiiiloonnnnutttst
            aceiiiloonnnnutttts
            aceiiiloonnnntsuttt
            aceiiiloonnnntstutt
            aceiiiloonnnntsttut
            aceiiiloonnnntstttu
            # etc.
            


            Et là, on voit que le code carbure... :p
            • Partager sur Facebook
            • Partager sur Twitter
            Zeste de Savoir, le site qui en a dans le citron !
              19 juillet 2010 à 23:01:44

              Citation : NoHaR


              Elle traduit littéralement l'algo auquel j'ai pensé en premier : "J'ai les lettres ZOZOR au scrabble, pour en trouver les anagrammes, j'isole d'abord le Z et je cherche tous les anagrammes de OZOR, puis j'isole le O et je cherche ceux de ZZOR, puis j'isole le R et je cherche ceux de ZOZO."



              Je pense que c'est l'algorithme qui vient spontanément à l'esprit de beaucoup.

              Citation : NoHaR

              Voilà ma solution (récursive),



              Ton code est en effet véloce.

              Citation : NoHaR

              (donc même pour "anticonstitutionnellement" ça ne plante pas...).

              EDIT : en parlant de "anticonstitutionnellement", si on appelle la fonction sur ce mot, c'est évidemment très long (à cause du nombre d'anagrammes), donc pour voir le résultat, (...)
              Et là, on voit que le code carbure... :p



              Et donc, combien obtiens-tu d'anagrammes au total ?


              Citation : NoHaR

              il est préférable de dégager la liste "mots", et de retourner un générateur,



              C'est ce que j'avais utilisé aussi mais codé différemment. Voici :

              def f(mot):
                  if len(mot)==1:
                      yield mot
                  else :
                      for z in set(mot):
                          i=mot.index(z)
                          for sm in f(mot[0:i]+mot[i+1:]):
                              yield z+sm
              
              for m in f("ZOZOR"): print(m)
              
              • Partager sur Facebook
              • Partager sur Twitter
                19 juillet 2010 à 23:46:39

                Dans cet exercice je me suis rendu compte que j'atais pas au point sur les references et les argments passés aux fonctions en python. Par exemple NoHaR ton dictionnaire "lettres" c'est une référence ? c'est donc le même objet dans toutes les fonctions ?


                Sion voilà mon(mes) codes, une version recursive avec optimisation pour ne pas faire deux fois la même travail, et une version iterative pour changer. Elle est plus rapide mais gère pas tous les cas, si y'a une lettre présente plus de 2 fois ça trouve trop de solutons, je verrais si je trouve une magniere d'éviter ça ( à part mettre un set à la fin).

                Le principe est assez compliqué a expliquer faudrait prendre une feuille pour bien s'en rendre compte : on part des deux premieres lettres, on les inverses, ce qui donnes deux mots de deux lettres, ensuite a chaque tour de boucle on fait deux choses :
                1. ajout de la lettre suivante du mot à la fin de chaque minimots
                2. "glissement" de chaque mini mots ( par exemple faire "glisser "abc" dans mon langage ça veut dire "abc" -> "bca" ) on repete donc ce glissement autant de fois que la taille du mot, ex : "abc" -> "bca" "cab" abc"
                On quitte la boucle quand on est arrivé a la fin du mot envoyé en parametre

                def anagrammes(mot):
                	""" plus rapide que l'autre algorithm, cependant a compléter et optimiser """
                	""" ne marche pas avec un mot ayant plus de deux occurences (renvoie plusieurs fois le même anagramme """
                	""" ne marche pas si les deux premieres lettres du mot un fois trié sont identiques """
                	
                	def glissement(mot):
                		""" décales toutes les lettres vers la gauche, la premiere lettre devient la derniere """
                		return mot[1:]+mot[0]
                		
                	result = [] # contient le resultat
                	tmp = sorted(mot) # mettre tous les doublons cote à cote
                	mot = ''
                	for c in tmp:
                		mot += c
                	result.append(mot[:2]) # ajout des deux premieres lettres
                	result.append(mot[1]+mot[0]) # ajout des deux premieres lettres dans l'autre sens
                	
                	index = 2
                	while index < len(mot):
                		#print (result)
                		if mot[index] == mot[index-1]: # si on a un doublon
                			result = result[:(len(result)//2)]
                		# ajout de la lettre suivante à la fin de chaques mots
                		for i in range(len(result)):
                			result[i] += mot[index]
                		#print (result)
                		# duplications et glissements
                		for i in range(len(result)):
                			temp = result[i]
                			for j in range(len(temp)-1):
                				temp = glissement(temp)
                				result.append(temp)
                		#print (result)
                		index += 1
                		
                		
                	return result
                
                r = anagrammes("zozora") # zozor renverai trop de resultats avec cet algorithm, la version finale est plus bas dans ce topic
                print(r)
                print (len(r))
                


                def anagrammes_simple(mot):
                	""" version recursive """
                	""" petit optimisation pour les doublons """
                	
                	result = []
                	
                	def traitement(liste,debut):
                		""" partie recursive de l'algo anagramme recursif """
                		if len(liste) == 1: # on est au bout, on stock la résultat dans la liste des résultats
                			result.append(debut+liste[0])
                			#print (debut+liste[0])
                		else:
                			repet = [] # les caracteres déjà lus dans cette fonction
                			for c in liste:
                				if c not in repet:
                					repet.append(c)
                					l = [ z for z in liste ]
                					l.remove(c)
                					traitement( l , debut+c)
                					
                	traitement([ z for z in mot ],'')
                	
                	return result
                
                r = anagrammes_simple("zozora")
                print(r)
                print(len(r))
                


                Est-ce que qqun peut expliquer le principe d'un yield vite fait ?? merci
                • Partager sur Facebook
                • Partager sur Twitter
                  20 juillet 2010 à 0:12:24

                  Citation : jojomolo

                  Dans cet exercice je me suis rendu compte que j'atais pas au point sur les references et les argments passés aux fonctions en python.



                  En python, le passage des paramètres est par valeur de référence ... ;) comme c'est expliqué dans le tuto officiel sur python.org, cf. une note de bas de page.




                  Citation : jojomolo


                  Sion voilà mon(mes) codes, une version recursive avec optimisation pour ne pas faire deux fois la même travail



                  Si tu avais accompagné ton code de quelques lignes de test ça aurait été plus clair. Ton code donne 120 anagrammes pour ZOZOR alors qu'il y en a seulement 30 ...
                  • Partager sur Facebook
                  • Partager sur Twitter
                    20 juillet 2010 à 1:43:13

                    Citation : candide

                    Citation : jojomolo

                    Dans cet exercice je me suis rendu compte que j'atais pas au point sur les references et les argments passés aux fonctions en python.



                    En python, le passage des paramètres est par valeur de référence ... ;) comme c'est expliqué dans le tuto officiel sur python.org, cf. une note de bas de page.

                    Cela depend des parametres en question
                    • Partager sur Facebook
                    • Partager sur Twitter
                      20 juillet 2010 à 1:48:09

                      Citation : psimod

                      Citation : candide



                      Cela depend des parametres en question



                      Non je ne pense pas ou alors précise ta pensée.
                      • Partager sur Facebook
                      • Partager sur Twitter
                        20 juillet 2010 à 2:18:41

                        Je pensais a quelque chose du genre:
                        a = 0
                        def f(a):
                            a = 1
                        f(a)
                        print a
                        

                        le print affiche 0 a l'ecran, ce qui montre bien que f travaille avec une copie est non une reference de a.
                        • Partager sur Facebook
                        • Partager sur Twitter
                          20 juillet 2010 à 3:01:33

                          Citation : psimod

                          Je pensais a quelque chose du genre:

                          a = 0
                          def f(a):
                              a = 1
                          f(a)
                          print a
                          


                          le print affiche 0 a l'ecran, ce qui montre bien que f travaille avec une copie est non une reference de a.



                          Non, f reçoit non pas la valeur de a mais une référence vers a. Tu le vois en lisant à chaque fois l'id (en quelque sorte l'adresse mémoire) de a :

                          a = 0
                          def f(a):
                              print "a dans f", id(a)
                              a = 1
                              print "a dans f apres reaffectation", id(a)
                          print "a hors de f",id(a)
                          f(a)
                          print a
                          print "a hors de f",id(a)
                          

                          (c'est du Python 2.6)
                          a hors de f 154574188
                          a dans f 154574188
                          a dans f apres reaffectation 154574176
                          0
                          a hors de f 154574188



                          f reçoit une copie de la référence vers a et donc peut lire la valeur (mais pas la modifier car a est immutable, c'est un nombre). A la ligne 4 tu associes à a un emplacement mémoire qui vaut 1 et donc f perd toute référence du a initial, c'est comme une perte de mémoire.

                          Une fois qu'on quitte f bien sûr que le a extérieur vaut toujours 0 car les scopes de f et du fichier ne sont pas les mêmes.


                          • Partager sur Facebook
                          • Partager sur Twitter
                            20 juillet 2010 à 3:28:24

                            oui je vois. merci pour ces explications.
                            • Partager sur Facebook
                            • Partager sur Twitter
                            Anonyme
                              20 juillet 2010 à 5:28:43

                              Voila ma réponse

                              >>> from itertools import permutations as p
                              >>> liste=[]
                              >>> for i in p('ZOZOR', 5):
                              	if ''.join(i) not in liste:
                              		liste.append(''.join(i))
                              
                              		
                              >>> for j in liste:
                              	print j
                              


                              Résultat

                              ZOZOR
                              ZOZRO
                              ZOOZR
                              ZOORZ
                              ZORZO
                              ZOROZ
                              ZZOOR
                              ZZORO
                              ZZROO
                              ZROZO
                              ZROOZ
                              ZRZOO
                              OZZOR
                              OZZRO
                              OZOZR
                              OZORZ
                              OZRZO
                              OZROZ
                              OOZZR
                              OOZRZ
                              OORZZ
                              ORZZO
                              ORZOZ
                              OROZZ
                              RZOZO
                              RZOOZ
                              RZZOO
                              ROZZO
                              ROZOZ
                              ROOZZ


                              • Partager sur Facebook
                              • Partager sur Twitter
                                20 juillet 2010 à 8:11:35

                                le but en fait c'etait de recoder permutations
                                • Partager sur Facebook
                                • Partager sur Twitter
                                Anonyme
                                  20 juillet 2010 à 8:17:27

                                  Je n'ai aucunes notions d'algorithmie, donc je fais l'exercice avec mes connaissances de bases en informatique, c'est à dire aucune, et c'est pour ça que j'ai choisis python. C'est un outil!

                                  Maintenant je montre la solution avec des modules me permettant de trouver ce résultat, ce qui serait impossible pour moi dans la version étudiante.

                                  Rien ne t'empêche de te casser la tête, tu en auras beaucoup plus d'intérêt que moi.
                                  • Partager sur Facebook
                                  • Partager sur Twitter
                                    20 juillet 2010 à 10:31:14

                                    Citation : candide


                                    Et donc, combien obtiens-tu d'anagrammes au total ?



                                    Hmmm, alors, rapidement (j'ai pas le temps de réfléchir à une manière élégante de faire le calcul):

                                    Soit <math>\(\mathcal{L}\)</math> l'ensemble des lettres du mot de cardinal <math>\(l\)</math>. Je construis cet ensemble comme on pioche des lettres au scrabble, c'est-à-dire que <math>\(l\)</math> est la longueur de la chaine de caractères. Par exemple, pour le mot "zozor", <math>\(\mathcal{L} = \left\lbrace z_1, o_1, z_2, o_2, r\right\rbrace\)</math>.
                                    Ensuite, je construis une partition <math>\(\mathcal{U}\)</math> de cet ensemble pour regrouper les lettres uniques. Par exemple, pour le mot "zozor" <math>\(\mathcal{U} = \left\lbrace \mathrm{Z}, \mathrm{O}, \mathrm{R} \right\rbrace = \left\lbrace{ \left\lbrace{z_1, z_2}\right\rbrace, \left\lbrace{o_1, o_2}\right\rbrace, \left\lbrace{r}\right\rbrace }\right\rbrace\)</math>.

                                    Maintenant, dans le cas le pire (c'est-à-dire que le mot ne contient que des lettres uniques : <math>\(\mathrm{Card}(u) = 1\; \forall u \in \mathcal{U}\)</math>), le nombre d'anagrammes est égal au nombre de permutations des éléments de <math>\(\mathcal{L}\)</math>, c'est-à-dire <math>\(l!\)</math>.

                                    Sauf que des lettres peuvent se répéter ce qui multiplie les permutations inutiles. Il faut donc diviser le nombre total de permutations possibles par celui des permutations inutiles :

                                    <math>\(N_{anagrammes} = \frac{\mathrm{Card}(\mathcal{L})!}{\prod_{u \in \mathcal{U}} \mathrm{Card}(u)!}\)</math>

                                    Pour "anticonstitutionnellement", ça donne, (en s'aidant un peu de python) :
                                    >>> from math import factorial as f
                                    >>> mot = "anticonstitutionnellement"
                                    >>> lettres = dict((l, mot.count(l)) for l in set(mot))
                                    >>> lettres
                                    {'a': 1, 'c': 1, 'e': 3, 'i': 3, 'm': 1, 'l': 2, 'o': 2, 'n': 5, 's': 1, 'u': 1, 't': 5}
                                    >>> n_anagrammes = f(len(mot))
                                    >>> for l in lettres:
                                    ...     n_anagrammes /= f(lettres[l])
                                    ... 
                                    >>> print n_anagrammes
                                    7480328917501440000
                                    


                                    Soit très très beaucoup ! :p
                                    • Partager sur Facebook
                                    • Partager sur Twitter
                                    Zeste de Savoir, le site qui en a dans le citron !
                                      20 juillet 2010 à 11:10:56

                                      Citation : fred1599

                                      Voila ma réponse



                                      Ah oui, très bien vu, les anagrammes, c'est ce qui reste quand on a supprimé les permutations identiques.

                                      Le petit inconvénient c'est que si je lui demande les anagrammes de ZZZZZZZZZZZ (il n'y en a qu'un), il va mettre un paquet de temps à le trouver.

                                      Citation : NoHaR


                                      <math>\(N_{anagrammes} = \frac{\mathrm{Card}(\mathcal{L})!}{\prod_{u \in \mathcal{U}} \mathrm{Card}(u)!}\)</math>



                                      Oui (c'est un coefficient multinomial).

                                      Citation : NoHaR



                                      7480328917501440000
                                      



                                      Soit très très beaucoup ! :p



                                      Oui et c'est pour cela que je t'avais posé la question parce qu'en te lisant, on aurait presque pu croire qu'un programme très véloce était capable de les générer toutes une par une ;)
                                      • Partager sur Facebook
                                      • Partager sur Twitter
                                      Anonyme
                                        20 juillet 2010 à 11:32:21

                                        Citation

                                        Ah oui, très bien vu, les anagrammes, c'est ce qui reste quand on a supprimé les permutations identiques.

                                        Le petit inconvénient c'est que si je lui demande les anagrammes de ZZZZZZZZZZZ (il n'y en a qu'un), il va mettre un paquet de temps à le trouver.



                                        ok je rectifie

                                        >>> from itertools import permutations as p
                                        >>> def ana(ch):
                                        	liste=[]
                                        	for i in ch:
                                        		if ch.count(i)==len(ch): return "1 anagramme", ch
                                        	for i in p(ch, len(ch)):
                                        		if ''.join(i) not in liste: liste.append(''.join(i))
                                        	for j in liste: print j
                                        


                                        • Partager sur Facebook
                                        • Partager sur Twitter
                                          20 juillet 2010 à 11:38:30

                                          Citation : candide


                                          Citation : NoHaR


                                          <math>\(N_{anagrammes} = \frac{\mathrm{Card}(\mathcal{L})!}{\prod_{u \in \mathcal{U}} \mathrm{Card}(u)!}\)</math>


                                          Oui (c'est un coefficient multinomial).



                                          Aha ! Je me coucherai moins bête ce soir ! :)

                                          Citation : candide


                                          Oui et c'est pour cela que je t'avais posé la question parce qu'en te lisant, on aurait presque pu croire qu'un programme très véloce était capable de les générer toutes une par une ;)



                                          Non effectivement on est obligé d'interrompre l'exécution, mais le mot contient tellement de lettres que l'on voit bien comment l'algo travaille quand il est "en mouvement".

                                          Sinon, j'aime beaucoup ton implémentation (je viens de découvrir l'intérêt des set :) ), moins littérale (intuitive, évidente...) que la mienne mais plus élégante.

                                          Citation : jojomolo

                                          Est-ce que qqun peut expliquer le principe d'un yield vite fait ?? merci



                                          yield permet de retourner un générateur de liste, c'est-à-dire qu'il permet de parcourir une séquence au fur et à mesure qu'elle est construite, ce qui évite de stocker le résultat dans une liste en mémoire, et fluidifie l'exécution du code.

                                          Par exemple :

                                          >>> def double(liste):
                                          ...     for element in liste:
                                          ...             print "je double {0}".format(element) 
                                          ...             yield 2*element
                                          ... 
                                          >>> ma_liste = [1, 3, 4, 2, 8]
                                          >>> for i in double(ma_liste):
                                          ...     print "ça me donne {0}".format(i)
                                          ... 
                                          je double 1
                                          ça me donne 2
                                          je double 3
                                          ça me donne 6
                                          je double 4
                                          ça me donne 8
                                          je double 2
                                          ça me donne 4
                                          je double 8
                                          ça me donne 16
                                          


                                          Citation : fred1599


                                          >>> from itertools import permutations as p
                                          >>> def ana(ch):
                                          	liste=[]
                                          	for i in ch:
                                          		if ch.count(i)==len(ch): return "1 anagramme", ch
                                          	for i in p(ch, len(ch)):
                                          		if ''.join(i) not in liste: liste.append(''.join(i))
                                          	for j in liste: print j
                                          




                                          Désolé de "faire mon candide", mais combien de temps ça met pour "ZZZZZZZZZZZZZA" ?
                                          :p
                                          • Partager sur Facebook
                                          • Partager sur Twitter
                                          Zeste de Savoir, le site qui en a dans le citron !
                                            20 juillet 2010 à 14:58:44

                                            Citation : NoHaR

                                            Voilà ma solution



                                            Tiens, à propos des respect des standards de codage (tu en parles dans un autre fil), j'ai été très étonné de lire ceci dans ton code :

                                            Citation : NoHaR


                                            for l in lettres:
                                                        if lettres[l] > 0:
                                                            lettres[l] -= 1
                                                            trouver_anagrammes(base+l, lettres, mots, n_lettres-1)
                                                            lettres[l] += 1
                                            




                                            EDIT je viens de voir que tu m'avais posé une question sur le code de fred, je regarde ça maintenant.
                                            Euh, non, en fait tu faisais ton "candide" mais je crois que la remarque s'adressait à fred dont la parade a été un peu trop simple.
                                            • Partager sur Facebook
                                            • Partager sur Twitter
                                              20 juillet 2010 à 15:05:43

                                              Citation : candide

                                              Ton code donne 120 anagrammes pour ZOZOR alors qu'il y en a seulement 30 ...


                                              Euh mon programme recursif renvoie bien 30 anagrammes pour zozor, pas plus pas moins,

                                              @fred1599 : génial je savais pas que y'avait des fonctions comme ça dans python, y'a pas la fonction combinaison par hasard ?
                                              Et je suis tout à fait d'accord sur le principe, python est un super outils, donc quand une fonctions existe ça sert à rien de la recoder, sauf pour s'amuser. Elle sera souvent moins efficace


                                              Ensuite voilà mon code fini pour la version itérative, j'ai utilisé un set ça me plait pas du tout mais bon j'avais que ça sous la main : voilà mon programme qui compare ma version itérative, ma version récursive, le version de Noharu et l'itertools (version de fred) :


                                              def factoriel(n):
                                              	p = 1
                                              	for i in range(1,n+1):
                                              		p*=i
                                              	return p
                                              		
                                              
                                              	
                                              def tailleTraitement(mot):
                                              	l = [ mot.count(p) for p in set(mot) if mot.count(p) > 1 ] # recuperationd des doublons (juste leur quantité)
                                              	# print (l)
                                              	tailleTraitement = factoriel(len(mot)) # taille si il n'y avait pas de doublons
                                              	for i in l: # on va maintenant diminuer ce nombre
                                              		tailleTraitement //= factoriel(i)
                                              	return tailleTraitement
                                              
                                              		
                                              	
                                              def anagrammes(mot):
                                              	""" fonction itérative couplant deux fonctions : """
                                              	""" une fonction pour les chaines avec des lettres qui se repetent """
                                              	""" une autre pour les chaines avec des lettres ne se repetants pas beaucoup """
                                              	
                                              	def glissement(mot):
                                              		""" décales toutes les lettres vers la gauche, la premiere lettre devient la derniere """
                                              		""" base de la rapidité de l'algorithme genere une nouvelle combinaison à partir d'un mot sans calculs """
                                              		return mot[1:]+mot[0]
                                              	
                                              	def v2(mot):
                                              		""" version générale de l'algorithme """
                                              		result = set() # contient le resultat
                                              		# ajout des deux premieres lettres
                                              		result.add(mot[:2])
                                              		# ajout des deux premieres lettres dans l'autre sens
                                              		result.add(mot[1]+mot[0])
                                              	
                                              		index = 2
                                              		while index < len(mot):
                                              			tmp = []
                                              			#print (result)
                                              			# ajout de la lettre suivante à la fin de chaques mots
                                              			for i in result:
                                              				tmp.append(i+mot[index])
                                              			result = set()
                                              			#print (result)
                                              			# duplications et glissements
                                              			for temp in tmp:
                                              				for j in range(len(temp)):
                                              					temp = glissement(temp)
                                              					result.add(temp)
                                              			#print (result)
                                              			index += 1
                                              		return result
                                              	
                                              	def v1(mot):
                                              		""" version pour les chaines avec des lettres présentent une seule fois """
                                              		""" equivalent a une permutation """
                                              		
                                              		result = [] # contient le resultat
                                              		
                                              		result.append(mot[:2]) # ajout des deux premieres lettres
                                              		result.append(mot[1]+mot[0]) # ajout des deux premieres lettres dans l'autre sens
                                              	
                                              		index = 2
                                              		while index < len(mot):
                                              			#print (result)
                                              			# ajout de la lettre suivante à la fin de chaques mots
                                              			for i in range(len(result)):
                                              				result[i] += mot[index]
                                              			#print (result)
                                              			# duplications et glissements
                                              			for i in range(len(result)):
                                              				temp = result[i]
                                              				for j in range(len(temp)-1):
                                              					temp = glissement(temp)
                                              					result.append(temp)
                                              			#print (result)
                                              			index += 1
                                              		return result
                                              	
                                              	
                                              	
                                              	tmp = sorted([(p, mot.count(p)) for p in set(mot)], key=lambda x: x[1])
                                              	# si au moins une lettre est présente plus de deux fois : v2
                                              	for i in tmp:
                                              		if i[1] > 1:
                                              			return v2(mot)
                                              	# sinon v1
                                              	return v1(mot)
                                              	
                                              	
                                              		
                                              	return result
                                              	
                                              
                                              	
                                              		
                                              def anagrammes_simple(mot):
                                              	""" version recursive """
                                              	""" petit optimisation pour les doublons """
                                              	
                                              	result = []
                                              	
                                              	def traitement(liste,debut):
                                              		""" partie recursive de l'algo anagramme recursif """
                                              		if len(liste) == 1: # on est au bout, on stock la résultat dans la liste des résultats
                                              			result.append(debut+liste[0])
                                              			#print (debut+liste[0])
                                              		else:
                                              			repet = [] # les caracteres déjà lus dans cette fonction
                                              			for c in liste:
                                              				if c not in repet:
                                              					repet.append(c)
                                              					l = [ z for z in liste ]
                                              					l.remove(c)
                                              					traitement( l , debut+c)
                                              					
                                              	traitement([ z for z in mot ],'')
                                              	
                                              	return result
                                              
                                              def anagramme(x):
                                              	from itertools import permutations as p
                                              	liste=[]
                                              	for i in p(x, len(x)):
                                              		liste.append(''.join(i))
                                              	return set(liste)
                                              
                                              def trouver_anagrammes(base, lettres, mots, n_lettres):
                                                  if n_lettres == 0:
                                                      mots.append(base)
                                                  else:
                                                      for l in lettres:
                                                          if lettres[l] > 0:
                                                              lettres[l] -= 1
                                                              trouver_anagrammes(base+l, lettres, mots, n_lettres-1)
                                                              lettres[l] += 1
                                              
                                              def anagrammes_noharu(mot):
                                                  lettres = dict([(l, mot.count(l)) for l in set(mot)])
                                                  mots = list()
                                                  trouver_anagrammes('', lettres, mots, len(mot))
                                                  return mots
                                              
                                              if __name__ == "__main__":
                                              	
                                              	import time
                                              	import signal
                                              	
                                              	class Timeout(Exception): 
                                              		"""Exception to raise on a timeout""" 
                                              		pass 
                                              	
                                              	def alarmHandler(signum, frame):
                                              		raise Timeout
                                              		
                                              	signal.signal(signal.SIGALRM, alarmHandler)
                                              	
                                              	# TEST
                                              	fonctions = { "iteratif": anagrammes, "recursif": anagrammes_simple, "itertols": anagramme, "nohar": anagrammes_noharu }
                                              	for test in ["zozor","abcdefghi","zzzzzzzzzzzzzzz","zozorzozorzozor","abcdeabcde","abcdefghik","aabbccddee","aabbccdde"]:
                                              		print ("\n--------------------------------------------")
                                              		print ("\n--------------------------------------------")
                                              		print ("\n--------------------------------------------")
                                              		print (test)
                                              		print ("taille de la sortie :", tailleTraitement(test))
                                              		
                                              		for n,f in fonctions.items():
                                              			print ("\n",n)
                                              			signal.alarm(30)
                                              			start = time.clock()
                                              			try:
                                              				result = f(test)
                                              			except Timeout:
                                              				print ("la fonction est trop lente (plus de 30s...)")
                                              				time.sleep(1)
                                              			else:
                                              				signal.alarm(0)
                                              				print ("temps : ",time.clock()-start)
                                              				print (len(result))
                                              



                                              et les resultat que j'ai récupéré dans un fichier :

                                              --------------------------------------------
                                              
                                              --------------------------------------------
                                              
                                              --------------------------------------------
                                              zozor
                                              taille de la sortie : 30
                                              
                                               iteratif
                                              temps :  0.0
                                              30
                                              
                                               recursif
                                              temps :  0.0
                                              30
                                              
                                               nohar
                                              temps :  0.0
                                              30
                                              
                                               itertols
                                              temps :  0.0
                                              30
                                              
                                              --------------------------------------------
                                              
                                              --------------------------------------------
                                              
                                              --------------------------------------------
                                              abcdefghi
                                              taille de la sortie : 362880
                                              
                                               iteratif
                                              temps :  0.37
                                              362880
                                              
                                               recursif
                                              temps :  1.66
                                              362880
                                              
                                               nohar
                                              temps :  2.04
                                              362880
                                              
                                               itertols
                                              temps :  0.44
                                              362880
                                              
                                              --------------------------------------------
                                              
                                              --------------------------------------------
                                              
                                              --------------------------------------------
                                              zzzzzzzzzzzzzzz
                                              taille de la sortie : 1
                                              
                                               iteratif
                                              temps :  0.1
                                              1
                                              
                                               recursif
                                              temps :  0.0
                                              1
                                              
                                               nohar
                                              temps :  0.0
                                              1
                                              
                                               itertols
                                              la fonction est trop lente (plus de 30s...)
                                              
                                              --------------------------------------------
                                              
                                              --------------------------------------------
                                              
                                              --------------------------------------------
                                              zozorzozorzozor
                                              taille de la sortie : 420420
                                              
                                               iteratif
                                              temps :  2.45
                                              420420
                                              
                                               recursif
                                              temps :  2.73
                                              420420
                                              
                                               nohar
                                              temps :  2.29
                                              420420
                                              
                                               itertols
                                              la fonction est trop lente (plus de 30s...)
                                              
                                              --------------------------------------------
                                              
                                              --------------------------------------------
                                              
                                              --------------------------------------------
                                              abcdeabcde
                                              taille de la sortie : 113400
                                              
                                               iteratif
                                              temps :  0.34
                                              113400
                                              
                                               recursif
                                              temps :  0.6
                                              113400
                                              
                                               nohar
                                              temps :  0.57
                                              113400
                                              
                                               itertols
                                              temps :  3.83
                                              113400
                                              
                                              --------------------------------------------
                                              
                                              --------------------------------------------
                                              
                                              --------------------------------------------
                                              abcdefghik
                                              taille de la sortie : 3628800
                                              
                                               iteratif
                                              temps :  3.67
                                              3628800
                                              
                                               recursif
                                              temps :  16.64
                                              3628800
                                              
                                               nohar
                                              temps :  21.11
                                              3628800
                                              
                                               itertols
                                              temps :  4.71
                                              3628800
                                              
                                              --------------------------------------------
                                              
                                              --------------------------------------------
                                              
                                              --------------------------------------------
                                              aabbccddee
                                              taille de la sortie : 113400
                                              
                                               iteratif
                                              temps :  1.44
                                              113400
                                              
                                               recursif
                                              temps :  0.6
                                              113400
                                              
                                               nohar
                                              temps :  0.58
                                              113400
                                              
                                               itertols
                                              temps :  3.82
                                              113400
                                              
                                              --------------------------------------------
                                              
                                              --------------------------------------------
                                              
                                              --------------------------------------------
                                              aabbccdde
                                              taille de la sortie : 22680
                                              
                                               iteratif
                                              temps :  0.06
                                              22680
                                              
                                               recursif
                                              temps :  0.12
                                              22680
                                              
                                               nohar
                                              temps :  0.12
                                              22680
                                              
                                               itertols
                                              temps :  0.37
                                              22680


                                              Conclusion : pour les chaines qui ne comportent pas de répétitions la fonctions permutation de itertools est le plus rapide, sauf que le fait de faire un test à chaque tour de boucle pour savoir si on a déjà trouvé cet anagramme lui fait perdre énormément de temps, pour ce qui est des chaines comportants plusieurs répétitions elle est beaucoup trop longue vu qu'elle fait tous les anagrammes.
                                              En global je pense que la version itérative avec le système de glissement est la plus polyvalente
                                              • Partager sur Facebook
                                              • Partager sur Twitter
                                                20 juillet 2010 à 15:10:14

                                                Citation : candide


                                                Tiens, à propos des respect des standards de codage (tu en parles dans un autre fil), j'ai été très étonné de lire ceci dans ton code :
                                                (...)



                                                En effet, mea culpa. J'ai fait cet exo pendant un petit trajet en train, j'ai donc pris ce raccourcis.
                                                Ceci dit, j'ai préféré utiliser "l" dans ce cas plutôt que "lettre" pour éviter de piquer les yeux avec "lettres[lettre]".

                                                Mais je l'avoue : la variable d'un seul caractère, c'est moche, et en plus c'est un "l" minuscule, ce qui est d'autant plus déconseillé.

                                                (merci d'y aller mollo sur le fouet quand même :euh: )
                                                • Partager sur Facebook
                                                • Partager sur Twitter
                                                Zeste de Savoir, le site qui en a dans le citron !
                                                Anonyme
                                                  20 juillet 2010 à 15:20:06

                                                  Citation

                                                  Désolé de "faire mon candide", mais combien de temps ça met pour "ZZZZZZZZZZZZZA" ?



                                                  Arf en effet tu fais ton candide :p

                                                  J'avais pas pensé à cela, dommage, là je vois pas la parade
                                                  • Partager sur Facebook
                                                  • Partager sur Twitter
                                                    20 juillet 2010 à 15:25:55

                                                    Citation : jojomolo

                                                    Citation : candide

                                                    Ton code donne 120 anagrammes pour ZOZOR alors qu'il y en a seulement 30 ...


                                                    Euh mon programme recursif renvoie bien 30 anagrammes pour zozor, pas plus pas moins,



                                                    Si tu ne veux pas prendre le risque que ton code soit mal utilisé, accompagne-le d'un code de test (éventuellement dans une docstring comme cela est couramment pratiqué) ce n'était pas le cas dans le code que tu as posté.

                                                    Cette remarque ne s'adresse pas spécifiquement à toi d'ailleurs, il arrive très fréquemment que du code brut sans "instantiation" soit livré dans le forum, c'est très préjudiciable pour les débutants qui très souvent ne seront pas en mesure d'exploiter le dit-code et c'est même préjudiciable pour des moins débutants.

                                                    Au demeurant voici ton code exécuté et la réponse qu'il fournit (120 au lieu de 30) :


                                                    # -*- coding: utf-8 -*-
                                                    def anagrammes(mot):
                                                        """ plus rapide que l'autre algorithm, cependant a compléter et optimiser """
                                                        """ ne marche pas avec un mot ayant plus de deux occurences (renvoie plusieurs fois le même anagramme """
                                                        """ ne marche pas si les deux premieres lettres du mot un fois trié sont identiques """
                                                        
                                                        def glissement(mot):
                                                            """ décales toutes les lettres vers la gauche, la premiere lettre devient la derniere """
                                                            return mot[1:]+mot[0]
                                                            
                                                        result = [] # contient le resultat
                                                        sorted(mot) # mettre tous les doublons cote à cote
                                                        result.append(mot[:2]) # ajout des deux premieres lettres
                                                        result.append(mot[1]+mot[0]) # ajout des deux premieres lettres dans l'autre sens
                                                        
                                                        index = 2
                                                        while index < len(mot):
                                                            #print (result)
                                                            if mot[index] == mot[index-1]: # si on a un doublon
                                                                result = result[:(len(result)//2)]
                                                            # ajout de la lettre suivante à la fin de chaques mots
                                                            for i in range(len(result)):
                                                                result[i] += mot[index]
                                                            #print (result)
                                                            # duplications et glissements
                                                            for i in range(len(result)):
                                                                temp = result[i]
                                                                for j in range(len(temp)-1):
                                                                    temp = glissement(temp)
                                                                    result.append(temp)
                                                            #print (result)
                                                            index += 1
                                                            
                                                            
                                                        return result
                                                    
                                                    
                                                    print len(anagrammes("zozor"))
                                                    



                                                    120





                                                    Citation : NoHaR


                                                    Mais je l'avoue : la variable d'un seul caractère, c'est moche, et en plus c'est un "l" minuscule, ce qui est d'autant plus déconseillé.



                                                    et même déconseillé par la PEP-8 :

                                                    Citation : PEP-8

                                                    Prescriptive: Naming Conventions

                                                    Names to Avoid

                                                    Never use the characters `l' (lowercase letter el), `O' (uppercase
                                                    letter oh), or `I' (uppercase letter eye) as single character variable
                                                    names.




                                                    Citation : NoHaR


                                                    (merci d'y aller mollo sur le fouet quand même :euh: )



                                                    Qui aime bien châtie bien ;)

                                                    Non, j'ai un bon fond (enfin j'espère) mais je sais pas mettre les formes !
                                                    • Partager sur Facebook
                                                    • Partager sur Twitter
                                                      20 juillet 2010 à 15:34:16

                                                      @candide, ben au début de la fonction y'a marqué que si tu rentres zozor ça va sortir des doublons...

                                                      je me cite mon code :
                                                      """ ne marche pas avec un mot ayant plus de deux occurences (renvoie plusieurs fois le même anagramme """
                                                      """ ne marche pas si les deux premieres lettres du mot un fois trié sont identiques """

                                                      je suis d'accord pour accompagner des lignes de tests c'est vrai que quand on voit un code la première chose qu'on veut faire c'est copier/coller/essayer
                                                      • Partager sur Facebook
                                                      • Partager sur Twitter
                                                        20 juillet 2010 à 16:31:15

                                                        Citation : jojomolo


                                                        je suis d'accord pour accompagner des lignes de tests c'est vrai que quand on voit un code la première chose qu'on veut faire c'est copier/coller/essayer



                                                        Un moyen très cool de faire ce genre de choses, qu'il faudrait peut-être conseiller plus souvent, est d'utiliser le module doctest : tu mets un "exemple console" dans le docstring de ta fonction :

                                                        def mult(a, b):
                                                            """
                                                            Multiplie 2 nombres a et b
                                                            
                                                            >>> mult(3,4)
                                                            12
                                                            """
                                                            return a * b
                                                        


                                                        puis à la fin du module :

                                                        if __name__ == '__main__':
                                                            import doctest
                                                            doctest.testmod()
                                                        


                                                        Quand tu lances ensuite ton script, l'exemple dans le docstring est utilisé comme test unitaire pour valider la fonction (l'argument -v permet d'afficher le détail) :

                                                        16:29 arnaud@laptop % python multiplication.py -v
                                                        Trying:
                                                            mult(3,4)
                                                        Expecting:
                                                            12
                                                        ok
                                                        1 items had no tests:
                                                            __main__
                                                        1 items passed all tests:
                                                           1 tests in __main__.mult
                                                        1 tests in 2 items.
                                                        1 passed and 0 failed.
                                                        Test passed.
                                                        • Partager sur Facebook
                                                        • Partager sur Twitter
                                                        Zeste de Savoir, le site qui en a dans le citron !
                                                          20 juillet 2010 à 22:20:38

                                                          génial ce truc, je savais pas que ça servait à ça les triples guillemets
                                                          donc en gros je peux mettre un commentaire au début, suivi de la commande a tester, suivi du résultat attendu c'est bien ça ?
                                                          • Partager sur Facebook
                                                          • Partager sur Twitter
                                                            21 juillet 2010 à 1:02:02

                                                            Citation : jojomolo

                                                            génial ce truc, je savais pas que ça servait à ça les triples guillemets



                                                            Ça a d'autres usages.


                                                            Citation : jojomolo


                                                            donc en gros je peux mettre un commentaire au début, suivi de la commande a tester, suivi du résultat attendu c'est bien ça ?


                                                            grosso modo oui, les détails sont dans la doc, ici et très lisibles (une fois le cap de l'anglais dépassé).
                                                            • Partager sur Facebook
                                                            • Partager sur Twitter
                                                              21 juillet 2010 à 2:23:41

                                                              Pour info, j'utilise énormément doctest dans mon boulot, pasrce que mon manager ne connait (encore) rien à Python (?!.. eh oui, ça se passe comme ça en entreprise), et que c'est un excellent moyen de lui montrer que ce que je code est conforme à ce qu'il attend de moi.

                                                              D'une manière générale, les tests unitaires sont une excellente habitude à adopter (même si, dans pas mal de cas, il faut un peu plus qu'un simple doctest pour valider une fonctionnalité complexe), tout comme les docstrings.

                                                              Je crois me souvenir que c'est dans la PEP-8 que notre cher Guido explique qu' « un programme n'est codé qu'une seule fois, mais il susceptible d'être lu de nombreuses fois par la suite ». Le fait d'intégrer des exemples (directements testables qui plus est !), est un excellement moyen de montrer ce que ton code fait, mais en plus qu'il fonctionne exactement de la manière que l'on s'attend.
                                                              • Partager sur Facebook
                                                              • Partager sur Twitter
                                                              Zeste de Savoir, le site qui en a dans le citron !

                                                              [exercice] Générer tous les anagrammes

                                                              × Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
                                                              × Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
                                                              • Editeur
                                                              • Markdown