2

私は問題があります。Racketでxブール値の可能なすべての組み合わせを取得するにはどうすればよいですか?(低言語レベルで)

私はそのようなものが必要です:

x = 1の場合(リスト(リストfalse)(リストtrue))

x = 2の場合(list(list false false)(list false true)(list true false)(list true true))

x = 3の場合(list(list false false false)(list false false true)(list false true false)(list false true true)(list true false false)(list true false true)(list true true false)(list true true true))

ラケットでこれを行う方法がわかりません。

ありがとうございます!

4

3 に答える 3

4

リストのすべての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

数値をブール値のリストに変換する1つの方法があります。すべての組み合わせを生成するには、説明したようにループで使用します。

  (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)は元の問題を返します。パワーセットを作成するには、次のようにします...

;; 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 に答える