Enlazar a través de diferentes conjuntos de permutaciones únicas

Question

Tengo dificultades para empezar a utilizar el código de diseño para este problema.

Tengo una cantidad fija de números aleatorios, en este caso 8 números. R [] = {1, 2, 3, 4, 5, 6, 7, 8};

Que se colocarán en 3 conjuntos de números, con la única restricción de que cada conjunto contenga un mínimo valor uno, y cada valor solo se puede usar una vez. Editar: los 8 números deben utilizarse

Por ejemplo:

R1 [] = {1, 4}

R2 [] = {2, 8, 5, 6}

R3 [] = {7, 3}

Necesito recorrer todas las combinaciones posibles de un conjunto R1, R2, R3. El orden no es importante, por lo que si el ejemplo anterior pasó, no necesito

R1 [] = {4, 1}

R2 [] = {2, 8, 5, 6}

R3 [] = {7, 3}

NOR

R1 [] = {2, 8, 5, 6}

R2 [] = {7, 3}

R3 [] = {1, 4}

¿Qué es un buen método?

Answer 1

Probablemente no sea el mejor enfoque, pero debería funcionar.

Determinar el número de combinaciones de tres números que suma a 8:

1,1,6 
1,2,5 
1,3,4 
2,2,4 
2,3,3 

Para encontrar el anterior Empecé con:

6,1,1 then subtracted 1 from six and added it to the next column... 
5,2,1 then subtracted 1 from second column and added to next column... 
5,1,2 then started again at first column... 
4,2,2 carry again from second to third 
4,1,3 again from first... 
3,2,3 second -> third 
3,1,4 

a sabiendas de que menos de la mitad es de 2 todas las combinaciones deben haber sido encontrado ... pero dado que la lista no es larga, podríamos ir al final.

Ahora ordena cada lista de 3 de mayor a menor (o viceversa) Ahora ordena cada lista de 3 una con relación a la otra. Copie cada lista única en una lista de listas únicas. Ahora tenemos todas las combinaciones que se suman a 8 (creo que cinco listas).

Consideremos ahora una lista en el anterior conjunto

6,1,1 todas las combinaciones posibles se encuentran por:

8 Pick 6, (ya que recogimos de seis sólo hay 2 para realizar los pronósticos de) 2 pick 1, 1 pick 1 que funciona hasta 28 * 2 * 1 = 56, vale la pena saber cuántas posibilidades hay para que pueda probar.

elegir n r (r elementos de recoger opciones n total)

n C r = n!/[(n-r)! r!]

Así que ya tienen el número total de iteraciones para cada componente de la lista para el primero es 28 ...

Bueno recoger los artículos en 6 8 es lo mismo que crear una lista de 8 menos 2 elementos, pero ¿qué dos elementos?

Bien si eliminamos 1,2 que nos deja con 3,4,5,6,7,8. Consideremos todos los grupos de 2 ... Comenzando con 1,2, el siguiente sería 1,3 ... entonces lo siguiente se lee columna por columna.

12 
13 23 
14 24 34 
15 25 35 45 
16 26 36 46 56 
17 27 37 47 57 67 
18 28 38 48 58 68 78 

Resumiendo cada una de las columnas anteriores nos da 28. (lo que esto sólo cubre el primer dígito en la lista (6,1,1) repetir el procedimiento para el segundo dígito (un uno), que es "2 Elija 1 "Por lo tanto, de la izquierda más de dos dígitos de la lista anterior elegimos uno de dos y luego para el último elegimos el restante.

Sé que este no es un algoritmo detallado pero espero que pueda para comenzar

Answer 2

Genere todas las combinaciones de subconjuntos recursivamente de la manera clásica. Cuando llegue al punto donde el número de elementos restantes es igual al número de subconjuntos vacíos, entonces restrinjate solo a los subconjuntos vacíos.

He aquí una implementación de Python:

def combinations(source, n): 
    def combinations_helper(source, subsets, p=0, nonempty=0): 
    if p == len(source): 
     yield subsets[:] 
    elif len(source) - p == len(subsets) - nonempty: 
     empty = [subset for subset in subsets if not subset] 
     for subset in empty: 
     subset.append(source[p]) 
     for combination in combinations_helper(source, subsets, p+1, nonempty+1): 
      yield combination 
     subset.pop() 
    else: 
     for subset in subsets: 
     newfilled = not subset 
     subset.append(source[p]) 
     for combination in combinations_helper(source, subsets, p+1, nonempty+newfilled): 
      yield combination 
     subset.pop() 

    assert len(source) >= n, "Not enough items" 
    subsets = [[] for _ in xrange(n)] 
    for combination in combinations_helper(source, subsets): 
    yield combination 

Y una prueba:

>>> for combination in combinations(range(1, 5), 2): 
... print ', '.join(map(str, combination)) 
... 
[1, 2, 3], [4] 
[1, 2, 4], [3] 
[1, 2], [3, 4] 
[1, 3, 4], [2] 
[1, 3], [2, 4] 
[1, 4], [2, 3] 
[1], [2, 3, 4] 
[2, 3, 4], [1] 
[2, 3], [1, 4] 
[2, 4], [1, 3] 
[2], [1, 3, 4] 
[3, 4], [1, 2] 
[3], [1, 2, 4] 
[4], [1, 2, 3] 
>>> len(list(combinations(range(1, 9), 3))) 
5796 

Answer 3

tengo frente a mí Knuth Volumen 4, Fascículo 3, Generación de todas las combinaciones y particiones, sección 7.2 .1.5 Generación de todas las particiones configuradas (página 61 en el fascículo).

Primero detalles algoritmo H, cadenas de crecimiento restringidos en orden lexicográfico debido a George Hutchinson. Parece simple, pero no voy a sumergirme en él ahora mismo.

En la siguiente página bajo una elaboración códigos gris para particiones conjunto reflexiona:

Supongamos, sin embargo, que no estamos interesados ​​en todo de las particiones; es posible que solo deseemos los que tienen bloques m. ¿Podemos ejecutar esto a través de la colección más pequeña de cadenas de crecimiento restringidas, que aún cambian un dígito a la vez?

Luego detalla una solución debido a Frank Ruskey.

La solución simple (y cierta para ser correcta) es codificar el filtrado de Algoritmo H en particiones donde m==3 y ninguna de las particiones son el conjunto vacío (de acuerdo con las restricciones establecidas). Sospecho que el algoritmo H funciona increíblemente rápido, por lo que el costo de filtrado no será grande.

Si está implementando esto en un 8051, puede comenzar con el algoritmo Ruskey y luego solo filtrar las particiones que contengan el conjunto vacío.

Si está implementando esto en algo más pequeño que un asunto de 8051 y milisegundos, puede inicializar cada una de las tres particiones con un elemento único (un simple bucle anidado de tres niveles) y luego aumentar particionando en el resto cinco elementos para m==3 usando el algoritmo de Ruskey. No tendrá que filtrar nada, pero sí debe hacer un seguimiento de los cinco elementos restantes para la partición.

Lo bueno de filtrar el algoritmo general es que no tiene que verificar ninguna habilidad propia, y luego cambia de opinión sobre sus limitaciones sin tener que revisar su inteligencia.

Incluso podría funcionar una solución más adelante, pero eso es todo por ahora.

P.S. para los guppies de Java: descubrí buscando en "cadenas de crecimiento restringidas de George Hutchison" un determinado paquete ca.ubc.cs.kisynski.bell con documentación para el método growthStrings() que implementa el algoritmo de Hutchison.

parece estar disponible en http://www.cs.ubc.ca/~kisynski/code/bell/

Answer 4

Girar el problema en su cabeza y usted encontrará una solución sencilla. Tienes 8 números que cada uno debe asignarse exactamente a un grupo; La "solución" es solo una solución si se asignó al menos un número a cada grupo.

La aplicación trivial implicaría 8 de bucles y de unos pocos, si (pseudocódigo):

for num1 in [1,2,3] 
    for num2 in [1,2,3] 
    for num3 in [1,2,3] 
     ... 
     if ((num1==1) or (num2==1) or (num3 == 1) ... (num8 == 1)) and ((num1 == 2) or ... or (num8 == 2)) and ((num1 == 3) or ... or (num8 == 3)) 
      Print Solution! 

También se puede implementar de forma recursiva, utilizando dos matrices y un par de funciones. Mucho más agradable y más fácil de depurar/seguimiento (pseudocódigo):

numbers = [1, 2, 3, 4, 5, 6, 7, 8] 
positions = [0, 0, 0, 0, 0, 0, 0, 0] 

function HandleNumber(i) { 
    for position in [1,2,3] { 
    positions[i] = position; 
    if (i == LastPosition) { 
     // Check if valid solution (it's valid if we got numbers in all groups) 
     // and print solution! 
     } 
    else HandleNumber(i+1) 
    }  
} 

La tercera aplicación utilizaría sin recursividad y un poco de marcha atrás. Pseudocódigo, nuevamente:

numbers = [1,2,3,4,5,6,7,8] 
groups = [0,0,0,0,0,0,0,0] 

c_pos = 0 // Current position in Numbers array; We're done when we reach -1 
while (cpos != -1) { 
    if (groups[c_pos] == 3) { 
     // Back-track 
     groups[c_pos]=0; 
     c_pos=c_pos-1 
    } 
    else { 
    // Try the next group 
    groups[c_pos] = groups[c_pos] + 1 
    // Advance to next position OR print solution 
    if (c_pos == LastPostion) { 
     // Check for valid solution (all groups are used) and print solution! 
     } 
    else 
     c_pos = c_pos + 1 
    } 
}