如何獲得所有布爾值組合的列表？

Question

我想創建下面的函數，即所有梳子，其行爲與示例中的相同。爲什麼我的代碼不工作？你能解決它或給你自己的代碼？

(all-combs 0) 
>> '(()) 
(all-combs 1) 
>> '((0) (1)) 
(all-combs 2) 
>> '((0 0) (0 1) (1 0) (1 1)) 

(define (all-combs1 n) 
    (cond 
    [(equal? n 0) '(())] 
    [else 
    (append (map (lambda (x) (cons 0 x)) (all-combs1 (- 1 n))) 
    (map (lambda (x) (cons 1 x)) (all-combs1 (- 1 n)))) 
])) 

Answer 1

你非常接近。問題是你正在切換被減數和不再。 (- 1 2)不會變成1小於2而是-1。 (- 1 n)顯然不是參數的預期順序。

(define (all-combs n) 
    (if (zero? n) 
     '(()) 
     (let ([rest-of-combs (all-combs1 (- n 1))]) 
     (append (map (lambda (x) (cons 0 x)) rest-of-combs) 
       (map (lambda (x) (cons 1 x)) rest-of-combs))))) 

我已經做了一些額外的undeeded的變化，以及：

既然你對同一數據集做了兩次all-combs1這將大數非常不佳。通過使用let綁定並使用結果兩次來代替它很容易被忽略。

由於您的案例分析只有一個謂詞，一個後果和一個替代方案，所以使用if而不是cond來閱讀它可能會更容易。

equal?可以在任何數據類型上使用，對於看起來相同的所有內容，將會是#t。對於數字，僅使用數字值即可使用eqv?或=。當看到=像(= a b)一樣，你知道a和b應該是數字，而(eqv? a b)可以是數字，字符或符號。使用更具體的過程可能會更快，但報告不需要實施。 (zero? n)與(= n 0)的做法相同，但不需要指定第二個操作數，並且其內涵略微更清晰。

Answer 2

獲取某物的所有組合的方法通常與cartesian-product適用於n可能值列表的副本。

是利用apply與make-list到功能應用到價值ň重複的方式：

#lang racket 

;; for combinations of booleans 
(define (all-boolean-combinations n) 
    (apply cartesian-product (make-list n '(#t #f)))) 

;; for combinations of integers 0 through 2 
(define (all-0..2-combinations n) 
    (apply cartesian-product (make-list n '(0 1 2)))) 

;; for combinations of any list of possible values 
(define (all-combinations n possible-values) 
    (apply cartesian-product (make-list n possible-values))) 

你用0和1的例子是這樣的：

> (all-combinations 0 '(0 1)) 
'(()) 
> (all-combinations 1 '(0 1)) 
'((0) (1)) 
> (all-combinations 2 '(0 1)) 
'((0 0) (0 1) (1 0) (1 1)) 
> (all-combinations 3 '(0 1)) 
'((0 0 0) (0 0 1) (0 1 0) (0 1 1) (1 0 0) (1 0 1) (1 1 0) (1 1 1)) 
> (all-combinations 4 '(0 1)) 
'((0 0 0 0) (0 0 0 1) (0 0 1 0) (0 0 1 1) (0 1 0 0) (0 1 0 1) (0 1 1 0) (0 1 1 1) 
    (1 0 0 0) (1 0 0 1) (1 0 1 0) (1 0 1 1) (1 1 0 0) (1 1 0 1) (1 1 1 0) (1 1 1 1))