Генерация всех возможных значений для переменных с рекурсией - PullRequest
Новая
       19

Генерация всех возможных значений для переменных с рекурсией

0 голосов
/ 07 февраля 2019

Я создаю таблицу истинности с Python, и я сделал это итеративно без каких-либо хлопот, но я пытаюсь выяснить, как сгенерировать все возможные значения True и False для любого числа переменных рекурсивно.

Начиная со списка, подобного: [[True], [False]]

Мне нужно создать список, подобный: 

[[True, True, True], 
 [True, True, False], 
 [True, False, True], 
 [True, False, False], 
 [False, True, True], 
 [False, True, False], 
 [False, False, True], 
 [False, False, False]]

, где каждый список представляет собой строку в таблице истинности.

Исходя из этого, вы проходите и оцениваете каждую строку, добавляя значение true или false в конец каждого списка на основе оцениваемого выражения.

Я уже решил проблему итеративно, но делать это рекурсивно не имеет никакого смысла для меня.Я всегда думал о рекурсии как о том, что она начинается с большого и становится маленьким (сокращается до базового варианта).Как в слиянии.Не наоборот.

Я не могу использовать ничего похожего на itertools.

Подсказка в назначении: «Советы: Вы можете использовать следующий рекурсивный алгоритм для создания всех комбинаций переменных для правды.таблица:

  • Базовый случай: для одной переменной список всех комбинаций: [[True], [False]]
  • Рекурсивный регистр: каждый элемент в списке (которыйсам по себе является списком), заменяется двумя списками, один с добавлением True, а другой с добавлением False. "

Алгоритм не имеет смысла для меня.

1 Ответ

0 голосов
/ 07 февраля 2019

Следующая рекурсивная реализация будет работать.Обратите внимание, что у вас может быть еще более простой базовый случай: 

def bool_combs(n):
    if not n:
        return [[]]
    result = []
    for comb in bool_combs(n-1):
        result.append(comb + [True])
        result.append(comb + [False])
    return result

>>> bool_combs(1)
[[True], [False]]
>>> bool_combs(2)
[[True, True], [True, False], [False, True], [False, False]]
>>> bool_combs(3)
[[True, True, True], [True, True, False], [True, False, True], [True, False, False], [False, True, True], [False, True, False], [False, False, True], [False, False, False]]
...