trouver les combinaisons possibles d'un tableau ?

Version imprimable

Bonjour à tous,

Suite à un sujet très interessant dans le forum PHP, je souhaiterai savoir comment vous auriez procédé pour ce problème :

Soit un tableau contenant des lettres (longueur non fixe) :
tableau = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i']

Comment feriez-vous pour obtenir toutes les combinaisons possibles de ces lettres sans doublons (interdit de retrouver la même lettre plusieures fois dans une même combinaison) ?

Pour le moment, l'algo qui semble le mieux marcher est le suivant :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 tableau = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i'] resultat = tableau pour i=0, i<longueur(tableau), i++ pour_chaque element1 de tableau1 pour_chaque element2 de resultat si element1 ne contient aucun élément de element2 temp = element1 concaténé à element2 fin si fin pour_chaque fin pour_chaque resultat = temp fin pour
pour un tableau de longueur 9, j'obtient 986400 itérations 'seulement' ;)

si vous avez de meilleures idées ;)

:merci:

le tableau initial contient il des doublons ?? tu me diras, sinon il suffit de les virer au prealable...

sinon, pourquoi ne pas faire du recursif ?? c'est un probleme qui l'appelle naturellement, il me semble. un truc du genre :
Code:

1 2 3 4 5 6 7 8 9 10 11 fonction combi(tableau tab, tableau cur) { si tab ne contient qu'un element stocker qqpart cur+ cet element. sinon : pour chaque element e de tab combi(cur+e, tab-e) ) finpour }

yep ici: http://python.developpez.com/sources...h#Combinatoire

Ca revient au calcul des Anp (si l'ordre compte) ou Cnp sinon.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def Anp(n, p, l=None, res=None):
    """ Created: 2005.11.05 - Updated: 2005.11.05
        Calcul de l'Anp - ne pas renseigne l et res lors de l'appel """    
    if l is None: l=[]
    if res is None: res=[]    
    if p==0:
        res.append(l)
        return
    for k in range(1,n+1):
        if k not in l:
            l1=list(l)
            l1.append(k)
            Anp(n, p-1, l1,res)
    return res

Code:

1
2
3
4
a=0
for i in range(1, 10):
    a += len(Anp(9, i))
print a

Par contre, je trouve a = 986409

18/09/2006, 11h48
titoumimi

Citation:

Envoyé par jobherzt

sinon, pourquoi ne pas faire du recursif ??

Mes premières versions étaient récursives, mais elles étaient très gourmandes, et je ne voit pas l'intérêt dans la dernière mouture l'intérèt du récursif ...

mais je vais tout de même essayer ton code ;)

:merci:
18/09/2006, 11h52
titoumimi

merci Guigui_, je regarde ça aussi, j'essaie de faire la traduction et je vous tiens au courant ;)

Titoumi, je ne comprends pas ton message initial, il y a une boucle sur i mais il me semble qu'à l'intérieur de la boucle on fait toujours la même chose.

Sinon, pour trouver toutes les permutations de n éléments ce qui me semble être la question initiale dans la discussion à laquelle tu te réfères, sans utiliser la récursion il y a
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 size = strlen(argv[1]); strcpy(permuted, argv[1]); do { printf("%s\n", permuted); i = size-1; while (i > 0 && permuted[i] <= permuted[i-1]) { --i; } if (i > 0) { j = size-1; while (permuted[j] <= permuted[i-1]) { --j; } tmp = permuted[j]; permuted[j] = permuted[i-1]; permuted[i-1] = tmp; } j = size-1; while (i < j) { tmp = permuted[j]; permuted[j] = permuted[i]; permuted[i] = tmp; ++i; --j; } } while (strcmp(permuted, argv[1]) != 0);
Un intérêt de cet algo, c'est qu'à partir d'une permutation, il trouve la suivante sans maintenir aucun état (le seul état qui est conservé, c'est la valeur de la permutation initiale pour savoir quand on est revenu au point de départ; si le point de départ est ordonné, on peut s'en passer).

Je prends les paris que mon code, écrit en¨ProLog, est le plus court et le plus simple.

Code:

1
2
3
4
5
6
7
8
permutation(nil, nil)->;
permutation(x.m, l)->
	permutation(m, l1)
	inserer(x, l1, l);
 
inserer(x, l, x.l)->;
inserer(x, y.l, y.l1)->
	inserer(x, l, l1);

Ce qui a été mis en rouge est le tableau en entrée.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
> permutation(1.2.3.1.nil, x);
{x=1.2.3.1.nil}
{x=2.1.3.1.nil}
{x=3.1.2.1.nil}
{x=1.1.2.3.nil}
{x=1.3.2.1.nil}
{x=2.3.1.1.nil}
{x=3.2.1.1.nil}
{x=1.2.1.3.nil}
{x=1.1.2.3.nil}
{x=2.1.1.3.nil}
{x=3.1.1.2.nil}
{x=1.3.1.2.nil}
{x=1.2.1.3.nil}
{x=2.1.1.3.nil}
{x=3.1.1.2.nil}
{x=1.1.3.2.nil}
{x=1.3.1.2.nil}
{x=2.3.1.1.nil}
{x=3.2.1.1.nil}
{x=1.2.3.1.nil}
{x=1.1.3.2.nil}
{x=2.1.3.1.nil}
{x=3.1.2.1.nil}
{x=1.3.2.1.nil}

Cordialement

18/09/2006, 12h51
Jean-Marc.Bourguet

Quand on utilise un langage fait pour explorer les arbres de possibilités, c'est facile. Mais il te reste à fixer le problème qui fait que si ta liste initiale contient un doublon, tu vas sortir deux fois certaines permutations. Mon programme C ne le fait pas.
18/09/2006, 12h55
titoumimi

Citation:

Envoyé par Jean-Marc.Bourguet

Titoumi, je ne comprends pas ton message initial, il y a une boucle sur i mais il me semble qu'à l'intérieur de la boucle on fait toujours la même chose.

Effectivement, le code dans ma boucle sur i fait toujours la même chose mais me sert à construire progressivement mes permutations jusqu'à la longueur désirée :

combinaisons initiales :
Array
(
[0] => a
[1] => b
[2] => c
)

après mon premier passage dans ma boucle sur i :

Array
(
[0] => ab
[1] => ac
[2] => ba
[3] => bc
[4] => ca
[5] => cb
)

et après le second passage :

Array
(
[0] => abc
[1] => acb
[2] => bac
[3] => bca
[4] => cab
[5] => cba
)

je le construit donc progressivement jusqu'à la longueur voulue en supprimant les doublons à chaque fois pour éviter les itérations inutiles.
19/09/2006, 15h02
Nemerle

1. si le tableau contient des doublons, on les vire (c'est plus rapide de les virer au début que de les garder)

2. Ensuite, si T[0...(N-1)] est le tableau contenant les N lettres de l'alphabet est qu'on veut les mots de longueur L sans doublon d'une même lettre, on peut produire un algo non récursif (pourquoi se compliquer la vie, ca, je ne sais pas, mais il doit surement y avoir une raison de taille de stack ). Grossièrement, tu gères

- une tableau d'entiers P[0,...,(L-1)] contenant les No des lettres dans T --> initialisation au départ à P[i]=i pour i de 0 à (L-1). A une itération donnée, la concaténation des éléments T[P[i]] te fournit un des mots désiré.

- un tableau de booléens b[0,...,(N-1)] indiquant (pour un P[] donnée) quelles sont les lettres en cours d'utilisation --> initialisation au départ à b[i]=true si i<L et false sinon.

- A une itération effectuée, où un P a fourni un mot par concaténation des éléments T[P[i]], il faut trouver le "P" suivant. Pour se faire:

- tu pars de P[L-1]. S'il est < à N-1, alors tu cherches le 1ier q vérifiant
P[L-1]<q<N et b[q]=false. Si il y en a un, c’est bon, tu fais b[P[L-1]]=false,
P[L-1]=q et b[q]=true. Sinon, tu fais comme si P[L-1]=N-1.

Si P[L-1]=N-1, tu cherches le plus grand k tel que P[k]<N-1 et tel que
il existe q vérifiant P[k]<q<N et b[q]=false (il en existe toujours un
si P[0]<N). Tu fais alors b[P[k]]=false, P[k]=q et b[q]=true, puis
tu remplaces les valeurs P[k+1],...,P[L-1] par les premières valeurs
v croissantes 0,1,2,... vérifiant b[v]=false (ça évite les doublons). Bien
sur, une fois les remplacements de P[k+1],...,P[L-1] effectués, tu mets
à jour ton tableau b[]

- tu termines tes itérations quand P[0]=N.

Y a pas plus rapide :mrgreen:

EDIT il manquait un truc, j'ai corrigé ;)
19/09/2006, 15h12
titoumimi

sans passer par la récursivité j'avait aussi trouver la solution de jouer avec les index des tableaux...

pour tout tableau tabl_1 de longueur n, on va créer un tableau tabl2 qui va contenir des index de tabl1 à combiner pour avoir notre solution.

pour obtenir ce tableau tabl2, rien de plus simple, il suffit de compter de 0 à ((n^n)-1) en base n, et hop, il ne reste plus qu'à dédoublonner, mais ça fait beaucoup trop d'itérations (n^n sans le dédoublonnage)
20/09/2006, 18h19
Nemerle

"mon algo ci-dessus est rapide ;) besoin d'un coup de main pour l'explication?
20/09/2006, 20h29
titoumimi

désolé, je n'ai pas eu de temps à y consacrer ces derniers jours :oops:

mais promis, je n'oublie pas, ça m'interesse fort, dè que je peux je retobe dedans et je vous tiens au courant ;)