Реализация алгоритма power set

Question

Ввод: [0, 1, 2]

Вывод: [[], [0], [1], [2], [0, 1], [1, 2], [0, 2], [0, 1, 2]] (Порядок вывода массива не имеет значения)

Псевдокод:

Алгоритм действия:

Код на Python:

def power_set(array):
    result = [[]]
    for element in array:
        new_list = result.copy()
        for subset in new_list:
            subset.append(element)
        result += new_list
    return result

print(power_set(range(3)))

Вывод: [[0, 1, 1, 2, 2, 2, 2], [0, 1, 1, 2, 2, 2, 2], [0, 1, 1, 2, 2, 2, 2], [0, 1, 1, 2, 2, 2, 2], [0, 1, 1, 2, 2, 2, 2], [0, 1, 1, 2, 2, 2, 2], [0, 1, 1, 2, 2, 2, 2], [0, 1, 1, 2, 2, 2, 2]]

Проблема заключается в том что элементы списка ссылаются на одно значение

Почему произошла ошибка и как это исправить?

P. s. Прошу без импортирования модулей и только с двумя циклами

Answer 1

    result = [[]] # <- список списков
    for element in array:
        new_list = result.copy() # <- "мелкая" копия

Проблема в том, что у вас список списков, а copy() копирует только верхний слой, а всё, что в остальных слоях, продолжает указывать на прежнее место. Можно починить так:

        new_list = [x.copy() for x in result] # <- копия глубиной 2 слоя

Answer 2

Проблема вашего кода в мелком копировании. Её можно избежать если уменьшить количество операций, которые меняют существующие массивы. Вместо subset.append(element) используйте subset + [element]. Результат обеих операций в чём-то одинаков, но вторая создаёт новый список, оставляя исходный без изменений:

def power_set(array):
    result = [[]]
    for element in array:
        result.extend([subset + [element] for subset in result])
    return result


print(power_set(range(3)))

БЛОГ НА HUSL

Реализация алгоритма power set

Ответы (2 шт):