¿Cuál es la mejor manera de calcular subconjuntos de un conjunto dado de números que no son necesariamente únicos?

Answer 1

Esta es una pregunta bastante común. Más a menudo, los problemas en los que usted siente la respuesta se pueden encontrar después de forzar brutalmente a través de todos los subconjuntos, tienen soluciones más inteligentes y más eficientes usando Programación dinámica.

Echa un vistazo a: El problema de la mochila.

De todos modos, si necesita enumerar todos los subconjuntos de un conjunto dado, la complejidad es O (2 ^ n), que es exponencial en wrt n y es muy difícil de calcular para n> 20.

Para valores razonablemente pequeños de n, podemos usar el concepto de BITMASKING aquí.

En primer lugar, afirmamos que :

“Si enumeramos todos los números binarios de 0 a 2 ^ (n-1), obtenemos TODAS las combinaciones posibles de selección n elementos “

Permite verificar para n = 3

000: Ninguno de los valores en el conjunto elegido.
001: 1º elegido, 2º y 3º artículos excluidos
010: 2 ° artículos elegidos, 1 ° y 3 ° omitidos
011: 1er y 2do ítem elegido, el 3er omitido.
…
111: Los 3 artículos elegidos.

De esta manera, hemos enumerado las 2 ^ n formas de obtener todos los subconjuntos de un conjunto de n números. Único o no, no importa porque el índice de cada elemento con el que estamos tratando es único.

Supongo que desea realizar ciertas operaciones en los elementos seleccionados. En ese caso, simplemente mantenga una matriz de tamaño n de los elementos del conjunto.

Ahora para la parte de cómputo, la idea central es la fuerza bruta a través de cada bit de cada número del 0-2 ^ n-1 y verificar los bits establecidos de cada número.

Algoritmo:
1. Ejecute un bucle para ‘i’ para todos los números del 0 al 2 ^ (n-1 ).
2. Cuando esté dentro de este bucle, ejecute un bucle para ‘j’ de 0 a n-1 inclusive
3. Dentro de este bucle, compruebe si el bit ‘j’th está SET (igual a 1) para el número’ i ‘.
4. Si es así, entonces incluimos este elemento en nuestro ‘i’th subconjunto
5. Hecho.

Estaba muy confundido cuando aprendí esto la primera vez, así que permítame demostrarlo con un pequeño ejemplo: digamos para i = 3, la representación binaria es 011. Cuando ejecutamos el bucle interno de 1 a n para i, que actualmente es 3, Esto es lo que estamos haciendo en realidad .

1. ¿Se ha establecido el bit más correcto (LSB)? Sí. Así que incluyelo. [01x]
2. ¿Está ajustado el bit medio? Sí. Así que incluyelo. [0x0]
3. ¿Está configurado el último bit (MSB)? No. Así que déjalo fuera. [x11]

Lo que esencialmente estamos haciendo es que para cada iteración de ‘j’, estamos ‘ocultando’ todos los bits en ‘i’ excepto el bit en la posición ‘j’th’. De ahí el nombre ‘ BitMasking ‘.

Usamos el operador BitWise ‘ <<' para desplazar el bit que se va a comprobar cada vez en j. (Estamos tomando la operación BitWise ‘&’ de 1 y x. Si es 1, está SET ya que en álgebra booleana, solo 1.1 = 1)

Aquí hay un fragmento de código en Python.

Código:

n=eval(input("Enter n: ")) # keep sub 20-ish max
for i in range(0,(2**n)):# loop from 0 to (2^n)-1
cursub="Current Subset Contains Elements: "
for j in range(0,n):
if((1<0): #Checking if jth bit in i is set
cursub+=(str(j+1)+" ")
print (cursub)
print ("All ", (2**n)," Subsets printed")


Código en acción: http://ideone.com/8vfz4U

Aquí hay un problema que puede probar: http://www.codechef.com/problems …