Subconjuntos con máscara de bits
La misión
Problema
Dada una lista de elementos distintos, devuelve todos sus subconjuntos. Ordena los subconjuntos contando: lee un subconjunto como un número binario en el que el bit i vale 1 cuando items[i] está incluido, y lista los subconjuntos desde el número 0 hasta el mayor. Dentro de cada subconjunto, conserva los elementos en su orden original. La lista tiene como máximo 15 elementos, y la lista vacía también tiene un subconjunto.
Ejemplos
Input: items = ["a", "b"]
Output: [[], ['a'], ['b'], ['a', 'b']]
Por qué: los números 0, 1, 2 y 3 en binario son 00, 01, 10 y 11
Input: items = [1, 2, 3]
Output: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
Por qué: items[2] aparece a partir del número 4, cuando se enciende el bit 2
Input: items = []
Output: [[]]
Por qué: caso límite: el conjunto vacío es el único subconjunto
Pistas
0 / 3
Cada elemento está dentro o fuera de un subconjunto, así que n elementos dan 2 elevado a n subconjuntos. ¿Qué otra cosa viene exactamente en esa cantidad de variantes?
Los enteros de 0 a 2 elevado a n menos 1 son todos los patrones posibles de n bits, y cada patrón puede describir un subconjunto.
Cuenta con un número mask desde 0 hasta 2 elevado a n menos 1. Para cada mask, reúne items[i] para cada i cuyo bit esté encendido, algo que puedes comprobar con un desplazamiento y un AND.
- Tiempo objetivo
- O(n · 2ⁿ)
- Espacio objetivo
- O(n · 2ⁿ)
Restricciones
- items are distinct
- 0 ≤ items.length ≤ 15
Solución
Un subconjunto de n elementos es una elección de sí o no por elemento, que es exactamente un número de n bits, así que contar de 0 a 2 elevado a n menos 1 recorre cada subconjunto una vez. Para cada número, el bit i se comprueba con mask >> i & 1, y los elementos cuyos bits están encendidos forman el subconjunto. Como el bit i siempre significa items[i], los miembros conservan su orden original. El tiempo es O(n por 2 elevado a n) y el espacio es el mismo por la salida.
def all_subsets(items):
n, subsets = len(items), []
for mask in range(1 << n): # every n-bit pattern is one subset
subsets.append([items[i] for i in range(n) if mask >> i & 1])
return subsets
print(all_subsets(["a", "b"])) # -> [[], ['a'], ['b'], ['a', 'b']]
print(all_subsets([1, 2, 3])) # -> [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
print(all_subsets([])) # -> [[]]¿Lo que te frena es la idea y no el código? La máscara de bits como conjunto lo explica.