Bonjour à tous,

j'ai un problème d'algo ...

en gros j'ai un tableau qui contient des valeurs, disons : A B C D

j'aurais besoin à la fin de mon algo me retrouver avec ces valeurs :

A
B
C
D
AB
AC
AD
BC
BD
CD
ABC
ABD
ACD
BCD
ABCD


en gros toute les combinaisons possibles sans doublons (si AB est affiché, BA ne doit pas l'être)

Merci à tous ceux qui auront le courage de m'aider

Arnaud

Salut,
ça semble pas trop dur tu as besoin de quatre boucle imbriqués la première qui balaie les quatre valeur la deuxième qui balaie de la première valeur+1 jusqu'à quatre et ect.
En clair, parce que je m'exprime mal :

for i de 1 à 4
{
    afficher(tableau[i])
    for j de i+1 à 4
    {
        afficher(tableau[i]+tableau[j])
        for k de j+1 à 4
        {
             afficher(tableau[i]+tableau[j]+tableau[k])
             for l de k+1 à 4
                  afficher(tableau[i]+tableau[j]+tableau[k]+tableau[l])
        }
    }
}

On remarque que la dernière boucle sur l n'est appelé qu'une seule fois de 4 à 4 (après on a de 5 à 4 et elle n'est plus exécuté)

Après si la longueur de ton tableau est inconnue ou vaux 10 000 il faut généraliser cet algo en utilisant, par exemple, une fonction qui s'appelle elle même.

Salut et bon courage

Première idée, (si ta liste a un nombre variable d'elements bien sur, si c'est toujours 4, utilise 4 boucles imbriquées) utilise le principe du developpement :
Pour 3 :
f A [B; C; D] 3 -> [[A; B; C; D]]
Pour 2 :
f A [B; C; D] 2 -> [[A; B]; [A; C]; [A; D]]
f B [C; D] 2 -> [[B; C]; [B; D]]
f C [D] 2 -> [[C; D]]
Pour 1 (cas particulier) : [[A]; [B]; [C]; [D]]

Bonne continuation !

Effectivement, pour le cas général il faut utiliser une fonction récursive ("qui s'appelle elle-même"). La présentation de Biiinoit est bonne, mais si tu as du mal avec la récursivité il y a un tuto à ce sujet sur le SdZ.

PS : il ne traite pas l'exemple précis des combinaisons sans doublons, c'est plus pour te donner une intuition sur la récursivité. Ce topic (qui est une question qui revient souvent sur le forum) m'a donné envie de l'ajouter au tutoriel (avec les combinaisons avec doublon sans doute).

Salut et merci pour vos réponses !!

malheureusement c'est bien avec un tableau de n qu'il faut que je fasse ce programme

je me doutais pour la récursivité, je suis bien bien nul en cela,

je vais tester avec ton lien bluestorm

merci a vous

(si qqun à un algo tout fait en récursivité je suis preneur )

ciao

Avec des listes :

let rec combinate n l =
  if n = 0 then [[]] else
  match l with
  | [] -> []
  | h::t ->
      List.map (fun x -> h::x) (combinate (n-1) t) @ combinate n t

# combinate 3 [1;2;3;4];;
- : int list list = [[1; 2; 3]; [1; 2; 4]; [1; 3; 4]; [2; 3; 4]]

Il veut plutôt les combinaisons pour toutes les tailles de 0 à n :

let rec combinaisons = function
  | [] -> [[]]
  | h::t ->
      let sans_h = combinaisons t in
      sans_h @ List.map (fun x -> h :: x) sans_h

Ou alors en impératif, en réutilisant la méthode de Biiinoit :

soit combinaisons(comb,i,n):
  stocker la combinaison 'comb'
  si i < n:
    pour j de i à n-1:
      soit comb2 = la combinaison 'comb' à laquelle on rajoute 'j'
      combinaisons(comb2, (j+1), n)

let rec combi comb i n =
  stocker comb;
  if i < n then
    for j = i to n - 1 do
      combi (j :: comb) (j + 1) n
    done

Une petite contribution Prolog ne fera pas de mal :

% définition d'une combinaison de N éléments pris dans P
tuple(1, P, [X]) :-
        !,
        between(1, P, X).

% suite de la def
tuple(N, P, [X|[H|T]]) :-
        N1 is N - 1,
        tuple(N1, P, [H | T]),
        H1 is H - 1,
        between(1, H1, X).

% pour avoir tous les combinaisons de N éléments parmi P
tous_les_tuples(N, P, L) :-
        bagof(T, tuple(N, P, T), L).

% Pour avoir les combinaisons prises entre 1 et P éléments
tous_les_tuples(P, L) :-
        between(1, P, I),
        tous_les_tuples(I, P, L).

test(P) :-
       % Pour avoir toutes les combinaisons de 1 à P éléments
        bagof(L, tous_les_tuples(P, L),LL),
        append(LL, LC),
        maplist(writeln, LC).

Methodologie Prolog :
On définit d'abord ce qu'est une combinasion de N éléments pris parmi P
On indique ensuite à Prolog qu'on veut toutes les combinaisons de N éléments pris parmi P
On demande enfin qu'il donne toutes les combinaisons possibles pour P éléments.

Merci

Je vais tester l'algo sur du php, et je vous retourne tout ca

merci encore!!

joel76 : on peut quand même implémenter l'algorithme opérationnel en prolog :

combi([], [[]]).
combi([H|T], S) :-
        combi(T, Sans_H),
        findall([H|T2], member(T2, Sans_H), Avec_H),
        append(Avec_H, Sans_H, S).

combinaisons(N, S) :-
        findall(K, between(1, N, K), L),
        combi(L, S).

C'est nettement plus court, et plus efficace, puisque ta solution ne réutilise pas la solution de tous_les_tuples(N) pour calculer tous_les_tuples(N+1).

PS : y a-t-il un moyen plus simple de formuler que Avec_H, c'est l'ensemble des Sans_H avec H devant ?

Tu peux faire un

maplist(append([H]), Sans_H, Avec_H),

au lieu du findall, on gagne 40 inférences pour combinaisons(5, S).

En python ça pourrait donner cela

from itertools import combinations as comb
def combi(ch, n):
    for i in xrange(n+1):
        a=comb(ch, i)
            for j in a:
                print ''.join(j)

Euh, oui, mais dans tous les langages c'est très rapide à coder quand tu réutilises une bibliothèque logicielle qui fait exactement ça.

L'intérêt ici c'est de donner des implémentations de l'algorithme, et ton code n'en est pas une.

Je voudrais comprendre pourquoi dès que l'on parle d'algorithme, tout le monde débarque avec du code ?

Surtout venant de personnes qui jugent que mettre du code comme ça sur un forum, c'est absolument inutile ?

L'ago, c'est de la réflexion ou pas ?

Citation

Euh, oui, mais dans tous les langages c'est très rapide à coder quand tu réutilises une bibliothèque logicielle qui fait exactement ça.

Ouais je sais Bluestorm

Pourquoi faire simple quand on peut faire compliquer?

Je me demandais si en ocaml il existe une fonction permettant comme combinations avec python de faire ce genre de travail?

function combinaison($comb,$i,$n)
{
	$s_comb=$comb;
	echo "$comb<br/>";
	if($i<$n)
	{
		for ($j=$i;$j<=$n-1;$j++)
		{
		$comb2=$comb.$j;
		combinaison($comb2,$j+1,$n);
		}
	}
}

je vous aime les gars !! ca marche

je vais essayer de m'attarder un peu plus sur la récurrence dorénavant

merci bcp