Usando el conjunto de bits de Python para encontrar todas las combinaciones de un conjunto de tamaño k.

Estoy intentando acelerar mi propia solución de programación dinámica para el Problema del Viajante de Comercio. Mi solución original utiliza memorización con un diccionario con frozenset() de Python como parte de la clave. Sin embargo, creo que esta implementación puede mejorarse utilizando bitsets (o en mi implementación, un entero regular de tamaño 2^n bits donde n es el número de vértices en nuestro grafo y el i-ésimo bit representa si el vértice i está incluido en el conjunto).

Dado un bitset, ¿cómo puedo generar todos los conjuntos de tamaño k?

Por ejemplo: conjunto = 11011, k = 3
Debemos devolver:
11010
11001
10011
01011

(4 elegir 3) = 4

¿Algo como combinations(element_set, k) de itertools pero para bitsets?

davy.ai

May 30, 2023 at 10:43 pm

Desafortunadamente, no hay una función incorporada en Python para generar todos los conjuntos de un tamaño dado k para un bitset. Sin embargo, una forma de hacerlo es utilizando operaciones bit a bit para manipular el bitset. Aquí hay un algoritmo que puede generar todos los conjuntos de tamaño k para un bitset dado:

Inicialice una variable resultado como una lista vacía.
Itere de 0 a 2^n – 1 (donde n es el número de vértices), inclusive.
En cada iteración, verifique el número de bits establecidos en la representación binaria de la iteración actual. Si el número de bits establecidos es igual a k, agregue la iteración actual a resultado.
Devuelva resultado.

Aquí está el código para el algoritmo:

def generate_sets(bitset, k):
    n = len(bin(bitset)) - 2
    resultado = []
    for i in range(2**n):
        if bin(i).count('1') == k:
            resultado.append(i)
    return resultado

Usando esta función, puedes generar todos los conjuntos de tamaño k para un bitset dado. Por ejemplo, para generar todos los conjuntos de tamaño 3 para el bitset 11011, debes hacer:

>>> generate_sets(0b11011, 3)
[11, 19, 22, 26]

Ten en cuenta que los conjuntos devueltos están en representación decimal. Para convertirlos nuevamente a binario, puedes usar la función bin():

>>> bin(11)
'0b1011'
>>> bin(19)
'0b10011'
>>> bin(22)
'0b10110'
>>> bin(26)
'0b11010'

Answer

davy.ai

May 30, 2023 at 10:43 pm
Desafortunadamente, no hay una función incorporada en Python para generar todos los conjuntos de un tamaño dado k para un bitset. Sin embargo, una forma de hacerlo es utilizando operaciones bit a bit para manipular el bitset. Aquí hay un algoritmo que puede generar todos los conjuntos de tamaño k para un bitset dado:
1. Inicialice una variable resultado como una lista vacía.
2. Itere de 0 a 2^n – 1 (donde n es el número de vértices), inclusive.
3. En cada iteración, verifique el número de bits establecidos en la representación binaria de la iteración actual. Si el número de bits establecidos es igual a k, agregue la iteración actual a resultado.
4. Devuelva resultado.
Aquí está el código para el algoritmo:
```
def generate_sets(bitset, k):
    n = len(bin(bitset)) - 2
    resultado = []
    for i in range(2**n):
        if bin(i).count('1') == k:
            resultado.append(i)
    return resultado
```
Usando esta función, puedes generar todos los conjuntos de tamaño k para un bitset dado. Por ejemplo, para generar todos los conjuntos de tamaño 3 para el bitset 11011, debes hacer:
```
>>> generate_sets(0b11011, 3)
[11, 19, 22, 26]
```
Ten en cuenta que los conjuntos devueltos están en representación decimal. Para convertirlos nuevamente a binario, puedes usar la función bin():
```
>>> bin(11)
'0b1011'
>>> bin(19)
'0b10011'
>>> bin(22)
'0b10110'
>>> bin(26)
'0b11010'
```

Comments are closed.

es.davy.ai

¿Tienes una pregunta?

Usando el conjunto de bits de Python para encontrar todas las combinaciones de un conjunto de tamaño k.

Answer

davy.ai