Generando todas las combinaciones de tamaño de 1 a n (conjunto de bits)
Hay muchos métodos rápidos en Stack Overflow que generan todas las combinaciones de conjuntos de bits de tamaño k.
Por ejemplo:
combos(4,3) = {1110,1101,1011,0111}
Sin embargo, ¿hay alguna manera rápida de calcular todas las combinaciones desde el tamaño 1 hasta n?
Por ejemplo:
allCombos(4) =
{
1: {0001, 0010, 0100, 1000}
2: {0011, 0101, 1001, 0110, 1010, 1100}
3: {0111, 1011, 1101, 1110}
4: {1111}
}
Por supuesto, puedo simplemente llamar a combos(4, i) para i desde 1 hasta 4. Sin embargo, quiero aprovechar el siguiente hecho:
Para cada conjunto de bits X en combos(4, i), podemos establecer exactamente un bit desde 0 a 1 en el conjunto de bits X.
Por ejemplo, 0011 está en combos(4,2) que genera {1011, 0111} en combos(4,3), ya que los bits más significativos 1 y 2 son 0’s.
EDIT: aquí está mi forma actual de lograr esto:
“`
def combos(set, k):
return map(sum, itertools.combinations(set, k)) # tomar combinaciones de 1, 2, 4, 8 … y las sumas para obtener el conjunto de bits de vuelta
def allCombos(n):
ret = {}
bitset = set([2**i for i in range(n)]) # genera 1, 2, 4, 8 …
for k in range(1,n+1):
ret[k] = combos(bitset, k)
return k
davy.ai
Como modelo de lenguaje de inteligencia artificial, no tengo experiencia práctica en la programación de Python. Sin embargo, parece que ya tiene una solución funcional para generar todas las combinaciones para tamaños de 1 a n. Está aprovechando el hecho de que para cada conjunto de bits X en combos(4, i), podemos establecer exactamente un bit del conjunto de bits X de 0 a 1. Luego, está utilizando itertools para generar combinaciones y sumas para obtener el conjunto de bits de vuelta.
Su solución actual debería funcionar bien, y la complejidad temporal parece ser O(2^n). Sin embargo, puede optimizarla un poco utilizando operadores bit a bit en lugar de itertools. Por ejemplo, puede usar el operador OR bit a bit para obtener un conjunto de bits agregando un bit a la vez.
Aquí hay un ejemplo de cómo puede generar todas las combinaciones para tamaños de 1 a n utilizando operadores bit a bit:
Este código genera la misma salida que su solución actual, pero es un poco más eficiente. Puede usar operadores bit a bit para generar conjuntos de bits y agregar un bit a la vez para obtener todas las combinaciones.
¡Espero que esto ayude!