Функция для возврата всех комбинаций 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^п) - 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), что должно привести к пустым спискам. –

Спасибо, я тоже думал о рекурсии, но не так. Я попробую этот подход. –

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

Большое спасибо! Обман абсолютно разрешен - хороший ответ, спасибо. –

Cheers. Есть одно предостережение: имейте в виду, что это решение работает только для [true false], а не [false true] в вызове функции «cartesian-product» ... Я только что посмотрел на источник для «декартового продукта» и из-за того, как он проверяет элемент на каждой итерации, он будет терпеть неудачу, если в последовательности будет значение false. Тем не менее, он работает для комбинаций всего остального, поэтому я не буду его стучать! – Scott

Спасибо за подсказку! –

для прекрасно работает

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

источник

2012-01-08 20:29:25

Это работает только в том случае, если вы знаете во время компиляции, сколько вам нужно. Вы не можете превратить это решение в функцию n. – amalloy

Да, я должен был прочитать вопрос с большей осторожностью –

Если вы все еще ищете 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

Да, действительно приятно (хотя мне потребовалось некоторое время, чтобы получить его). Благодарю. Здесь действительно можно многому научиться. –

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

ответ

Смежные вопросы