Как создать все перестановки списка кортежей в зависимости от порядка следования одного логического поля в Python

Question

Допустим, у меня есть входные данные в виде списка кортежей, таких как:

[('a', True),
 ('b', False),
 ('c', True),
 ('d', False)] 

Каждый кортеж с True в качестве второго параметра считается необязательным.

• суммакортежей в списке произвольно
• значение первого значения произвольно и должно быть сохранено

Теперь я хочу переставить эту структуру следующим образом:

• выводом должен быть список списков кортежей
• каждый список кортежей уникален
• списки различаются на необязательных кортежах, которые либо есть, либо нет
• кортежи, которые False не меняются (исчезают)
• порядок кортежей внутри списков не меняется
• порядок кортежей не изменяется
• спискикортежей может быть в любом порядке

Выходные данные приведенного выше примера должны выглядеть следующим образом:

[[('a', True),
  ('b', False),
  ('c', True),
  ('d', False)],

 [('b', False),
  ('c', True),
  ('d', False)],

 [('a', True),
  ('b', False),
  ('d', False)],

 [('b', False),
  ('d', False)]]

Есть мысли, как решить эту проблему элегантным способом?Я попытался с рекурсией, но я не мог осуществить это.

Answer 1

Вы можете сделать выбор, сделав копию списка ранее сделанных выборов и добавив новое значение к копии, а затем объединяя его со списком сделанных выборов.

Извините за это ужасное объяснение, но сейчас я не могу придумать ничего лучшего.Не стесняйтесь редактировать, если вы можете придумать что-нибудь лучше.В противном случае, я надеюсь, что приведенные ниже диаграмма и код помогут лучше объяснить мое решение.

                                        []
                    -------------------------------------------
                   []                                        [0]
       ----------------------------                ---------------------------
       []                       [1]                [0]                  [0, 1]
       ...                      ...                ...                  ...

Основная идея состоит в том, чтобы перебрать любой элемент, клонировать все частичные решения и добавить элемент в клонированные решения.

def choose(arr):
    res = [[]]

    for t in arr:
        if t[1]:
            # make a copy of all found solutions
            clone = [list(c) for c in res]

            # append the new value to the original solutions
            for l in res:
                l.append(t)

            # merge solution-list with the list of copies
            res += clone
        else:
            # non-optional element => just add the element to all solutions
            for l in res:
                l.append(t)

    return res

Вывод:

print('\n'.join(str(l) for l in choose([('a', True), ('b', False), ('c', True), ('d', False)])

[('a', True), ('b', False), ('c', True), ('d', False)]
[(' b ', False), (' c ', True), (' d ', False)]
[(' a ', True), (' b ',False), ('d', False)]
[('b', False), ('d', False)]

Answer 2

На самом деле есть хорошее рекурсивное решение, о котором я только что подумал:

def choices(a):
    if not a:
        yield []
        return
    head, *tail = a
    if head[1]:
        yield from choices(tail)
    for tail_choice in choices(tail):
        yield [head] + tail_choice

Это создает ленивый генератор для всех списков кортежей:

>>> list(choices(a))
[[('b', False), ('d', False)],
 [('b', False), ('c', True), ('d', False)],
 [('a', True), ('b', False), ('d', False)],
 [('a', True), ('b', False), ('c', True), ('d', False)]]

Answer 3

Я не уверен, что есть особенно элегантный способ. Концептуально вам необходимо вычислить набор мощности необязательных элементов, но объединить его с необязательными элементами таким образом, чтобы удовлетворить ваши требования. Вот один из способов:

import itertools
a = [('a', True), ('b', False), ('c', True), ('d', False)]
optional_count = sum(optional for x, optional in a)
for include in itertools.product([True, False], repeat=optional_count):
    include_iter = iter(include)
    print([
        (x, optional)
        for x, optional in a
        if not optional or next(include_iter)
    ])

печать

[('a', True), ('b', False), ('c', True), ('d', False)]
[('a', True), ('b', False), ('d', False)]
[('b', False), ('c', True), ('d', False)]
[('b', False), ('d', False)]

Цикл повторяется по всем кортежам, указывая, включать ли дополнительные элементы:

True, True
True, False
False, True
False, False

Понимание списка в операторе печати включает в себя все необязательные элементы, а для необязательных просматривает следующий доступный элемент из include.