Discussion :

[sm1z2000]

Bonjour,
Je suis coince sur une partie ou je dois generer toutes les combinaisons exemple:
(n n n t t t t)->(0 1 2)
(n n t n t t t)_>(0 1 3)
ainsi de suite et biensur eviter les cas ou les n se superpose exemple (0 3 3)...
J'ai essayer de faire un code qui s'est vite transforme en usine a gaz de plus il ne marche pas pour un cas n.
Du coup apres recherche j'ai trouve un algo en recursif que j'arrive pas a faire fonctionner:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
procedure Cnp(n, p, liste) 
 
   si p = 0 alors 
      begin      
      affiche liste 
      fin de la procedure 
      end 
 
    si n = 0 alors fin de la procedure 
 
    cnp(n-1,  p-1,  liste + {élément numéro n}) 
    cnp(n-1,  p,    liste)

Pensez vous qu'il est juste?
Si oui je serai reconnaissant si vs m'aidiez a le developper.
merci a vous

[Trap D]

Je dois avoir du caca dans les yeux, mais je ne comprends pas pourquoi

(n n n t t t t)->(0 1 2)
(n n t n t t t)->(0 1 3)

[sm1z2000]

Je developpe:
(n n n t t t t)->(0 1 2)
(n n t n t t t)->(0 1 3)
(n n t t n t t)->(0 1 4)
(n n t t t n t)->(0 1 5)
(n n t t t t n)->(0 1 6)
(n t n n t t t)->(0 2 3)

(0 1 2) correspond a la position ou l'index des n dans la list
J'espere que c'est ca la reponse a ta question.

[Garulfo]

Je dois avoir du caca dans les yeux, mais je ne comprends pas pourquoi

C'est effectivement très mal expliqué. @sm — tu permets que je t'appelles sm ? — il faut que tu expliques ce que tu fais en ne supposant pas qu'on ait l'exercice devant les yeux. Si je ne le connaissais pas celui-ci je ne suis pas sûr que j'aurais compris.

@Trap il faut afficher toutes les combinaisons possibles de 3 parmi 7.

[sm1z2000]

euh... ok pour sm
En fait ce que je veux c'est generer toute les positions qui correspondent aux combinaisons des n parmis les t pour liste un cas genreal(p parmis n).
Garulfo j'ai deja poste une question pour la generation des buffers. ce n'est plus le cas ici puisque j'ai resolu le probleme.
j

[Jedai]

voyons, il te faut donc générer une liste de p nombres dans l'ordre, chacun étant dans un intervalle facilement déterminé par sa position dans la liste générée et le nombre le précédent dans cette liste ? Je rajoute le terme "récursivité" comme bonus et même une petite implémentation en Haskell :

Code Haskell :

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

1
2
3
4
combinations p n = go p 0 (n - p)
  where
    go 0 _ _ = [[]]
    go p begin close = [ x:xs | x <- [begin..close], xs <- go (p-1) (x+1) (close + 1) ]

Bonne chance

--
Jedaï

[Trap D]

Et 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
tuple(1, P, [X]) :-
	!,
	between(1, P, X).

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

tous_les_tuples(N, P, L) :-
	bagof(T, tuple(N, P,T), L).

[sm1z2000]

Merci pour la collaboration en Prolog et Haskell. Mais j'aurais besoin d'un code en scheme..d'ailleurs c'est un forum scheme. Prolog et Haskell ne me disent rien.
Par contre je n'ai pas eu de reponse par rapport a l'algo suivant:

procedure Cnp(n, p, liste)

si p = 0 alors
begin
affiche liste
fin de la procedure
end

si n = 0 alors fin de la procedure

cnp(n-1, p-1, liste + {élément numéro n})
cnp(n-1, p, liste)

est il correct?
De ma part je pense avoir trouve la solution mais comme j'ai dit c'est tordu et un algo recursive me semble plus adequat.
Merci en tt cas pour vos proposition

[Jedai]

Ton algo est exprimé sous une forme bien trop impérative : des if sans else, des "fins de procédures"... Scheme est un langage fonctionnel, transcrire directement ton algo serait inélégant au possible. Sans parler du fait qu'il n'est pas clair : que diable veut dire "{élément numéro n}" ?

L'algo que j'ai implémenté en Haskell est très simple : il génère les positions une à une en explorant toutes les possibilités (l'intervalle est facile à déterminer) et les cons devant chacune des listes possibles pour la suite (obtenues récursivement).

--
Jedaï

[sm1z2000]

oui je suis tt a fait d'accord, en fait j'ai recuperer l'algo, sur le furom dedie aux algos.
Peux tu stp me commenter ton code ou encore le traduire en scheme ou lisp.
car apres je dois le traduire en un autre langage.
Merci

[Garulfo]

oui je suis tt a fait d'accord, en fait j'ai recuperer l'algo, sur le furom dedie aux algos.
Peux tu stp me commenter ton code ou encore le traduire en scheme ou lisp.
car apres je dois le traduire en un autre langage.
Merci

C'est à toi de trouver l'algorithme. Si tu n'en as pas, alors c'est dans le forum algo qu'il faut aller le chercher. Un bon algo bien formulé s'affranchira en partie du problème du langage d'implémentation.

Revenons donc au base : fais l'exercice sur papier et regarde ce que tu fais. Si tu ne sais pas le faire, tu ne sauras pas l'automatiser. Ensuite exprime en français ce que tu veux faire. Puis essaye d'en faire un algorithme. Si tu n'as pas d'algorithme, tu seras incapable de l'écrire en un langage quelconque de toute façon -_-

Jedai t'a indiqué la voie, jeune padawan

[sm1z2000]

bon, je sens que ca juge dans tout les sens par ici.
Mon premier post etait une question assez simple: Est ce que l'algo etait bon? si oui pourrai je avoir de l'aide pour le developper.
Donc si tu ne peux pas m'aider abstiens toi de me juger.

Pour le fait d'ecrire sur papier le probleme, j'y suis dedans, et j'ai trouve la solution, mais comme j'ai dit ca prend trop de temps d'execution.
Donc si TrapD ou Jedai peuvent me traduire leur code ca serait pas mal.

Allez bonne journee, et merci a tous.

[Trap D]

Tu as tort de le prendre come ça, on t'a déjà dit que ton algo était orienté impératif, or tu veux le traduire en Scheme qui est un langage fonctionnel, il faut que tu écrives un algo orienté fonctionnel, je veux bien croire que celà soit difficile si tu n'as jamais fait de fonctionnel.

Pour ma part, Prolog étant un langage déclaratif, on ne peut pas traduire directement le code en Scheme, et malheureusement n'étant pas très fort en focntionnel, je ne puis pour le moment pas t'aider. désolé.

Médite tout de même ces réflexions de Jedai :

voyons, il te faut donc générer une liste de p nombres dans l'ordre, chacun étant dans un intervalle facilement déterminé par sa position dans la liste générée et le nombre le précédent dans cette liste ?

L'algo que j'ai implémenté en Haskell est très simple : il génère les positions une à une en explorant toutes les possibilités (l'intervalle est facile à déterminer) et les cons devant chacune des listes possibles pour la suite (obtenues récursivement).

[sm1z2000]

Merci trapD. C'est assez constructif ce que me dis la.
pour ce qui est du reste. Je voulais remettre les choses a leur place pour que ca ne derape pas trop.

Envoyé par Jedai
L'algo que j'ai implémenté en Haskell est très simple : il génère les positions une à une en explorant toutes les possibilités (l'intervalle est facile à déterminer) et les cons devant chacune des listes possibles pour la suite (obtenues récursivement).

Quand tu generes les positions une a une ca veut dire que tu incrementes a chaque fois
ici par exemple la longeur de la list est length('(n n n t...t))=23:
(0 1 2 3)->(0 1 2 4)->(0 1 2 5)->(0 1 2 6)->...(0 1 2 23)->(0 1 3 4)->(0 1 3 5)->...etc

et les cons devant chacune des listes possibles pour la suite (obtenues récursivement).

Je n'ai pas compris.

sm1z2000

[Garulfo]

Merci trapD. C'est assez constructif ce que me dis la.
pour ce qui est du reste. Je voulais remettre les choses a leur place pour que ca ne derape pas trop.[...]

Oh mais ça ne dérape pas. On ne te traduira rien en Scheme. Désolé de paraître sans pitié: nous t'aidons mais ne faisons rien à ta place.

Tu dis avoir une solution sur papier, donnes la nous. Nous n'avons rien vu. Qu'est-ce qui te dit qu'elle est correcte ? Va voir les autres sujet tu verras que c'est quasiment un problème d'algorithme et non un problème de traduction. Le précédent algo ne venait pas de toi — du moins c'est ce que tu nous as dit.

Si l'algo est correct, dis nous où est le problème et nous t'aiderons à le traduire en Scheme. L'algo impératif de ton premier post pourrait être une solution. Il faudrait cependant que tu le comprennes — ça veut dire éclaircir les points mal spécifiés — et que tu nous dises quels sont les problèmes que tu rencontres.

De ma part, tu n'auras jamais de solution directe.

[sm1z2000]

Bof. Ma solution est correct puisque je te le dis. Je ne peux t'ecrire le code puisque c'est confidentiel.
Par contre mon raisonnement etait de creer deux procedure: une pour incrementer la liste qui donne la position des nil. ensuite a partir de cette liste je cree ma liste a l'aide d'une autre procedure:
(n t n n t t t)<-(0 2 3)
ainsi de suite, donc j'incremente puis je recree la liste. c'est pour ca que je dis que c'est une usine a gaz.

Apres ma question, c'etait si l'algo est bon. Pour ta gouverne je l'ai trouve sur le forum algo: http://www.developpez.net/forums/d29...rangement-anp/

Alors, j'ai demander gentillement sur le forum scheme si'il peut etre implementer en scheme. J'ai eu quelques reponses constructives. Par contre toi Garulfo si tu lis tes postes ici ou ailleurs, on dirait un prof de maternel...Je comprend que des fois tu n'as plus de patience.
C'est exasperant...
Fin de la discussion pour moi

[Nicolas_75]

Bonjour,

Tombant sur ce fil car travaillant sur un problème similaire en... Prolog, je tente de le résoudre en Scheme à titre d'exercice.

Le coeur du code tient en quelques lignes :

Code :

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

1
2
3
4
5
6
7
8
(define (enumere-combinaisons p m n)
  (if (= p 1)
      (map list (liste-des-entiers-dans-intervalle m n))
      (apply append (map 
                     (lambda (i) (map
                                  (lambda (tail) (cons i tail))
                                  (enumere-combinaisons (- p 1) (+ i 1) n)))
                     (liste-des-entiers-dans-intervalle m (+ (- n p) 1))))))

Une version largement commentée est proposée ci-dessous.

Je soumets ce code à la critique des personnes éventuellement intéressées, dans le but de progresser en Scheme.

Cordialement,

Nicolas

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
; 10 janvier 2011
; http://www.developpez.net/forums/d763158/autres-langages/langages-fonctionnels/scheme/enumeration-combinaisons-doublon/


; renvoie la liste des entiers successifs compris entre m et n (tous deux inclus), ordonnés par ordre croissant
; (récursion terminale)
; par exemple (liste-des-entiers-dans-intervalle 4 7) renvoie (4 5 6 7)
(define (liste-des-entiers-dans-intervalle m n)
  (if (> m n)
      '()
      (cons m (liste-des-entiers-dans-intervalle (+ m 1) n))))


; renvoie la liste de tous les p-uplets strictement ordonnés d'entiers pris dans |[m, n]|
; 1 =< p =< n-m+1
; par exemple  :
;   (enumere-combinaisons 1 4 9) --> ((4) (5) (6) (7) (8) (9))
;   (enumere-combinaisons 2 3 7) --> ((3 4) (3 5) (3 6) (3 7) (4 5) (4 6) (4 7) (5 6) (5 7) (6 7))
;   (enumere-combinaisons 3 1 5) -->  ((1 2 3) (1 2 4) (1 2 5) (1 3 4) (1 3 5) (1 4 5) (2 3 4) (2 3 5) (2 4 5) (3 4 5))
;   (length (enumere-combinaisons 10 3 20)) ; --> 43758 = C(n-m+1, p)
; on va choisir, dans la dernière ligne du code, le premier élément x du p-uplet, au sein de |[m, n-p+1]|
; puis on complète par tous les (p-1)-uplets strictement ordonnés d'entiers pris dans |[x+1, n]|
(define (enumere-combinaisons p m n)
  (if (= p 1)
      (map list (liste-des-entiers-dans-intervalle m n)) ; si p = 1, renvoie (m m+1 ... n-1 n)
      (apply append (map 
                     ; dans le cas p=2, m=3, n=7, ce map va renvoyer :
                     ; {   [ (3 4) (3 5) (3 6) (3 7) ]   [ (4 5) (4 6) (4 7) ]   [ (5 6) (5 7) ]   [ (6 7) ]   }
                     ; où les crochets et les accolades doivent être lus comme des parenthèses
                     (lambda (i) (map
                                  (lambda (tail) (cons i tail))
                                  (enumere-combinaisons (- p 1) (+ i 1) n)
                                  ; dans le cas p=2, m=3, n=7, ce "enumere-combinaisons" renvoie :
                                  ; pour i=3 : (4 5 6 7)
                                  ; pour i=4 : (5 6 7)
                                  ; pour i=5 : (6 7)
                                  ; pour i=6 : (7)
                                  ))
                     ; la fonction "lambda (i)" qui précède associe à i la liste des p-uplets débutant par i
                     ; par exemple, pour p=2, m=3, n=7, il s'agit de la fonction :
                     ;   3 |--> (3 4) (3 5) (3 6) (3 7)
                     ;   4 |--> (4 5) (4 6) (4 7)
                     ;   5 |--> (5 6) (5 7)
                     ;   6 |--> (6 7)
                     (liste-des-entiers-dans-intervalle m (+ (- n p) 1))
                     ; dans le cas p=2, m=3, n=7, la liste précédente est : (3 4 5 6)
                     ))))

(enumere-combinaisons 1 4 9) ; --> ((4) (5) (6) (7) (8) (9))
(enumere-combinaisons 2 3 7) ; --> ((3 4) (3 5) (3 6) (3 7) (4 5) (4 6) (4 7) (5 6) (5 7) (6 7))
(enumere-combinaisons 3 1 5) ; -->  ((1 2 3) (1 2 4) (1 2 5) (1 3 4) (1 3 5) (1 4 5) (2 3 4) (2 3 5) (2 4 5) (3 4 5))
(length (enumere-combinaisons 10 3 20)) ; --> 43758 = C(n-m+1, p)