函數返回n個布爾值的所有組合？

我想實現一個函數，它需要一個數字n並返回包含n個布爾值的所有可能組合的布爾表列表。例如， (make-bools 3)應該像函數返回n個布爾值的所有組合？

[[false false false] 
[false false true ] 
[false true false] 
[false true true ] 
[true false false] 
[true false true ] 
[true true false] 
[true true true ]]

我想從0轉換號碼（2^N） - 1的二進制格式，並使用bit-test使布爾值列表，最後鏈接所有這些名單。但是，這對我來說似乎很笨拙，我想應該有一個更優雅的解決方案。

來源

2012-01-08 A Friedrich

嘗試一種遞歸方法：假設你知道如何做一個（make-bools 2），你將如何創建（make-bools 3）：只需在每個元素前加上false和true。將此概括爲（make-bools n）表示爲（make-bools n-1）並處理（make-bools 0），這應該導致列表爲空。 – 2012-01-08 12:59:12

謝謝，我也想到了遞歸，但方式不對。我會嘗試這種方法。 – 2012-01-08 13:21:45

我不知道它是否被認爲是使用現有庫的「作弊」，而不是響應你的問題的算法細節，但Clojure-contrib有一組常用的組合函數可用於計算排列：

(require '[clojure.contrib.combinatorics :as comb]) 

(defn make-bools [n] 
    (apply comb/cartesian-product (repeat n [true false])))

http://richhickey.github.com/clojure-contrib/combinatorics-api.html

來源

2012-01-08 13:23:33 Scott

非常感謝！作弊是絕對允許的 - 很好的答案，謝謝。 – 2012-01-08 13:40:47

乾杯。有一個警告：請注意，這個解決方案只適用於[true false]而不是[false true]在調用'cartesian-product'的函數中......我剛剛查看了'cartesian-product'的源代碼，並且由於它在每次迭代中測試元素的方式，如果在序列中第一個虛假值，它將失敗。不過，它適用於其他任何組合，所以我不會敲它！ – Scott 2012-01-08 13:53:38

感謝您的提示！ – 2012-01-08 15:05:13

的也能正常工作

(let [bools [false true]] 
    (for [x bools y bools z bools] [x y z]))

來源

2012-01-08 20:29:25

這隻有在編譯時知道你需要多少個布爾值時纔有效。你不能真正把這個解決方案變成n的函數。 – amalloy 2012-01-08 20:55:06

是的，我應該更仔細地閱讀這個問題 – 2012-01-09 01:00:41

如果你還在尋找一個recursiv即，從劃傷溶液（如果只研究），這裏有一個實現該常常用於通過樹結構遞歸構建的「路徑」有用的模式：

(let [bools [true false]] 
    (fn combs [n] 
    (if (zero? n) 
     [[]] 
     (for [smaller (combs (dec n)) 
      b bools] 
     (cons b smaller)))))

在這種情況下，「樹」是虛數（一系列的真假選擇），但同樣的技巧也適用。

來源

2012-01-08 20:58:52 amalloy

這是一個非常好的模式，值得記住。我有一種感覺，我會一次又一次地回到這個。 – Scott 2012-01-08 21:26:04

是的，確實不錯（雖然我花了一段時間纔得到它）。謝謝。這裏真的可以學到很多東西。 – 2012-01-08 23:10:46

函數返回n個布爾值的所有組合？

回答

相關問題