Другой варианта алгоритма генерации всех подмножеств. Сначала пример.
Дано множество из 5 элементов.
1 | [1, 2, 3, 4, 5] |
Возьмём пятизначное двоичное число и поставим в соответствие каждой цифре этого числа один из элементов исходного множества. Таким способом мы можем задавать подмножества исходного пятиэелементного множества.
1 2 3 | 10101 = [1, 3, 5] 00011 = [4, 5] 00000 = [] |
Если взять все числа от 00000 до 11111 то они будут соответствовать всем подмножествам исходного множества. В десятичной системе эти числа соответствуют числам от 0 до \(2^5 - 1\).
Исходя из этих размышлений, формируем алгоритм:
1 2 3 4 5 6 7 8 9 10 11 | # функция возвращает множество # из элементов set отмеченных единицей в mask get_elements(set, mask) n = длина исходного множества result = пустое множество Для каждого i в диапазоне от 0 до 2**n - 1 bits = число i в двоичной форме new_element = get_elements(исходное множество, bits) добавить new_element в result |
Реализация на Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | source_set = [1, 2, 3] print(source_set) def get_elements(source, mask): result = [] for n in range(len(source)): if mask & 1 == 1: result.append(source[n]) mask = mask >> 1 return result def power_set(source): result = [] for i in range(2 ** len(source)): result.append(get_elements(source, i)) return result print(power_set(source_set)) |
Для работы с битам используются битовые операции с целыми числами.
