2

我有个问题。如何在 Racket 中获得所有可能的 x 布尔值组合？（在低语言水平上）

我需要这样的东西：

对于 x=1 (list (list false) (list true))

对于 x=2 (list (list false false) (list false true) (list true false) (list true true))

for x=3 (list (list false false) (list false false true) (list false true false) (list false true true) (list true false false) (list true false true) (list true false) (list真实真实真实））

等等

我不知道如何在 Racket 中做到这一点。

谢谢！

4

3 回答 3

4

您要求 list 的所有 n 大小排列（不是组合！），'(#t #f)允许重复。为球拍改编这个答案：

(define (permutations size elements)
  (if (zero? size)
      '(())
      (append-map (lambda (p)
                    (map (lambda (e)
                           (cons e p))
                         elements))
                  (permutations (sub1 size) elements))))

像这样使用它：

(permutations 3 '(#t #f))

=> '((#t #t #t) (#f #t #t) (#t #f #t) (#f #f #t)
     (#t #t #f) (#f #t #f) (#t #f #f) (#f #f #f))
于 2012-12-20T19:09:59.493 回答
2

这是将数字转换为布尔值列表的一种方法。要生成所有组合，请按照您的描述在循环中使用它。

  (map (λ (x) (eqv? x #\1)) 
       (string->list (number->string 12345 2)))

将 12345 替换为任意数字。

于 2012-12-20T19:18:29.533 回答
1

您实际上在做的是为一组大小 x 构建幂集。

幂集是所有可能子集的集合。例如， (list 1 2 3) 的幂集是 (list (list 1 2 3) (list 1 2) (list 1 3) (list 1) (list 2 3) (list 2) (list 3) empty) .

（一个集合是它自己的一个子集，而空集是所有集合的一个子集。）

为什么您正在做的事情描述了幂集是因为一个元素可以在或不在一个子集中。所以 apply (list true true true) to (list 1 2 3) 将返回 (list 1 2 3) 并且 (list false true true) 将返回 (list 2 3)。

这是我解决您问题的代码。

(define baselist (list  (list true) (list false)))
;; List1 List2 -> List of Lists
;; Where List1 is any list of lists, and list2 is a list of lists of size 2
;; and all of the lists within list 2 has one element
(define (list-combination list-n list-two)
  (cond [(empty? list-n) empty]
        [else (cons (append (first list-n) (first list-two))
                    (cons (append (first list-n) (second list-two))
                          (list-combination (rest list-n) list-two)))]))
;; tflist Number -> List of Boolean Lists
;; creates baselistn
(define (tflist n)
  (cond [(= 1 n) baselist]
        [else (list-combination (tlist (sub1 n)) baselist)]))

所以 (tflist 3) 会返回你原来的问题。现在要制作一个powerset，您可以执行以下操作...

;; subset List1 ListofBooleans -> List
;; Determines which elements of a set to create a subset of
;; List1 and LoB are of the same length
(define (subset set t-f-list)
  (cond [(empty? t-f-list) empty]
        [(first t-f-list) (cons (first set) (subset (rest set) (rest t-f-list)))]
        [else (subset (rest set) (rest t-f-list))]))
;;powerset set -> Powerset
;; produces a  powerset of a set
(define (powerset set)
  (local ((define upperbound (expt 2 (length set)))
          (define tflist (tlist (length set)))
          (define (powerset set n)
            (cond [(= n upperbound) empty]
                  [else (cons (subset set (list-ref tflist n)) (powerset set (add1 n)))])))
    (powerset set 0)))
于 2012-12-27T17:45:02.267 回答