我有一個問題。我如何在Racket中獲得所有可能的x布爾組合? (在低語言水平)獲得所有可能的x布爾組合(球拍,方案)
我需要類似的東西:
當x = 1 (名單 (清單作虛僞) (名單真))
當x = 2 (名單 (列表虛假) (列表假真) (列表真假) (列表真真))
對於X = 3 (列表 (名單假假假) (名單虛假真) (名單假真假) (清單作虛僞真真) (名單真虛假) (名單真假真) (名單真真假) (名單真真真))
等
我不知道如何做到這一點的球拍。
謝謝你!
我有一個問題。我如何在Racket中獲得所有可能的x布爾組合? (在低語言水平)獲得所有可能的x布爾組合(球拍,方案)
我需要類似的東西:
當x = 1 (名單 (清單作虛僞) (名單真))
當x = 2 (名單 (列表虛假) (列表假真) (列表真假) (列表真真))
對於X = 3 (列表 (名單假假假) (名單虛假真) (名單假真假) (清單作虛僞真真) (名單真虛假) (名單真假真) (名單真真假) (名單真真真))
等
我不知道如何做到這一點的球拍。
謝謝你!
這裏是一個數字轉換爲布爾值的列表的方法之一。 要生成所有組合,請按照您所描述的方式在循環中使用它。
(map (λ (x) (eqv? x #\1))
(string->list (number->string 12345 2)))
將12345替換爲任意數字。
工作太棒了!謝謝。 – pythonimus
你問所有正大小排列列表'(#t #f)
的(不組合!),以允許重複。爲適應球拍this答案:
(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))
你實際上在做的是爲一組尺寸x構建powerset。
powerset是所有可能子集的集合。例如,(list 1 2 3)的powerset是(list 1 2 3)(list 1 2)(list 1 3)(list 1)(list 2 3)(list 2)(list 3)empty) 。
(A組是本身和空集的一個子集是所有集合的子集。)
爲什麼你在做什麼介紹了冪是因爲一個元素可以是或不是在一個子集。因此,將(list 1 2 3)應用(list true true)將返回(list 1 2 3)並且(list false 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)))
數學說,這是2^n,並且所有你需要做的是將所有的數字從0到2^n的迭代 - 1,並將其轉換爲二進制 – hoaz