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);
}