clojure:编写一个clojure函数，该功能返回了所有长度n的所有2^n位字符串的列表

Question

我想编写一个称为（nbits n）的clojure函数，该函数返回了所有长度n的2^n位字符串的列表。

我的预期输出是：

user=> (nbits -2)
()
user=> (nbits 0)
()
user=> (nbits 1)
((0) (1))
user=> (nbits 2)
((0 0) (0 1) (1 0) (1 1))
user=> (nbits 3)
((0 0 0) (0 0 1) (0 1 0) (0 1 1) (1 0 0) (1 0 1) (1 1 0) (1 1 1))

这是我的尝试：

(defn add0 [seq] 
  (cond (empty? seq) 'nil
        (and (seq? seq) (> (count seq) 0)) 
          (cons (cons '0 (first seq)) (add0 (rest seq)))))
(defn add1 [seq]
  (cond (empty? seq) 'nil
        (and (seq? seq) (> (count seq) 0)) 
          (cons (cons '1 (first seq)) (add1 (rest seq)))))
(defn nbits [n]
  (cond (number? n) 
          (cond (< n 1) '()
                (= n 1) '((0) (1))
                (> n 1) 
                  (list (add0 (nbits (- n 1))) (add1 (nbits (- n 1))))) 
        :else 'nil))

但是输出不正确。我哪里做错了？我不知道如何修复它。

Answer 1

您也可以使用Math.binatorics库（懒惰和迭代）进行此操作：

user=> (defn nbits [n] 
         (if (pos? n) 
           (clojure.math.combinatorics/selections [0 1] n) 
           '()))
#'user/nbits
user=> (nbits 0)
()
user=> (nbits 1)
((0) (1))
user=> (nbits 2)
((0 0) (0 1) (1 0) (1 1))
user=> (nbits 3)
((0 0 0) (0 0 1) (0 1 0) (0 1 1) (1 0 0) (1 0 1) (1 1 0) (1 1 1))

此版本的优点是利用迭代来避免吹堆（我在计算机上使用原始版本的n = 14）。

Answer 2

您问题的简短答案是用nbits中的concat替换list。您的add0和add1都返回"位"列表的列表，因此创建这两个列表的列表添加了一个太多级别的列表嵌套。您想代替add0和add1的结果。

Answer 3

另一个要看的是迭代数字，然后将每个数字转换为序列而不是重新实现添加。

(defn nbits [n] 
  (for [m (range (Math/pow 2 n))]
    (map #(if (bit-test m %) 1 0) (range (dec n) -1 -1))))