Discussion :

[saad.hessane]

Bonjour tout le monde,
Je cherche à trouver les combinaisons d'un tableau trié, qui soit eux même trié.
Exemple :
A B C doit donner :

A
A B
A B C
A C
B
B C
C

Je crois que ça doit faire appelle à la récursivité, mais je ne sais vraiment par où commencer.

Mon analyse :
J'ai fais une petite analyse. Résonnons sur les indices des lettres.
A=>0
B=>1
C=>2

Les possibilités peuvent être écrite comme ceci :
0
0 1
0 1 2
0 2
1
1 2
2

On pourrait transformer ceci en matrice :
0 0 0
0 1 1
0 1 2
0 2 2
1 1 1
1 2 2
2 2 2

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
Pour i=0 à 2
  Pour j=i à 2
    Pour k=j à 2
      Prendre [i][j][k]
      Si i==j
        j suivant
      Sinon
        k suivant
      Fin Si
    Fin Pour k
  Fin Pour j
Fin Pour i

Mais ça doit être super lourd.
Avez vous une autre idée?

[pseudocode]

Je ne sais pas si tu as remarqué comme une légère répétition:

A
A B
A B C
A C
B
B C
C

Si tu arrives a trouver la combinaison avec juste des "B" et des "C", il suffit de rajouter un "A" devant et c'est pratiquement gagné. De là a trouver l'algo récursif, il n'y a pas loin.

[saad.hessane]

C'est pas con, je vais y réfléchir un peu.
Merci pour la réponse rapide.

[Zavonen]

Si tu veux un exemple récursif en Python:

Code python :

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
# -*- coding: latin-1 -*-
# comparaison des parties
def Avant(A,B):
    if A==B:
        return 0
    if A==[]:
        return +1
    if B==[]:
        return -1
    while A or B:
        if A[0]!=B[0]:
            return A[0]<B[0]
        else:
            return Avant(A[1:],B[1:])
 
# définition récursive d'un ensemble de parties
def Parts (E):
    if len(E)==0:
        return [[]] #cas de l'ensemble vide
    else:
        a=E[0] # on prelève le premier élément
        F=Parts(E[1:]) # appel récursif ensemble des parties de l'ensemble privé de son premier élément
        G=[X+[a] for X in F]
        G=F+G
        return G #et c'est fini!
 
#programme principal
def main():
    E=['a','b','c']
    PE=Parts(E)
    G=[]
    for X in PE:
        X.sort()
        G.append(X)
    G.sort(Avant)
    G.reverse()
    print G
 
if __name__ == '__main__':
    main()

[Trap D]

On peut en donner un aussi en Prolog :

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
27
28
29
% L  : Liste de départ
% LF : liste resultat finale
% toutes_les_sous_listes(L, LF) :-
%
% S'il n'y a qu'un seule élément, une seule liste
toutes_les_sous_listes([X], [[X]]):- !.
 
 
toutes_les_sous_listes([H | T], LF) :-
 
	% on extrait d'abord toutes les sous_listes
	% de la liste privées du premier élément
	toutes_les_sous_listes(T, L1),
 
	% On ajoute le premier élément à toutes
	% les sous-listes qui viennent d'être trouvées
	bagof( [H | X], member(X, L1), L2),
 
	% Et on construit la liste définitive avec
	% 1 : les premières sous_listes trouvées à la premiere ligne
	% 2 : les sous_listes construites à la deuxièmle ligne
	% 3 : sans oublier d'ajouter la sous-liste formée par l'élément lui-meme
	append([[H] | L2], L1, LF).
 
 
test(Depart) :-
	toutes_les_sous_listes(Depart, Fin),
	% on affiche le résultat,
	maplist(writeln, Fin).

Résutat :

20 ?- test([a,b,c]).
[a]
[a, b]
[a, b, c]
[a, c]
[b]
[b, c]
[c]

Yes

On peut écrire une version avec une philosophie "fonctionnelle", nettement plus performante (deux fois moins d'inférences) :

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
27
28
29
30
% L  : Liste de départ
% LF : liste resultat finale
% toutes_les_sous_listes(L, LF) :-
%
% ici on traite le cas de la liste vide
toutes_les_sous_listes([], []).
 
toutes_les_sous_listes([H | T], LF) :-
	% on extrait d'abord toutes les sous_listes
	% de la liste privées du premier élément
	toutes_les_sous_listes(T, L1),
	% On ajoute le premier élélement à toutes
	% les sous-listes qui viennent d'être trouvées
 
        % le côté "fonctionnel"
	maplist(ajoute_element_en_tete(H), L1, L2),
 
	% Et on construit la liste définitive avec
	% a : les premiers sous_listes trouvées à la premiere ligne
	% b : les sous_listes construites à la deuxièmle ligne
	% c : sans oublier d'ajouter la sous-liste formée par l'élément lui-meme
	append([[H] | L2], L1, LF).
 
% le prédicat "fonctionnel"
ajoute_element_en_tete(X, L, [X|L]).
 
test(ListeInitiale) :-
	toutes_les_sous_listes(ListeInitiale, SousListes),
	% on affiche le résultat,
	maplist(writeln, SousListes).

[pseudocode]

Ah... je ne savais pas qu'il y avait un concours.

Code java :

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
27
28
29
30
31
32
33
34
 
public static Stack<String> combination(Stack<Character> characters) {
	Stack<String> result = new Stack<String>();
 
	// la liste des carateres est vide => resultat vide
	if (characters.isEmpty()) return result;
 
	// retire le 1er caractere le la liste
	Character first = characters.remove(0);
 
	// calcule les sous-combinaisons avec les caracteres restants
	Stack<String> subcombination = combination(characters);
 
	// ajoute: le caractere seul
	result.add(first.toString());
 
	// ajoute: le caractere seul devant chaque sous-combinaison
	for(String s:subcombination)
		result.add(first+s);
 
	// ajoute: les sous-combinaisons
	result.addAll(subcombination);
 
	return result;
}
 
public static void main(String[] args) {
	Stack<Character> stack = new Stack<Character>();
	stack.push('A'); stack.push('B'); stack.push('C');
 
	Stack<String> resultats = combination(stack);
	for(String s:resultats)
		System.out.println(s);
}

[Jedai]

Code Haskell :

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

1
2
3
4
5
6
7
8
9
10
11
{- Le code demandé calcule en fait les parties d'un ensemble 
modélisé comme une liste ordonnée .
Le nom anglais pour Parties() est powerset, nous l'utiliserons ici -}
 
-- powerset prend une liste d'élément et renvoie une liste de listes
powerset :: [a] -> [[a]]
-- la seule partie de l'ensemble vide est l'ensemble vide
powerset [] = [[]]
-- P( {x1} u {x2, x3, .. xn } ) = (U_{p in P( { x2, .. xn } ) {x1} u p) u P( { x2, .. xn } ) 
powerset (x:xs) = map (x:) psXs ++ psXs
  where psXs = powerset xs

On peut faire un peu plus rapide et moins gourmant en mémoire avec :

Code Haskell :

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

1
2
3
4
5
6
powerset [] = [[]]
powerset (x:xs) = interleave (map (x:) psXs) psXs
  where psXs = powerset xs
 
interleave [] ys = ys
interleave (x:xs) ys = x : interleave ys xs

--
Jedaï

[Trap D]

Et maintenant en Scheme, améliorable sans doute

Code :

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

1
2
3
4
5
6
7
8
9
10
11
(define (ajoute-en-tete-element elem lst)
  (map (lambda x
         (cons  elem (car x))) lst))
 
(define (toutes-les-sous-listes lst)
  (cond ((null? lst) lst)
        (else (let* ((tete (car lst))
                    (reste (cdr lst))
                    (resultat (toutes-les-sous-listes reste))
                    (lst (ajoute-en-tete-element tete resultat)))
                (append (list (list tete)) lst resultat)))))

[Trap D]

Pour finir, un code en C, beaucoup plus bavard

Code C :

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
// structure utile pour savoir le nombre de listes déjà existantes
typedef struct
{
	int nb;
	char **ssliste;
} s_combinaisons;
 
 
// la seule et unique fonction, récursive
// elle a le tort de modifier son argument combi
void toutes_les_sous_listes(s_combinaisons *combi, char *lst)
{
       // au cas où ...
	if (lst == NULL || combi == NULL)
	{
		fprintf(stderr, "Lst ou combi NULL\n");
		exit(EXIT_FAILURE);
	}
 
	if (strlen(lst) == 0)
	{
		combi->nb = 0;
		combi->ssliste = NULL;
	}
	else
	{
		int i;
		char **stmp;
               // on récupère les sous-listes créées avec la chaînes sans le premier caractère
		toutes_les_sous_listes(combi, lst+1);
               //on met à la bonne taille le pointeur contenant les sous-listes
		stmp = realloc(combi->ssliste, (2 * combi->nb + 1) * sizeof (char **));
		if (stmp == NULL)
		{
			// liberation de la memoire
			int i;
			for(i = 0; i < combi->nb; i++)
				free(combi->ssliste[i]);
 
			free(combi->ssliste);
 
			fprintf(stderr, "realloc NULL\n");
			exit(EXIT_FAILURE);
		}
		combi->ssliste = stmp;
               // on ajoute les nouvelles sous-listes créées en ajoutant la première lettre
		for(i = 0; i < combi->nb; i++)
		{
			combi->ssliste[i + combi->nb] = malloc(strlen(combi->ssliste[i])+ 2);
			if (combi->ssliste[i + combi->nb] == NULL)
			{
				int k;
				for(k = 0; k < combi->nb; k++)
					free(combi->ssliste[k]);
 
				for(; k < combi->nb + i - 1; k++)
					free(combi->ssliste[k]);
 
				free(combi->ssliste);
				fprintf(stderr, "combi->ssliste[i] NULL\n");
				exit(EXIT_FAILURE);
			}
			combi->ssliste[i + combi->nb][0] = lst[0];
			strcpy(combi->ssliste[i + combi->nb]+1, combi->ssliste[i]);
		}
               // et on n'oublie pas d'ajouter la liste formée par la première lettre
		combi->ssliste[i + combi->nb] = malloc(2);
		if (combi->ssliste[i + combi->nb] == NULL)
		{
				int k;
				for(k = 0; k < combi->nb; k++)
					free(combi->ssliste[k]);
 
				for(; k < combi->nb + i - 1; k++)
					free(combi->ssliste[k]);
 
				free(combi->ssliste);
				fprintf(stderr, "combi->ssliste[i] NULL\n");
				exit(EXIT_FAILURE);
		}
		combi->ssliste[i + combi->nb][0] = lst[0];
		combi->ssliste[i + combi->nb][1] = 0;
		combi->nb = 2 * combi->nb + 1;
	}
}
 
int main(void)
{
	int i;
	s_combinaisons cval = {0, NULL};
	toutes_les_sous_listes(&cval, "ABC");
 
	for(i = cval.nb - 1; i >= 0; i--)
	{
		puts(cval.ssliste[i]);
               // on laisse l'environnement propre
		free(cval.ssliste[i]);
	}
        // on laisse l'environnement propre
	free(cval.ssliste);
	return EXIT_SUCCESS;
}

[PRomu@ld]

Je pense que ça suffit

Le tout est d'attendre si le PO a une solution qui lui convient.

[pseudocode]

Je pense que ça suffit

Ce forum est beaucoup trop performant.

[saad.hessane]

Merci beaucoup pour les codes, je vous remercie vraiment.
Je voulais le faire en C ou en C++, et donc le code C est celui qui me convient le plus.
Mais si j'ai poster dans le forum algo, c'est pour qu'on me donne une explication, plus que l'on me donne du code.
Je sentais bien que c'est une récursivité qu'il fallait faire, mais comment vous faites pour trouver l'algorithme aussi facilement? C'est de l'expérience, y a t il une méthode?
Car là même avec le code sous le nez j'ai du mal à comprendre (algorithmiquement) le code.
Merci à vous, et désoler du retard.

[Zavonen]

Serait peut être temps de donner une version dérécursivée;

Code python :

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

1
2
3
4
5
6
7
8
def PartsOf(E):
    P=[[]]
    while E:
        a=E[0]
        E=E[1:]
        Q=[x+[a] for x in P]+P
        P=Q
    return P

[saad.hessane]

Merci beaucoup Zavonen, mais si c'est possible que tu m'expliques un peu ce que tu fais, et surtout comment tu fais. Si c'est de l'expérience qu'on acquiert avec le temps c'est pas grave, mais s'il y a vraiment une technique à cela je voudrais bien l'apprendre.
Je ne m'y connais pas en python, mais de voire la variable P[[]] sans type ça me fais penser aux array à deux dimensions de PHP. Je suppose donc que le python est un langage assez haut niveau pour permettre ce genre de chose.
C'est pourquoi je veux avoir une technique, pour que si aujourd'hui je veux le faire en C, il se peux que demain je veuille le faire en JAVA ou en C++.
Alors si quelqu'un pouvais m'expliquer d'une façon un peu algorithmique son code.
Merci infiniment à vous tous.

[Zavonen]

Python est un langage de très haut niveau, qui manipule les listes sans bibliothèques supplémentaires.
[] désigne la liste vide NIL en Lisp etc..
[[]] désigne la liste contenant un seul élément, cet élément étant l'ensemble vide. OK ?
En Python, comme dans (presque) tous les langages A[0] représente le premier élément, la tête de liste. (en lisp schemme, etc.. c'est CAR).
En Python A[1:] représente la queue de liste (LISP SCHEME: CDR)
Ce que je fais maintenant c'est une boucle itérative.
Supposons que E=[1,2,3]
au départ P=[[]]
Je prélève le premier élément de E en remplaçant E par sa queue de liste
Je place ce premier élément en tête de tous les éléments de P et je concatène le résultat à P.
J'obtiens donc: comme nouvelle valeur de P: [[1]]+[[]] = [[1],[]]
E vaut cette fois [2,3]
On recommence l'opération:
P vaut [[2,1],[2]]+[[1],[]]
et ainsi de suite.
Si tu n'a pas compris n'hésite pas à reposer des questions.

[pseudocode]

Je sentais bien que c'est une récursivité qu'il fallait faire, mais comment vous faites pour trouver l'algorithme aussi facilement? C'est de l'expérience, y a t il une méthode?

Les 2 .

Tu peux partir d'une constatation "visuelle" comme je l'ai fait au post #2. L'algo recursif va donc transformer le probleme a N elements en un problème a N-1 elements:

Solution(ABC)=A,A*Solution(BC),Solution(BC)
Solution(BC)=B,B*Solution(C),Solution(C)
Solution(C)=C

Tu peux aussi utiliser des connaissances mathématique et reconnaitre un produit cartésien de listes:
Solution = ['',A]x['',B]x['',C] = ['',A]x['',C,B,BC] = ['',C,B,BC,A,AC,AB,ABC]

[saad.hessane]

@Zavonen :

En Python A[1:] représente la queue de liste

La queue de liste c'est le reste de la liste à partir de l'élément indiquer?
Exemple A[0,1,2,3]
A[0] tête de liste;
A[1:] Queue de liste est équivalente à B[2,3]
J'ai bien compris?

@pseudocode

Solution(ABC)=A,A*Solution(BC),Solution(BC)
Solution(BC)=B,B*Solution(C),Solution(C)
Solution(C)=C

T'es le plus fort!
Mais rien compris sur le truc des produits cartésiens.

[Zavonen]

Voilà à peu près ce que donne en C 'basique' mon algo itératif.
On peut apprécier la différence entre un langage de script et un langage 'système' ...

Code c :

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include <stdio.h>
#include <stdlib.h>
 
//NB ce que nous appelons ici listes sont en fait des tableaux dynamiques
/***** Le type liste de caractères (par exemple) *********/
typedef struct
{
    unsigned int nc; // nombre de charactères
    char* lc; // pointeur sur tête de liste
} listchar;
 
 
char CAR (listchar L)
{
    return L.lc[0];
}
 
listchar CDR (listchar L)
{
    unsigned int i;
    listchar cdr;
    cdr.nc=L.nc-1;
    cdr.lc = (char *) malloc(L.nc);
    for (i=1;i<L.nc;i++)
        cdr.lc[i-1]=L.lc[i];
    if (cdr.nc==0)
        cdr.lc=NULL;
    return cdr;
}
 
listchar CONS(char C, listchar L)
{
    unsigned int i;
    listchar cons;
    cons.nc=L.nc+1;
    cons.lc= (char *) malloc(cons.nc);
    cons.lc[0]=C;
    for (i=1;i<=L.nc;i++)
        cons.lc[i]=L.lc[i-1];
    return cons;
}
 
void initlc (listchar * pL,unsigned int n, char* LC)
{
    unsigned int i;
    pL->nc=n;
    if (n==0)
        pL->lc=NULL;
    else
    {
        pL->lc=(char *) malloc(n);
        for (i=0;i<n;i++)
            pL->lc[i]=LC[i];
        pL->lc=LC;
    }
}
 
void affichelc(listchar L)
{
    unsigned int i;
    printf("{");
    if (L.nc>=2)
        for (i=0;i<L.nc-1;i++)
            printf("%c,",L.lc[i]);
    if (L.nc>=1)
        printf("%c",L.lc[L.nc-1]);
    printf("}");
}
 
/*************** fin de liste de caractères*************/
 
/************le type liste de listes *******************/
typedef struct
{
    unsigned int nl; // nmbre de listes
    listchar * ll; // pointeur sur première liste
} listlistchar;
 
 
void initllc(listlistchar *pLL, unsigned int n, listchar * LLC)
{
    unsigned int i;
    pLL->nl=n;
    if (n==0) pLL->ll=NULL;
    else
    {
        pLL->ll=(listchar *)malloc(n*sizeof(listchar));
        for (i=0;i<n;i++)
            initlc(&(pLL->ll[i]),LLC[i].nc,LLC[i].lc);
    }
 
}
 
listlistchar APPEND (listlistchar L1, listlistchar L2)
{
    unsigned int i,j,h;
    listlistchar append;
    append.nl=L1.nl+L2.nl;
    append.ll=malloc(append.nl*sizeof(listchar));
    h=0;
    for (i=0;i<L1.nl;i++)
        initlc(append.ll+h++,L1.ll[i].nc,L1.ll[i].lc);
    for (j=0;j<L2.nl;j++)
        initlc(append.ll+h++,L2.ll[j].nc,L2.ll[j].lc);
    return append;
}
 
void affichellc(listlistchar LLC)
{
    unsigned int i;
    printf("{");
    if (LLC.nl>=2)
        for (i=0;i<LLC.nl-1;i++)
            affichelc(LLC.ll[i]);
    if (LLC.nl>=1)
        affichelc(LLC.ll[LLC.nl-1]);
    printf("}\n");
}
/***************fin du type liste de listes********************/
 
 
listlistchar Parties (listchar E)
{
    listlistchar P;
    listlistchar Q;
    listchar V;
    unsigned int i;
    unsigned char c;
    initlc(&V,0,NULL);
    initllc(&P,1,&V);
    listchar * TL;
    listchar * SL;
    while (E.nc>=1)
    {
        c=CAR(E);
        E=CDR(E);
        for (i=0;i<P.nl;i++)
            initlc(TL+i,P.ll[i].nc,P.ll[i].lc);
        for (i=0;i<P.nl;i++)
            SL[i]=CONS(c,TL[i]);
        initllc(&Q,P.nl,SL);
        P=APPEND(Q,P);
    }
    return P;
}
 
int main()
{
    listchar L0;
    listlistchar P;
    char T[]={'1','2','3'};
    initlc(&L0,3,T);
    P=Parties(L0);
    affichellc(P);
    return 0;
}

[saad.hessane]

Merci beaucoup Zavonen, résolu.