Forums des Zéros

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).

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...

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...

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)

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

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 ...

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

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.

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.

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.

20 juillet 2010 à 3:28:24

oui je vois. merci pour ces explications.

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

20 juillet 2010 à 8:11:35

le but en fait c'etait de recoder permutations

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.

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 !

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 !

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

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

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" ?

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.

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

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:

)

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

J'avais pas pensé à cela, dommage, là je vois pas la parade

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"))

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 )

Qui aime bien châtie bien

Non, j'ai un bon fond (enfin j'espère) mais je sais pas mettre les formes !

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

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.

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 ?

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é).