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) |
Partager