Python Binary сравнить со значениями списка - PullRequest
Новая
       19

Python Binary сравнить со значениями списка

0 голосов
/ 05 октября 2018

Я пытаюсь выяснить, как это сделать в Python:

Распечатать все подмножества любого данного набора.

Например: [1,2]

Такответ от руки следующий: 

[]
[2]
[1]
[1,2]

Я понял, что общее число решений будет 2(exp)n, где n - количество элементов в списке.

Так, например, если список равен [1,3,4], то общее число подмножеств будет 2(exp)3 = 8.

Я также понял, что, если я получу двоичное представление битов из списка выше, появится следующее:

Так, например: [1,2]

00 : []
01 : [2]
10 : [1]
11 : [1,2]

Каждая позиция бита, содержащая 1, то есть позиция подмножества при индексации его к исходному набору [1,2].например, двоичный 01 = получить индекс в позиции 1 исходного набора [1,2], который будет [2].

двоичный 11, означает получить индексные позиции 0 и 1 из исходного набора [1,2], который дает ответиз [1,2] и т. д.

Как мне это закодировать, у меня такой грязный код, есть ли простой способ отобразить это?

1 Ответ

0 голосов
/ 05 октября 2018

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

def combinations(l):
    for i in range(1 << len(l)):
        c = []
        for b in range(len(l)):
            if i & (1 << (len(l) - b - 1)):
                c.append(l[b])
        yield c

или со списком: 

def combinations(l):
    return [[l[b] for b in range(len(l)) if i & (1 << (len(l) - b - 1))] for i in range(1 << len(l))]

, чтобы: 

list(combinations([1, 2])))

возвращало: 

[[], [2], [1], [1, 2]]

и: 

list(combinations([1, 3, 4]))

вернется: 

[[], [4], [3], [3, 4], [1], [1, 4], [1, 3], [1, 3, 4]]
...