Partage

[exercice] Générer tous les anagrammes

zozor rozzo rozoz roozz ...

21 juillet 2010 à 22:05:56

Bonsoir.

Voici mon code :
from itertools import permutations

element = input('Veuillez saisir un mot : ')
for anagramme in set(permutations(element, len(element))):
    print(''.join(anagramme))


[michael@myarch ExosPython]$ python3 anagrammes.py 
Veuillez saisir un mot : abc
bac
bca
cab
acb
cba
abc
[michael@myarch ExosPython]$ python3 anagrammes.py 
Veuillez saisir un mot : zzz
zzz
21 juillet 2010 à 22:27:23

Citation : tcpc_


Voici mon code



Merci de ta participation. Le code que tu proposes a déjà été donné au set près. C'est un code très compact mais qui a le désavantage d'avoir un temps d'exécution totalement prohibitif pour trouver les anagrammes d'un mot long mais contenant peu de lettres distinctes, genre aaaaaaaaaaabbcccc.
21 juillet 2010 à 22:28:46

Je n'ai pas vu le code proposé, loin de moi l'idée de copier bêtement. Pour le temps d'exécution, je regarde cela.

EDIT : je regrette, je n'ai pas vu le même code que le mien.
Anonyme
21 juillet 2010 à 22:30:54

Citation

Je n'ai pas vu le code proposé, loin de moi l'idée de copier bêtement



Je ne pense pas qu'il voulait dire ça, mais plutôt donné le point faible de ce code, dont je suis l'auteur tout comme toi.

Si tu trouves la parade à ce temps d'attente, je signe :)
21 juillet 2010 à 22:32:09

Quel temps d'attente ? C'est immédiat, chez moi.

EDIT : ha. Mea culpa. Je n'avais pas essayé avec la suite de lettres que proposait Candide.
Anonyme
21 juillet 2010 à 22:33:21

Essai avec ZZZZZZZZZZZZZZZZZZZZZZ
21 juillet 2010 à 22:38:58

Citation : tcpc_

Je n'ai pas vu le code proposé, loin de moi l'idée de copier bêtement.



Loin de moi cette idée.


Citation : tcpc_


EDIT : je regrette, je n'ai pas vu le même code que le mien.



Regarde le code de fred, au set près, c'est la même idée (générer toutes les permutations comme si les lettres étaient distinctes puis supprimer les doublons). C'est pas impossible qu'il y ait le moyen de s'en sortir en lisant bien la doc de itertools.
21 juillet 2010 à 22:41:55

Ouais, ce n'est pas exactement le même code (il utilise une liste, etc.). Mais bref, le problème reste le même. Tester avec une longue suite de lettres fait tout planter. Que ce soit avec "zzzzzzzz", "aaabbbbcccc" ou "anticonstitutionnellement".

Je réfléchirai au problème demain. J'aimerai trouvé une solution à ton sujet, s'appuyant sur itertools. Cela me paraît plus intéressant (pour moi) que de chercher une solution à part entière avec un algorithme (NoHaR et Cie).
Anonyme
21 juillet 2010 à 22:48:47

Citation

Je réfléchirai au problème demain. J'aimerai trouvé une solution à ton sujet, s'appuyant sur itertools. Cela me paraît plus intéressant (pour moi) que de chercher une solution à part entière avec un algorithme (NoHaR et Cie).



Je suis d'accord avec toi, et surtout si tu trouves n'hésite pas à poster
23 juillet 2010 à 11:46:39

je pense qu y'en a pas puisque itertools.permutation fait tout simplement (et très efficacement) toutes les pérmutations, donc après faut toutes les tester pour voir si on les a déjà sorti ou pas, alors que quand tu fais le code toi même tu lui fait sauter des étapes quand tu vois deux lettres pareils. Mais bon si tu trouves je suis prenneur aussi
Anonyme
23 juillet 2010 à 15:31:37

Une version récursive, compact sans appel de lib extérieures :
def poped(foo, i): return foo[:i]+foo[i+1:]

def anagramme(mot, base=''):
    if mot == []: 
        print(base)
    else:
        for i, c in enumerate(mot):
            anagramme(poped(mot, i), base+c)
21 février 2012 à 20:18:31

version ci-dessus fausse...

EDIT :
Mon code (aucun mérite pour l'algo, j'ai lu les autres posts) :

import collections

def rec_anagram(counter):
    if sum(counter.values()) == 0:
        yield ''
    else:
        for c in counter:
            if counter[c] != 0:
                counter[c] -= 1
                for _ in rec_anagram(counter):
                    yield c + _
                counter[c] += 1

                
def anagram(word):
    return rec_anagram(collections.Counter(word))
3 juin 2013 à 20:04:59

Bonjour, 

    Je suis débutant en programmation et j'ai voulu essayer de trouver par moi même une solution a cet exercice. J'ai donc créer cette fonction, qui répond ( à peu près à l'exercice. Il y a tout de même quelques problèmes ( beaucoup à mon avis mai j'en ai trouvé que deux ) :

  _ on est obliger de mettre une liste vide comme argument de la fonction (je n'ai pas trouvé de moyen de mettre cette liste dans la fonction elle même sans que la liste ne s'éfface à chaque boucle)

_ Quand le mot à plusieurs fois la même lettre, cela créer des doublons dans les anagrammes, je ne sais pas comment m'en débarasser... ( je ne peux que les supprimer grace a une autre fonction)..

def anagramme(vide, string):
    import math
    string = list(string)
    for a in range (0, len(string)-1):
        string[a], string[a+1] = string[a+1], string[a]
        x = "".join(string)
        vide.append(x)
    if len(vide) != math.factorial(len(string)):
        anagramme(vide, string)


   ( si vous pouviez cdonner des critiques du code constructives ca serait super ! :) )

-
Edité par MrLukeHman 3 juin 2013 à 20:13:41

15 juin 2013 à 14:21:24

Plop.

Je suis retombé sur cet exercice alors que je cherchais à m'entraîner un peu sur lua. J'ai donc repris cet exo en lua pour me faire une idée. Le programme en lui-même semble beaucoup plus rapide et prendre beaucoup, beaucoup moins de mémoire puisque tout le traitement se fait sur un seul tableau "en-place" et l'équivalent d'un dictionnaire en minimisant au maximum les concaténations.

Le code, en revanche, est un peu plus compliqué puisque lua ne propose pas les mêmes facilités à haut niveau que Python pour traiter les chaînes de caractères et les tableaux, même si on retrouve le même mécanisme ultra-puissant de coroutines et de générateurs (en mieux). En fait le langage est plus minimaliste, mais c'est ce qui fait tout son charme et sa légèreté. Voilà le code au cas où ça intéresse quelqu'un :

#!/usr/bin/env lua

-- Counts the number of occurences for each character in given string
-- returns: an associative array with (letter <-> n_occurences)
function occurences (str)
    local res = {}
    for i = 1, #str do
        local c = str:sub(i, i)
        res[c] = (res[c] or 0) + 1
    end
    return res
end

-- Generates all words with given letters
-- * occurs: an associative array with (letter <-> n_occurences)
-- * word_len: length of the word
-- returns a generator function
function gen_anagrams (occurs, word_len, base, cur_idx)
    base = base or {}
    cur_idx = cur_idx or 0

    if cur_idx == word_len then 
        coroutine.yield(base)
    else
        for c, o in pairs(occurs) do
            if o > 0 then
                base[cur_idx+1] = c
                occurs[c] = o - 1
                gen_anagrams(occurs, word_len, base, cur_idx+1)
                occurs[c] = o
            end
        end
    end
end


-- Prints all anagrams of given string.
function anagrams (str)
    local occ = occurences(str)
    for res in coroutine.wrap(function() gen_anagrams(occ, #str) end) do
        print(table.concat(res, ''))
    end
end
           
if not arg[1] then
    print("Usage: " .. arg[0] .. " WORD")
    os.exit(1)
end

anagrams(arg[1])

-
Edité par nohar 16 juin 2013 à 10:58:26

Zeste de Savoir, le site qui en a dans le citron !
16 juin 2013 à 7:56:14

MrLukeHman a écrit:

  _ on est obliger de mettre une liste vide comme argument de la fonction (je n'ai pas trouvé de moyen de mettre cette liste dans la fonction elle même sans que la liste ne s'éfface à chaque boucle)

Ça, tu peux facilement t'en affranchir en donnant une valeur par défaut à l'argument "vide" (je le trouve pas très bien nommé...).

def anagramme(string, liste=[]):

Pour les doublons, c'est en effet toute la difficulté de cet exo. En fait, beaucoup de solutions proposées sur cet exo règlent ce cas de façon assez dégueu : ils génèrent d'abord tous les anagrammes avant de supprimer les doublons en transformant leur liste en set. Pour cet exercice, obtenir des résultats uniques en se basant sur la propriété d'unicité des clés d'une table de hash (set ou dict) est une très mauvaise idée : pour une chaîne comme "AAAAAAAAAAAAAAAAA" ça prend la vie à s'exécuter alors qu'il n'y a qu'un seul anagramme. Sur la page précédente tu trouveras ma solution (la version Python...) pour s'en affranchir sans perdre en perfs : il faut "penser comme au Scrabble".

PS : Et malheureusement, contrairement à ce qui a été dit plus haut, il n'existe pas de solution magique dans itertools pour générer les anagrammes. On en arrive à la deuxième erreur courante rencontrée sur ce thread : viser un code compact de quelques lignes grand max au détriment des performances et de l'utilisation de la mémoire. C'est bien joli de chercher à utiliser la bibliothèque standard de Python (et c'est un bon réflexe dans l'absolu), mais ce n'est certainement pas parce qu'une solution utilise un module pré-existant qu'elle est forcément meilleure. La preuve.

-
Edité par nohar 16 juin 2013 à 23:03:18

Zeste de Savoir, le site qui en a dans le citron !
17 juin 2013 à 20:52:22

Pour le fun:

f=lambda w,r=lambda b,s,n:(a for l in s for a in r(b+l,{k:(v-1 if k==l else v) for k,v in s.items()},n-1) if s[l]) if n else (b,):r('',{l:w.count(l) for l in w},len(w))

168 bytes (python3)

En (un peu) plus lisible:

f = lambda w, r=(lambda b,s,n:
                 (a for l in s for a in r(b+l,
                                          {k:(v-1 if k==l else v) for k,v in s.items()},
                                          n-1) if s[l]) if n else (b,)): \
                r('',{l:w.count(l) for l in w},len(w))



-
Edité par Gaber 17 juin 2013 à 20:58:14

6 août 2013 à 19:07:01

Bonjour,

J'essaye de faire cet exercice et je suis bloqué (j'ai peu d'expérience en programmation). J'ai trouvé une méthode pour trouver les anagrammes qui marche sur le papier et que j'ai écrite clairement. Ca donne ça :

Pour le mot:
    Renvoyer le mot
    et en créer un autre en permutant les deux premières lettres
Puis pour chacun des deux mots obtenus:
    en créer un autre en permutant la troisième et la deuxième lettre
    et un autre en permutant la deuxième lettre et la première lettre
    (à partir du mot obtenu)
Puis pour chacun des quatre mots obtenus:
    en créer un autre en permutant la quatrième lettre à la troisième lettre
    et un autre en permutant la troisième lettre et la deuxième
    et un autre en permutant la deuxième et la première lettre
Puis pour chacun des seize mots obtenus:
    en créer un autre en permutant la cinquième et la quatrième lettre,
    et ainsi de suite...

Modification : je me suis rendu compte que je n'avais pas tout les mots. Il faut appliquer chaque nouvelle permutation à tout les mots que l'on a déjà.

A partir de là j'ai fait des bouts de code pour permutter les lettres à l'intérieur du mot  :

#Le code qui permutte les deux premières lettres du mot:
    
set(chaine[:i]+chaine[i+1]+chaine[i]+chaine[i+2:]
    for i in range(0,1))

#Le code qui permutte la troisième et la deuxième lettre du mot:

set(chaine[:i]+chaine[i+1]+chaine[i]+chaine[i+2:]
    for i in range(1,2))

#Le code qui permutte la quatrième et la troisième lettre du mot:

set(chaine[:i]+chaine[i+1]+chaine[i]+chaine[i+2:]
    for i in range(2,3)

Voilà, maintenant l'idée pour pouvoir écrire la fonction, c'est que chacune ce ces lignes de code puisse s'appliquer aux résultats de la précédentes. Et là je sèche...Si quelqu'un peut m'indiquer comment faire...

PS: je sais que mon code ne sera de toute façon pas optimisé, et que tout ça doit pouvoir être factorisé mais j'en suis clairement pas encore là.


-
Edité par Flo963 21 août 2013 à 7:30:29

13 août 2013 à 2:05:39

Bonjour,

La méthode qui consiste à générer toutes les permutations de la chaîne de caractères avant de supprimer les doublons par une conversion vers le type set est bien sûr à proscrire.

Je vous propose un algorithme très compact (garanti 100% perso) qui utilise une méthode itérative.

Voici mon code:

def anagrammes(mot):
    anags = ['']
    for c in set(mot):
        for _ in range(mot.count(c)):
            anags = [s[:k+1]+c+s[k+1:] for s in anags for k in range(s.rfind(c),len(s))]
    return anags

Les anagrammes vont être construits par insertions successives de caractères dans les chaînes qui constituent la liste anags.

Au départ, cette liste ne contient qu'une chaîne vide.

Pour chaque caractère unique c de mot, et si on note n le nombre d'occurences de c dans mot, on effectue n fois l'opération qui consiste à effectuer toutes les insertions utiles (voir plus loin) du caractère c dans chacune des chaînes de anags.

Par insertions utiles d'un caractère c dans une chaîne s, j'entends toutes les chaînes obtenues en insérant c dans toutes les positions possibles à partir de la dernière occurence de c dans s (c'est là qu'on utilise la méthode rfind), donc à partir de la position 0 si c ne figure pas dans s (ce qui est le cas lors du premier passage dans la boucle for _ in range(...)). Cette idée permet de ne pas générer deux fois le même anagramme.

 >>> anagrammes('zorro')

['zrroo', 'rzroo', 'rrzoo', 'rrozo', 'rrooz', 'zroro', 'rzoro', 'rozro', 'rorzo', 'roroz', 'zroor', 'rzoor', 'rozor', 'roozr', 'roorz', 'zorro', 'ozrro', 'orzro', 'orrzo', 'orroz', 'zoror', 'ozror', 'orzor', 'orozr', 'ororz', 'zoorr', 'ozorr', 'oozrr', 'oorzr', 'oorrz']

voila, voila....

Edit de nohar: on va éviter la pub hors contexte, merci.

-
Edité par nohar 13 août 2013 à 11:36:10

www.mathprepa.fr (mathématiques et python en classe prépa)
13 août 2013 à 3:42:23

Rebonjour

Juste une petite amélioration de mon algorithme précédent, au prix d'une variable supplémentaire m, qui va mesurer la taille des chaînes s de la liste anags à un moment donné: au moment où on va effectuer les insertions utiles d'un caractère dans ces chaînes, celles-ci ont en effet toutes la même longueur. Il est donc plus efficace d'utiliser la variable m plutôt que de recalculer systématiquement les longueurs des chaînes s par len(s).

def anagrammes(mot):
    anags = ['']; m = 0
    for c in set(mot):
        for _ in range(mot.count(c)):
            anags = [s[:k+1]+c+s[k+1:] for s in anags for k in range(s.rfind(c),m)]
            m += 1
    return anags

Edit de nohar : pareil qu'au-dessus. Si tu veux faire de la pub pour ton site, mets-le en signature.

-
Edité par nohar 13 août 2013 à 11:37:06

www.mathprepa.fr (mathématiques et python en classe prépa)
13 août 2013 à 11:05:36

Et elle te fait gagner un facteur combien ton amélioration ?

Edit : C'est une question piège.

Le coût de l'appel à len est négligeable devant le nombre catastrophique de concaténations et de slices que tu réalises, de l'appel systématique à rfind (qui, contrairement à len, est en \(O(N)\)), du fait que tu crées une nouvelle liste, et tout ça à chaque itération.

C'est exactement ce que je disais plus haut :

nohar a écrit :

On en arrive à la deuxième erreur courante rencontrée sur ce thread : viser un code compact de quelques lignes grand max au détriment des performances et de l'utilisation de la mémoire.

Pour améliorer un code, il ne suffit pas de se demander combien d'appels à telle fonction on réalise : il faut vraiment tenir compte de la complexité de chaque fonction, sinon on se retrouve à faire des efforts pour s'affranchir de choses qui ne sont absolument pas handicapantes, au détriment de la lisibilité.

Donald E. Knuth :

Premature optimization is the root of all evil.

-
Edité par nohar 13 août 2013 à 11:55:28

Zeste de Savoir, le site qui en a dans le citron !
13 août 2013 à 11:25:50

Une piste ne serait-elle pas la recursivite? Generer un anagramme sur un mot de six lettres, c'est generer les anagrammes sur les mots de 5 lettres precedes des premieres lettres :

Je reviendrai plus tard poster cette solution car pour l'instant j'ai un probleme sur la touche "crochet" de mon clavier, mais voici l'idee :

FONCTION anagrame(chaine)
 Pour i de 0 a taille-1 faire :
   cloner la chaine
   retenir la lettre  a l'indice i et l'enlever du clone
   liste_partielle = anagrame(clone)
   pour tous les elements de liste_partielle preposer la lettre enlevee
   ajouter la liste_partielle a liste_finale
FIN pour
 RETURN liste_finale

-
Edité par artragis 13 août 2013 à 11:26:24

13 août 2013 à 11:30:46

artragis a écrit:

Une piste ne serait-elle pas la recursivite? Generer un anagramme sur un mot de six lettres, c'est generer les anagrammes sur les mots de 5 lettres precedes des premieres lettres :

Voilà, c'est exactement la solution que j'ai proposée (à la fois en Python et en lua) sur ce thread.

Zeste de Savoir, le site qui en a dans le citron !
13 août 2013 à 11:54:05

Ça ne t'empêche pas de le coder et ni le proposer ici pour t’entraîner hein.

-
Edité par nohar 13 août 2013 à 11:54:44

Zeste de Savoir, le site qui en a dans le citron !
13 août 2013 à 15:02:41

@nohar

Je crains que vous ne vous preniez un peu trop au sérieux, jeune homme, et je n'apprécie ni le tutoiement systématique, ni votre ton un peu condescendant.

Etes-vous ici chez vous pour vous permettre ce genre de remarques?

Quand vous aurez lu TAOCP autant que moi, vous pourrez sans doute me trouver une citation où Knuth fustige les faux gourous et les codeurs prétentieux.

J'ai dit que mon code était compact, et il l'est.

Je n'ai pas dit qu'il était optimal, car il ne l'est pas.

Et quand bien même, il fait exactement ce qu'on lui demande dans une situation raisonnable. Qui a besoin de calculer (et de lire) les anagrammes d'anticonstitutionnellement?

J'enseigne l'option info (Caml) en classe préparatoire depuis de nombreuses années, et je ne crois pas à avoir de leçons à recevoir en matière de calcul de complexité.

Commencez donc par donner (et prouver) un ordre de grandeur de la complexité (spatiale et temporelle) de votre algorithme (qui est facilement améliorable, c'est vrai que vous l'avez "pondu" en quelques minutes) et on en reparle.

www.mathprepa.fr (mathématiques et python en classe prépa)
13 août 2013 à 15:44:42

misterjmf a écrit:

@nohar

Je crains que vous ne vous preniez un peu trop au sérieux, jeune homme, et je n'apprécie ni le tutoiement systématique, ni votre ton un peu condescendant.

Je crains que TU ne te prennes trop au sérieux, en oubliant que nous sommes sur un site communautaire où, par tradition et depuis plus de dix ans, tout le monde se tutoie.

Etes-vous ici chez vous pour vous permettre ce genre de remarques?

Hmmm... Oui.

Quand vous aurez lu TAOCP autant que moi, vous pourrez sans doute me trouver une citation où Knuth fustige les faux gourous et les codeurs prétentieux.

J'ai dit que mon code était compact, et il l'est.

Certes, mais il est aussi illisible.

Je n'ai pas dit qu'il était optimal, car il ne l'est pas.

Toujours est-il que factoriser un appel à len dans ce cas ne sert absolument à rien devant le coût astronomique du reste de la ligne. Ce n'est pas moi qui ai qualifié ça d'amélioration, que je sache.

Et quand bien même, il fait exactement ce qu'on lui demande dans une situation raisonnable. Qui a besoin de calculer (et de lire) les anagrammes d'anticonstitutionnellement?

N'empêche qu'il est moche et que des solutions bien plus lisibles et élégantes ont été apportées par d'autres sur ce thread. Je trouve par ailleurs très dommage qu'un prof ne cherche pas à montrer une solution exemplaire.

J'enseigne l'option info (Caml) en classe préparatoire depuis de nombreuses années, et je ne crois pas à avoir de leçons à recevoir en matière de calcul de complexité.

Et c'est moi qui me prends trop au sérieux ?

Je n'ai pas besoin d'argument d'autorité pour dire que ce code est illisible, ni d'enseigner l'option info en prépa pour savoir que la fonction len sur les listes et les chaînes de caractères est en O(1) en Python, donc que stocker cet appel dans une variable n'a aucune incidence sur l'efficacité du code, puisque ce calcul de longueur est réalisé lors de la création d'un nouvel objet str : opération qui est réalisée 4 fois lors de l'évaluation d'une expression de type "slice + str + slice" (2 slices + 2 concaténations). En clair, cette modification n'a d'incidence que sur la lisibilité du code.

Désolé si je te blesse dans ton amour propre, mais c'est comme ça.

Zeste de Savoir, le site qui en a dans le citron !
15 août 2013 à 12:17:13

Mon code est compact, c'était ça l'idée, merci de le reconnaître.

Quand à dire qu'il est illisible, pas d'accord: j'ai expliqué son fonctionnement dans le détail, un programme c'est un code plus des explications, et c'est mon job.

Pour ce qui est de l'amélioration par la factorisation de l'appel à len(s), je persiste. Il s'agit ici d'une question d'hygiène générale: quand dans un scope donné on effectue des appels répétés (disons au moins trois) à une même fonction et que ces appels rendent une valeur constante, on utilise un identificateur pour y mettre cette valeur (à condition bien sûr de documenter l'usage de cet identificateur, ce que j'ai fait). Je crois sur ce point que Knuth serait d'accord.

Dernier point, sur la complexité: désolé mais je sais exactement ce que je fais en écrivant ce code. Faut pas prendre les gens pour des idiots, ça aide dans un site communautaire. Je ne découvre quand même pas aujourd'hui que "slice + str + slice" ça coûte ceci ou cela !!! J'ai voulu rester dans le type string tout du long, et je ne vois pas trop comment on peut créer les anagrammes d'un mot de n+1 lettres (à partir d'un sous-mot de n lettres) sans pratiquer des insertions de caractères dans des chaînes.

En résumé, je voulais fournir un code aussi court que possible, et qui soit un joli (désolé si c'est immodeste) exemple d'utilisation de liste en compréhension. Je n'ai jamais prétendu donner un temps d'exécution minimum, et ça n'était d'ailleurs demandé nulle part (faut lire l'énoncé, hein).

Il y a toutes sortes de critères qui rentrent en ligne de compte dans l'appréciation subjective qu'on peut donner d'un code: beauté de l'idée, rapidité d'exécution, concision, etc. Il n'y a pas de raison de tout sacrifier sur l'autel de la rapidité à tout prix.

Et pour terminer, j'ai trouvé ça comique qu'on me rappelle que rfind est en O(N) alors que dans le cas qui nous occupe, N est a priori inférieur à 10.

Donc la prochaine fois, au lieu de cette façon d'éditer un message sans prévenir, de parler de pub quand il s'agit d'information, et d'écrire des choses aussi péremptoires, j'attends un tout petit peu plus de tolérance.  

Dernière minute: je viens de vérifier, mon code est environ 10 fois plus rapide que le tien sur la chaîne de caractère "carambarmou". Voila qui achève de me mettre d'excellente humeur. 

Quelqu'un pourrait-il faire un comparatif des codes proposés jusque là (avec comme contrainte de former le résultat sur forme de liste des anagrammes, mais sans compter l'affichage de cette liste), sur des mots de taille raisonnable.

www.mathprepa.fr (mathématiques et python en classe prépa)
16 août 2013 à 3:11:52

@ nohar

Pour être plus honnête, mon code n'est pas 10 fois plus rapide, mais environ 6 fois (j'ai renommé les fonctions anagrammes du nom de leurs auteurs).

Donc, il est le plus court, il est le plus rapide, mais il est "moche", c'est ça? "illisible", c'est ça? Je me marre...

%timeit nohar('carambarmou')
1 loops, best of 3: 10.6 s per loop

%timeit misterjmf('carambarmou')
1 loops, best of 3: 1.77 s per loop


Maintenant, je peux te tutoyer, car je te connais mieux, mon p'tit gars :-)

Dernière info: quand je factorise l'appel à len(s), je gagne 10% en temps de calcul. Pas négligeable donc.

Et désolé si je t'ai blessé dans ton amour propre, mais c'est comme ça.



www.mathprepa.fr (mathématiques et python en classe prépa)
16 août 2013 à 17:08:37

misterjmf a écrit:

@ nohar

Pour être plus honnête, mon code n'est pas 10 fois plus rapide, mais environ 6 fois (j'ai renommé les fonctions anagrammes du nom de leurs auteurs).

Donc, il est le plus court, il est le plus rapide, mais il est "moche", c'est ça? "illisible", c'est ça? Je me marre...

Ok, on va essayer de calmer le jeu et de rester constructif, mais devant tant de snobisme ça va pas être facile.

Déjà, on va commencer par faire preuve d'un tout petit peu d'honnêteté intellectuelle, ça ne pourra pas faire de mal. Je suppose que tu compares ton code avec celui que j'ai posté sur la page précédente il y a un peu plus de trois ans. Replaçons les choses dans leur contexte : mon but n'était ni de faire un code compact, ni de faire la solution la plus rapide possible, mais simplement, pendant un trajet de train, de participer à l'exo en proposant une solution réaliste, lisible et acceptable. Dès le post qui a suivi le mien, il était acquis que ma solution n'était pas la plus rapide. Je ne l'ai d'ailleurs jamais prétendu.

Mais en parlant de réalisme :

arnaud@umad(prg)% ulimit -v 100000             
arnaud@umad(prg)% ./anagrams.py carambarmou                             
Traceback (most recent call last):
  File "./anagrams.py", line 13, in <module>
    anagrammes(argv[1])
  File "./anagrams.py", line 6, in anagrammes
    anags = [s[:k+1]+c+s[k+1:] for s in anags for k in range(s.rfind(c),m)]
  File "./anagrams.py", line 6, in <listcomp>
    anags = [s[:k+1]+c+s[k+1:] for s in anags for k in range(s.rfind(c),m)]
MemoryError

Ouch ! On dirait bien que 100 000 Ko d'espace virtuel, soit le double de la place occupée par mon OS (environnement de bureau compris), sont trop étroits pour ce code compact et vif comme l'éclair...

Line #    Mem usage    Increment   Line Contents
================================================
     4                             @profile
     5     8.438 MB     0.000 MB   def anagrammes(mot):
     6     8.453 MB     0.016 MB       anags = ['']; m = 0
     7     8.457 MB     0.004 MB       for c in set(mot):
     8    19.488 MB    11.031 MB           for _ in range(mot.count(c)):
     9   124.996 MB   105.508 MB               anags = [s[:k+1]+c+s[k+1:] for s in anags for k in range(s.rfind(c),m)]
    10   124.996 MB     0.000 MB               m += 1
    11   124.996 MB     0.000 MB       return anags

Une fonction qui prend 125 Mo de RAM juste pour générer les anagrammes d'une chaîne de 11 caractères, chez moi, c'est un gâchis monstrueux, et mon job, c'est en particulier de ne jamais commettre ce genre de trucs : alors non, je n'appelle pas ça un code propre puisqu'il fait crasher un Raspberry Pi (et même un netbook) sur "déshypothéquiez", sans parler de la confiance aveugle que ça demande de faire dès le départ au garbage collector. Tu imagines bien que lorsque tu parles d'« hygiène générale du code » à côté de ça, ça prête à sourire.

C'est pour cette raison que je me suis rapidement penché vers un générateur il y a trois ans, quitte à payer un overhead en temps d'exécution : tu peux fanfaronner que ta fonction met 6 fois moins de temps à trouver tous les anagrammes de "carambarmou", n'empêche que si je n'ai besoin que des dix premiers anagrammes d'"anticonstitutionnellement", la mienne (aussi perfectible qu'elle soit) me les servira instantanément. Et bien que tu aies éludé la question par anticipation dans un post précédent, je ne vois absolument aucune raison valable de se contenter d'un sous-ensemble strict du vocabulaire français sous prétexte que ce sont des cas "raisonnables" ; je suis sûr que cette excuse ferait beaucoup marrer les islandais.

Par ailleurs je ne sais pas ce qu'il en est aujourd'hui, mais quand je faisais l'option info en prépa il y a dix ans, outre le fait que ça m'ait dégoûté du CamL (c'est bête, mais il m'a fallu plusieurs années avant de me réintéresser à Haskell et Lisp après ça, donc je ne porte pas forcément cet enseignement dans mon coeur) je me souviens pourtant que l'on m'avait appris que deux fonctions n'étaient comparables que si elles associaient la même sortie à la même entrée... Mais trève de provocations gratuites, puisque je suppose que ça non plus, je n'ai pas besoin de le rappeler à quelqu'un qui a autant lu TAOCP. ;)

Puisque j'en suis à regarder ton code de plus près (vu que je t'ai suffisamment vexé pour que tu prennes le temps de me répondre deux fois de suite, autant te rendre la politesse en t'accordant un peu du mien), il faut quand même admettre que l'idée est plutôt jolie. Il serait d'ailleurs très intéressant de remplacer tes list comprehensions par des generator expressions, à mon avis.

Dernière info: quand je factorise l'appel à len(s), je gagne 10% en temps de calcul. Pas négligeable donc.

Pour moi ça l'est complètement, et si tu veux bien éviter de me faire dire n'importe quoi, c'était exactement le sens de ma remarque initiale : le prix de cet appel à len n'a aucune importance devant le coût global de cette ligne, et je voulais justement que tu précises ce que ça te faisait gagner pour de vrai, de façon à éviter de se faire de fausses idées en te lisant. J'ai pu paraître sec, mais il y avait une excellente raison à cela : sur ce forum, quotidiennement, on passe notre temps à détromper les débutants sur les "petites améliorations après coup", et sur l'importance des perfs dans un langage de script (par exemple quand on les voit passer des heures à dégueulasser un code qui traite des données quelconques "pour gagner en vitesse" alors que ces données sont récupérées dans la même boucle au travers d'une socket... et du coup envisager d'apprendre un autre langage juste parce qu'ils s'aperçoivent que leurs efforts leur ont fait gagner 50 ms sur une exécution de 2 minutes, et qu'ils reportent leur échec sur la nature interprétée de Python). C'est peut-être justement parce que l'on n'enseigne pas l'info au travers d'un langage purement académique à la nouvelle génération de l'élite française que l'on doit se battre tous les jours contre ce genre d'idées reçues sur ce forum, et ce depuis des années.

Ensuite, question lisibilité, tu dis plus haut que Knuth serait d'accord avec toi. Certes, mais je me demande ce qu'en penserait Von Rossum, même si là non plus, finalement, ça n'a pas une importance capitale. Je trouve néanmoins un len(word) beaucoup plus explicite et lisible qu'un m, personnellement. Tu me dis que ton job c'est "un code + des explications", je veux bien le croire venant d'un prof (il m'est d'ailleurs arrivé de donner des formations, donc j'y suis plutôt sensible), mais le mien c'est "un code qui s'auto-documente", tout simplement parce que dans le monde dans lequel je vis, ça coûte moins cher à livrer d'une part et à maintenir pour une personne tierce d'autre part. Je ne dis pas que c'est mieux ou moins bien, mais c'est le genre de choses que l'on ne montre à aucun débutant durant son apprentissage, donc pour moi c'est une lacune à combler.

Une autre déclaration qui me fait réagir est celle-ci :

J'ai voulu rester dans le type string tout du long

Pourquoi donc ?

Sincèrement. Pourquoi ne pas utiliser à la place un type mutable (comme une liste) ? Je sais par exemple qu'en lua il est beaucoup plus efficace de faire l'équivalent d'un join sur une liste plutôt que d'utiliser l'opération de concaténation sur les chaînes de caractères, et je subodore (quoique ça demande vérification) que ça doit être la même chose en Python.

Il y a toutes sortes de critères qui rentrent en ligne de compte dans l'appréciation subjective qu'on peut donner d'un code: beauté de l'idée, rapidité d'exécution, concision, etc. Il n'y a pas de raison de tout sacrifier sur l'autel de la rapidité à tout prix.

Ce n'est pas moi qui dirai le contraire. Les habitués de ce forum peuvent en témoigner.


Maintenant dans un tout autre registre :

Donc la prochaine fois, au lieu de cette façon d'éditer un message sans prévenir, de parler de pub quand il s'agit d'information, et d'écrire des choses aussi péremptoires, j'attends un tout petit peu plus de tolérance.

Ce sont les règles du forum : « Toute forme de publicité est interdite ». Et j'ai la tâche ingrate de les faire respecter (c'est ce que signifie le petit badge "Staff" à côté de mon pseudo). En ce qui concerne tes posts, j'ai appliqué ni plus ni moins les guidelines de la modération : si ce n'est pas du spam, et que le reste du post est constructif, on se contente d'un rappel à l'ordre. Dans ce cas précis, le lien n'avait pas de rapport direct avec le sujet, néanmoins, comme je l'ai dit dans mon édit, rien ne t'empêche de le faire figurer dans ta signature : c'est fait pour ça et c'est le seul endroit (avec la biographie sur le profil) où la pub au sens large est tolérée.

-
Edité par nohar 17 août 2013 à 5:51:41

Zeste de Savoir, le site qui en a dans le citron !
17 août 2013 à 5:54:29

Hello nohar

Enfin un message constructif, merci.

Mon petit programme, qui n'avait pas de prétention particulière (sauf celui de mettre à genoux un Raspberry Pi, et on dirait que c'est gagné!), il m'était venu un peu comme ça, en rêvant (ben oui, c'est comme ça que vienne les bonnes idées). Je ne m'attendais pas à un telle charge en retour, c'est vrai. Et j'ai pensé dans un premier temps que tu utilisais ton statut d'administrateur pour faire de l'intimidation.

Je ne connais pas très bien les règles de ce forum, donc désolé si je les ai enfreintes en mettant un lien vers mon site dans le corps même du message. Si tu vas y faire un tour, tu verras que je ne me monte pas du col, et que je mets pas mal de boulot perso en accès libre (et ça ne fait que commencer).

Sur l'encombrement mémoire, le mot carambarmou possède 11!/(3!2!2!) = 1663200 anagrammes, de 11 lettres chacun. Si on veut former leur liste, on consomme (au moins) 11* 1663200 = 18295200 caractères, soit dans les 20 Mo en majorant à peine. Tout programme qui forme la liste de ces anagrammes va saturer la mémoire d'un Raspberry Pi, et aussi celle d'un ZX-81, ou d'un Apple II, ou d'un TO-7. C'est pas ma faute, m'sieur.

Je suis d'accord pour le recours aux générateurs plutôt qu'aux listes. Je réfléchis (mollement tout de même) à une idée pour écrire une fonction anagrammes en ce sens. Comme l'algorithmique est une discipline qui me passionne, ce sujet m'intéresse. Ce que je voudrais, dans l'idéal, c'est écrire une fonction qui renvoie le n-ième anagramme d'un mot donné, dans l'ordre lexicographique, et en temps constant (de même qu'on peut facilement écrire une fonction donnant la n-ième permutation d'une liste d'éléments distincts), la difficulté tenant ici aux lettres qui apparaissent plusieurs fois.

Et ce qui me rendrait tout à fait heureux, c'est de savoir instantanément quel rang le mot carambarmou occupe dans la liste ordonnée de ses anagrammes. On a les plaisirs qu'on peut.

Merci encore d'avoir pris le temps de m'écrire le message précédent, j'apprécie.

www.mathprepa.fr (mathématiques et python en classe prépa)

[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