Discussion :

[mail.spam]

Bonjour,
je cherche l'algorithme qui donne le nombre de combinaison possible.
Je m'explique j'ai un nombre x d'élément et je cherche à connaitre toutes les combinaison possible.

Exemple j'ai 1 2 3
et je veux énumérer la liste suivante
1
1 2
1 3
1 2 3
2
2 3
3

Connaissez vous l'algorithme
Merci pour votre aide

[SpiceGuid]

Pour le dénombrement :
http://fr.wikipedia.org/wiki/Coeffic...et_statistique



(dans cette formule l'ensemble vide k=0 est considéré comme une solution)

Le dénombrement est constructif, il te donne un algorithme.
Ici il suffira d'énumérer toutes les combinaisons pour k=1 jusqu'à k=n.

[mail.spam]

Merci.
J'ai besoin maintenant d'énumérer cette liste
mais je ne vois pas trop comment faire

[millie]

C'est en fait assez simple.

Si t'as un ensemble S qui contient un élément a et un sous ensemble S' = S-{a}.

L'ensemble des combinaisons de S est l'ensemble des combinaisons de S' + l'ensemble des combinaisons de S' concaténé avec a.

Et si S est l'ensemble vide, il n'y a pas de combinaisons possibles.

C'est donc une propriété récursive qui permet d'écrire ceci

[mail.spam]

MOUAIS..
J'ai pas tout compris.
Si on pouvais m'expliquer ça autrement ça serai gentil.

[millie]

Si on prend l'ensemble : [1,2,3]

Si je note comb(S) la fonction qui donne l'ensemble des combinaisons d'un ensemble
Je note concat(n, C) la concaténation de n à à l'ensemble de combinaisons C
Par exemple :
concat(n, [[1,2,3], [1,2]) = [ [1,2,3,n], [1,2,n] ]

J'ai dit que :
comb([1,2,3]) = concat(1, comb([2,3])) UNION comb([2,3])

Faut calculer comb([2,3]) =
concat(2, comb([3]) UNION comb([3])

Puis comb([3]) = concat(3, comb([])) UNION comb([])) = [[3], []]
(car comb([]) = [[]])

Donc comb([2,3]) = concat(2, [[3],[]]) UNON [[3],[]] = [[2,3], [2], [3], []]
Donc comb([1,2,3]) = concat(1, [[2,3], [2], [3], []) UNION [[2,3], [2], [3], []) = [[1,2,3], [2,1], [3,1], [1], [2,3], [2], [3], []]

[SpiceGuid]

Code Caml :

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

1
2
3
4
5
let rec power_set = function
  | [] -> [[]]
  | a::l ->
      let t = power_set l
      in  List.append (List.map (fun x -> a::x) t) t

Exemple:

Code Caml :

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

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

[millie]

@SpiceGuid : c'est tout à fait à ça que je pensais. J'ai pas voulu l'écrire car j'avais désinstallé caml de l'ordi... et je voulais pas filer un truc de 3 lignes non testé

[mail.spam]

Je suis vraiment désolé, j'aurai du le dire depuis le début.

Je débute dans la programmation, et je code en Windev.

Après avoir fait d'autre recherche je suis tomber sur ce bout de code

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
fonction permutation(tableau, permutation)
debut
  si tableau est vide alors
    afficher la permutation
  sinon
    pour tous les éléments a du tableau faire
      tableau1 <- tableau - a
      permuation1 <- permutation + a
      permutation(tableau1, permutation1)
    fin pour
  fin si
fin

Mais je n'arrive pas à le mettre en place.
Est-ce bon pour ce que je veux faire?

[mail.spam]

Ca y est, j'ai réussi.
Merci pour votre aide.

Le bout d'algo fonctionne, fallait juste que j'arrive à le transposer en code.