Generate the combinations of K distinct objects chosen from the N elements of a list

	;; P26 (**) Generate the combinations of K distinct objects chosen from the N elements of a list
	;; In how many ways can a committee of 3 be chosen from a group of 12 people? We all know that there are C(12,3) = 220 possibilities (C(N,K) denotes the well-known binomial coefficients). For pure mathematicians, this result may be great. But we want to really generate all the possibilities in a list.
	;; Example:
	;; * (combination 3 '(a b c d e f))
	;; ((A B C) (A B D) (A B E) ... )
	#lang racket
	(provide (all-defined-out))
	(require "p17.ss")
	(define (combination n lst)
	(let ((num (- n 1)))
	(let loop ((lst lst) (acc '()))
	(if (or (> num (length lst)) (< n 2))
	acc
	(let ((ls0 (split num lst))
	(ls1 (split-after num lst)))
	(loop (cdr lst)
	`(,@acc ,@(combination-aux ls0 ls1))))))))
	(define (combination-aux new old)
	(let loop ((lst old) (acc '()))
	(if (null? lst)
	acc
	(loop (cdr lst)
	`(,@acc (,@new ,(car lst)))))))

view raw p26.ss hosted with ❤ by GitHub