Hay muchos métodos rápidos en el desbordamiento de pila que generan toda la combinación de conjuntos de bits de tamaño k.
Ex:
combos(4,3) = {1110,1101,1011,0111}Sin embargo, ¿existe una forma rápida de calcular todos los combos para los tamaños 1 a n?
Ex:
allCombos(4) = { 1: {0001, 0010, 0100, 1000} 2: {0011, 0101, 1001, 0110, 1010, 1100} 3: {0111, 1011, 1101, 1110} 4: {1111} } Por supuesto, solo puedo llamar a combos(4, i) for i del 1 al 4. Sin embargo, quiero aprovechar el siguiente hecho:
Para cada conjunto de bits X en combos(4, i) , podemos configurar exactamente un bit del conjunto de bits X de 0 a 1.
Por ejemplo, 0011 está en combos(4,2) que genera {1011, 0111} en combos(4,3) ya que el 1er y 2do bit más significativo son 0's.
EDITAR: aquí está mi forma actual de lograr esto:
def combos(set_, k): return map(sum, itertools.combinations(set_, k)) # take combos of 1, 2, 4, 8 ... and the sums to get bitset back def allCombos(n): ret = {} bitset = set([2**i for i in range(n)]) # generates 1, 2, 4, 8 ... for k in range(1,n+1): ret[k] = combos(bitset, k) return kComo señala Frank Yellin, su "atajo" probablemente no sea realmente tan útil. La única forma en que creo que podría mejorar ligeramente el tiempo de este cálculo es reconocer que si volteamos cada bit en cada conjunto de bits en combos(n,i) obtenemos los conjuntos de bits combos(n,ni) . Podría crear una función muy simple y rápida que tomaría un conjunto de conjuntos de bits y devolvería un conjunto con el conjunto de bits opuesto para cada uno. Por ejemplo, si se le da combos(4,1) que es {0001,0010,0100,1000} , generaría {1110,1101,1011,0111} que es combos(4,3) . Esto reduciría su tiempo de ejecución aproximadamente a la mitad.