Функция для возврата всех комбинаций n логических значений?

Question

Я пытаюсь реализовать функцию, которая принимает число n и возвращает список списков логических значений, который содержит все возможные комбинации из n логических значений. Выход, например, (make-bools 3) должно выглядеть как

[[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, чтобы составить список логических значений, и, наконец, объединить все эти списки в цепочку. Но это кажется мне довольно неуклюжим, и я полагаю, что должно быть более элегантное решение.

Answer 1

Я не знаю, считается ли это «мошенничеством» для использования существующей библиотеки вместо того, чтобы отвечать на алгоритмические детали вашего вопроса, но 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

Answer 2

Если вы все еще ищете рекурсивное решение с нуля (если только для изучения), вот то, которое реализует шаблон, который часто полезен для рекурсивного построения «путей» через древовидные структуры:

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

В этом случае «дерево» является воображаемым (серия истинных / ложных выборов), но применяются те же методы.

Answer 3

для также отлично работает

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