trouver les combinaisons possibles d'un tableau ?

**titoumimi** · 18/09/2006, 11h33

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

**jobherzt** · 18/09/2006, 11h43

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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
}

**Guigui_** · 18/09/2006, 11h46

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

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

**titoumimi** · 18/09/2006, 11h48

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

**titoumimi** · 18/09/2006, 11h52

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

**Jean-Marc.Bourguet** · 18/09/2006, 12h34

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

**billynirvana** · 18/09/2006, 12h40

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

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

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.

**titoumimi** · 18/09/2006, 12h55

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.

**Nemerle** · 19/09/2006, 15h02

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

EDIT il manquait un truc, j'ai corrigé

**titoumimi** · 19/09/2006, 15h12

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)