print possible permutations combination all algorithm combinations

algorithm - possible - print permutations in c



Encuentra todas las combinaciones de 3x3 holepunch (7)

Mi solución: 116 formas únicas

Al probar 2 formas para la igualdad, la comparación del número de pines ahorra mucho tiempo. Pero mi avance más grande fue darme cuenta de que todas esas 25 posiciones pueden ser reemplazadas por esto: para cada una de las dos formas de 3x3 a verificar por igualdad, concatene las líneas con dos ceros y luego recorte los ceros al principio y al final. Los ceros concat son para evitar envolverse. Ejemplo:

010 => 01000 => 0100010100000 => 1000101 101 10100 000 000 000 => 00000 => 0000001000101 => 1000101 010 01000 101 101

Luego solo prueba los resultados para la igualdad. Eso es 4 repeticiones fáciles (1 para cada rotación) en lugar de 100 (25 posiciones * 4 rotaciones) más complejas.

Hora:
cadenas solo

  • fuerza bruta, las 25 posiciones para cada rotación: 2018ms
  • ... 00 ... 00 ... recortado: 75ms
  • más optimización: 59ms

OOP y mejor almacenamiento en caché: 17 ms

Estaba en un carnaval donde en cada lugar marcan su programa con un golpe especial. El perforador es una cuadrícula de 3x3 espacios. En cada espacio, hay un alfiler que pincha su papel o no lo hay. Esto me hizo preguntarme cuántos patrones diferentes podrías hacer con esta herramienta. Lo primero que pensé fue: 2 ^ 9 = 512, pero los 9 espacios sin pin no son realmente buenos, así que realmente: 511.

Entonces la complejidad me golpeó. Especialmente dado que los trabajadores no son tan cuidadosos cuando perforan su periódico, todos se verían idénticos:

x.. .x. ... etc. .x. x.. .x. ... ... ..x

Pregunta: ¿Cómo podría escribirse una prueba para tener en cuenta la rotación y el cambio?

Diligencia y pensamientos hasta el momento:

  • Binary se siente como una parte obvia de esta ecuación
  • Cuando se encuentra un patrón único, guárdelo en la memoria para que los patrones futuros puedan ser probados en su contra
  • Hay 4 posibilidades de rotación.
    Editar: lo que quiero decir con "rotaciones" es que puedes tomar cualquier forma y girarla 90 grados. Considere el patrón que es un punto en la esquina superior izquierda. Puede girarlo / rotarlo 90 grados y obtener el punto en la esquina superior derecha. Hazlo de nuevo y está en la esquina inferior derecha. De nuevo, está en la esquina inferior izquierda. Usando el cálculo puro de 2 ^ 9, estas son 4 combinaciones diferentes. Sin embargo, para este problema, estos son exactamente el tipo de duplicados que intento eliminar.
  • Para cada rotación, hay 25 maneras de hacer superposición de rejillas de 3x3:

Superposiciones:

/ = the spaces in the new one to test / = the spaces in a verified unique one 1 2 25 / / / . . . . . / / / . . . . . . . . . . / / / . . . . . / / / . . . . . . . . . . / / X / / . . . / X X / . . . . / / / . . . . / / / . . . . / / / . . . . / / / . . . . / / / . . . . / / / . . . . / / X / / . . . . . . . . . . . . . . . . . . / / / . . . . . . . . . . . . . . . . . . / / /

  • No es necesario probar una superposición si cualquiera de los patrones contiene un pin que no se encuentra en el área de superposición. Bitwise Y podría ayudar aquí.
  • Si convierte cada posición para cada uno de los 2 patrones en cadenas, puede simplemente verificar la igualdad
  • ¿Pueden combinarse estas dos ideas anteriores para aumentar la eficiencia?

No creo que esto sea como el caso de la esfera, ya que no se puede girar alrededor de los bordes? ES DECIR:

XOO XXO XOO

no es lo mismo que

OOX XOX OOX

Intenté contar a mano sobre papel para ver lo que obtuve. Considere la caja de 2x2: tiene 1 con 0 puntos, 1 con 1 punto, 2 con 2 puntos (adyacente o diagonal), 1 con 3 puntos y 1 con 4; para un total de 5 (o 4 si descuida el caso vacío). Tenga en cuenta que la enumeración es simétrica, ya que es lo mismo contar los espacios vacíos que los totales. Para el caso 3x3, obtuve esto:

C(0) = 1 C(1) = 1 C(2) = 5 C(3) = 10 C(4) = 21

y luego por simetría, 21, 10, 5, 1, 1

Tengo 76. Podría haber contado mal, muy especialmente en el caso 4/5.

La única forma en que puedo pensar en enumerar estos automáticamente implicaría desplazar y rotar los patrones para ver si coinciden con uno previamente enumerado. El cambio es complicado, ya que solo puedes cambiar hasta que "choques" contra un borde.

No entiendo claramente esta parte sobre las rotaciones, pero para este escenario:

Hay 3x3 = 9 hoyos y 10 cajas y cada vez que solo un caso puede tener lugar:

Case 1 = no holes Case 2 = one hole ... Case 10 = 9 holes

Entonces sería así con la fórmula de combinación C (n, k):

Total = C (9,0) + C (9,1) + .... + C (9,9)

esto es para sumar k combinaciones diferentes de n elementos.

Totol = 1 + 9 + 36 + 84 + 126 + 126 + 84 + 36 + 9 + 1 = 512

Creo que tienes razón, 512 parece ser correcto y theoritically sin PIN se define como una combinación también, si no lo quieres solo elimínalo para obtener 511.

Todos estos casos ocurren por separado, así que agregamos los diferentes casos.

Si ocurrieran sincrónicamente, por ejemplo calculando las combinaciones para 3 empleados perforando el papel una vez o calculando las combinaciones para marcar el papel 3 veces por un empleado, entonces se vuelve más complicado y debería ser 512 * 512 * 512 según la regla nxm.

La regla m * n en una pantalla simple es:

Tengo 4 = m bolsillos y dos = n manos:

my_left * 4 (bolsillos) = 4 my_right * 4 (bolsillos) = 4

total = 4 + 4 = 4 * 2 = m * n

Solo una mano puede ingresar al bolsillo a la vez o solo una combinación de un empleado se combina con una sola combinación del otro empleado y esta es la razón exacta por la que tomamos la regla m * n.

Esto es lo que creo, no soy matemático y no pretendo ser correcto al 100%, es solo lo que recuerdo del curso de probabilidades.

No pretendo ser 100% correcto, es exactamente lo que recuerdo para el curso de probabilidad.

En cuanto a la superposición de patrones, verificando si el patrón ya se encuentra, etc. no me molestaría en absoluto ya que hay tantos algoritmos en el pseudocódigo que generan combinaciones. Como generan, no es necesario verificar las superposiciones ni nada.

Después de todo esto es lo que significa que está diseñado a priori para encontrar todos los resultados, simplemente déjalo funcionar.

Encontré una vez un algoritmo aún más raro que las combinaciones simples y cuando lo cambié a php, hizo el trabajo a la perfección, sin necesidad de preocuparse por superposiciones ni nada.

No está pidiendo contar el número de patrones únicos hasta la traducción y la rotación, sino para una prueba de congruencia.

Elija una representación de cadena de bits de la cuadrícula de 3x3. Elegiré fila por fila, de arriba hacia abajo. Al establecer un bit donde se perfora su agujero correspondiente, ahora podemos mapear números enteros de 9 bits para perforar patrones (y viceversa).

Para cualquier representación particular, podemos idear operaciones de manipulación de bits que representan rotaciones y traducciones. Algunas traducciones son ilegales para realizar en algunos patrones, ya que deseamos evitar "envolverse".

Así como las rotaciones y las traducciones son reversibles, también lo serán nuestras operaciones. Si dos movimientos asignan el patrón A a B, y luego B a C, ciertamente podemos componer los movimientos para hacer una transformación que tome de A a C. No hacer nada (la transformación de identidad) también es legal, por lo que podemos alcanzar A desde A. Accesibilidad por transformación es por lo tanto una relación de equivalencia en los patrones de perforación, y patrones tan equivalentes partición el espacio.

Al tener un medio para asignar un puntaje entero positivo a cada patrón de perforación, podemos invocar el principio bien ordenado: la clase de equivalencia que contiene el patrón contendrá un patrón único (incluidas las traducciones y rotaciones) de puntaje mínimo. Elegiremos este patrón mínimo para ser un representante de la clase de equivalencia. Si dos patrones tienen el mismo representante de clase de equivalencia, necesariamente son congruentes. Si no lo hacen, necesariamente no son congruentes.

Dado un patrón, ¿cómo encontramos su representante de menor peso? Por inspección, no se garantiza que los algoritmos codiciosos funcionen. Podemos alcanzar uno de los innumerables algoritmos de optimización heurística, o podemos notar que solo estamos presionando 9 bits y buscando exhaustivamente el espacio. Cabe señalar que por la misma razón, esto se presta muy bien para que se compute una vez, y se empuje en una tabla de búsqueda para siempre.

Aquí está la búsqueda exhaustiva. Tenga en cuenta que el almacenamiento en caché es bastante rápido (menos de un segundo).

#!/usr/bin/env ruby require ''set'' class PunchPattern < String @@representatives = Hash.new do |h, k| equivalence_class = k.closure representative = equivalence_class.min k.closure.each do |node| h[node] = representative end representative end def initialize(s) raise "9 digits of 0 and 1, pls" unless s =~ /[01]{9}/ super end def left return nil unless self =~ /0..0..0../ PunchPattern.new([self[1...3], 0, self[4...6], 0, self[7...9], 0].join) end def right return nil unless self =~ /..0..0..0/ PunchPattern.new([0, self[0...2], 0, self[3...5], 0, self[6...8]].join) end def up return nil unless self =~ /000....../ PunchPattern.new([self[3...9], 0, 0, 0].join) end def down return nil unless self =~ /......000/ PunchPattern.new([0, 0, 0, self[0...6]].join) end def turn PunchPattern.new([2, 5, 8, 1, 4, 7, 0, 3, 6].collect { |i| self[i].chr }.join) end def closure seen = Set.new([]) frontier = Set.new([self]) until frontier.empty? node = frontier.first frontier.delete(node) seen.add(node) %w{left right up down turn}.collect do |motion| node.send motion end.compact.each do |neighbor| frontier.add(neighbor) unless seen.include? neighbor end end seen end def representative self.class.representatives[self] end def self.representatives @@representatives end end (0...512).collect do |p| p = PunchPattern.new(p.to_s(2).rjust(9, ''0'')) [p.representative, p] end.inject(Hash.new { |h, k| h[k] = [] }) do |h, pair| h[pair.first] << pair.last h end.sort_by { |pair| pair.first }.each do |representative, patterns| puts patterns.collect { |p| p[0...3] + " " }.join puts patterns.collect { |p| p[3...6] + " " }.join puts patterns.collect { |p| p[6...9] + " " }.join puts end puts "#{PunchPattern.representatives.values.uniq.size} total congruence classes"

Produce

$ ./congruence.rb 000 000 000 000 000 000 000 000 000 001 010 100 000 000 000 001 010 100 000 000 000 001 010 100 000 000 000 000 000 000 000 000 000 000 000 000 000 001 010 011 100 110 000 000 001 010 011 100 110 001 010 000 100 000 011 110 001 010 000 100 000 000 000 000 000 000 000 000 001 010 100 101 000 101 000 000 000 000 101 000 001 010 100 000 000 000 001 010 100 111 000 111 001 010 100 000 111 000 001 010 100 000 000 000 000 000 001 010 010 100 001 010 010 100 010 001 100 010 010 001 100 010 000 000 000 000 000 000 000 000 000 000 000 000 001 010 010 011 011 100 110 110 001 010 010 011 011 100 110 110 011 011 110 001 010 110 010 100 011 011 110 001 010 110 010 100 000 000 000 000 000 000 000 000 000 001 010 100 001 100 000 000 100 000 001 010 000 000 001 010 011 100 101 110 001 101 101 000 000 000 100 000 101 100 000 011 001 110 000 010 000 000 001 010 010 011 100 100 001 011 110 001 010 100 010 100 110 100 000 001 001 000 010 010 000 000 001 010 011 100 110 111 001 111 111 010 001 100 010 100 111 100 000 011 001 110 010 000 000 000 001 010 010 010 100 101 010 101 010 001 100 101 010 010 101 010 001 010 010 000 100 000 000 000 001 010 010 010 100 111 010 111 011 011 110 111 110 010 111 010 001 010 010 000 100 000 000 000 011 110 011 110 011 110 011 110 000 000 000 000 010 011 011 100 101 110 011 101 001 010 101 010 110 100 101 110 011 001 000 110 000 010 000 010 011 100 011 011 110 110 110 001 000 010 000 000 010 011 011 100 110 111 011 111 011 011 111 110 110 110 111 110 011 001 000 110 010 000 000 001 010 100 100 000 000 001 001 010 100 000 000 000 001 001 010 010 100 110 100 110 001 010 010 100 011 001 011 001 010 010 100 100 000 000 000 000 001 010 011 100 101 110 100 101 000 000 000 101 001 000 101 001 011 110 010 000 000 100 000 000 001 010 011 100 110 111 100 111 001 010 010 111 100 001 111 001 011 110 010 000 100 000 000 000 001 010 011 101 110 110 101 110 010 100 001 011 010 101 011 101 011 110 010 000 100 000 000 011 101 110 101 000 101 000 101 011 000 110 000 000 011 011 101 110 110 111 101 111 001 010 111 010 100 101 111 101 011 011 000 110 110 000 000 001 010 110 110 011 110 011 011 010 100 000 000 000 001 010 011 110 110 111 110 111 011 110 011 110 111 011 111 011 011 110 010 100 000 000 000 011 110 111 111 011 110 111 111 011 110 000 001 100 000 000 100 001 001 100 101 101 000 000 000 000 101 101 001 100 001 011 100 100 000 000 001 100 110 100 001 001 001 100 101 111 000 100 001 000 111 101 001 100 001 001 100 110 001 100 000 000 100 100 011 001 001 100 101 111 001 000 100 000 101 111 100 001 001 011 100 110 001 100 100 001 110 100 011 001 001 100 111 111 001 100 001 100 111 111 001 100 001 100 010 010 100 001 001 100 101 101 010 010 010 010 101 101 001 100 001 011 100 100 010 010 011 110 110 100 001 001 001 100 101 111 010 110 011 010 111 101 001 100 001 001 100 110 011 110 010 010 100 100 011 001 001 100 101 111 011 010 110 010 101 111 100 001 001 011 100 110 011 110 110 011 110 100 011 001 001 100 111 111 011 110 011 110 111 111 001 100 001 010 100 101 100 000 001 000 001 101 100 010 001 010 010 100 100 001 100 001 010 100 001 010 001 010 101 110 100 100 001 001 011 101 010 100 001 101 101 110 100 000 001 000 101 011 100 101 001 011 100 110 100 001 001 100 110 100 011 001 001 101 110 111 100 001 100 001 111 011 101 100 001 010 100 111 101 000 101 000 001 111 100 010 001 010 010 110 101 100 101 001 010 011 100 010 001 010 110 111 101 100 101 001 011 111 100 010 001 110 101 000 100 011 001 101 110 111 101 101 000 000 101 100 111 011 001 011 110 110 101 101 001 100 110 100 011 011 001 110 111 111 101 100 001 101 111 111 011 100 001 010 100 101 110 010 011 010 001 101 100 010 001 010 010 100 110 011 110 011 010 100 001 010 001 010 101 110 110 110 011 011 011 101 010 100 001 101 101 110 110 010 011 010 101 011 100 101 001 011 100 110 110 011 011 110 110 100 011 001 001 101 110 111 110 011 110 011 111 011 101 100 001 010 100 111 111 010 111 010 001 111 100 010 001 010 010 110 111 110 111 011 010 011 100 010 001 010 110 111 111 110 111 011 011 111 100 010 001 110 111 010 100 011 001 101 110 111 111 111 010 010 101 100 111 011 001 011 110 110 111 111 011 110 110 100 011 011 001 110 111 111 111 110 011 111 111 111 011 100 010 011 100 101 001 100 001 100 101 001 110 010 010 010 011 100 001 101 100 101 110 001 010 010 010 011 100 111 001 101 101 100 111 001 110 010 010 011 100 101 011 110 011 110 101 001 110 010 010 010 011 100 011 111 110 111 110 001 010 010 010 011 100 111 011 111 111 110 111 001 110 010 010 101 010 010 010 011 110 101 101 101 101 011 110 010 010 010 011 101 110 101 100 101 001 101 011 010 110 010 011 110 111 101 101 101 101 111 011 110 010 010 111 010 010 010 011 110 111 111 111 111 011 110 010 010 010 011 101 110 111 110 111 011 101 011 010 110 010 011 110 111 111 111 111 111 111 011 110 010 011 100 101 101 000 001 000 100 101 101 110 001 011 100 000 101 110 001 011 100 101 111 000 101 101 000 111 101 001 110 011 100 101 111 001 001 100 100 101 111 110 001 011 011 100 110 001 100 101 101 110 110 011 001 011 100 111 111 001 101 100 101 111 111 110 001 011 100 101 101 010 011 010 110 101 101 110 001 011 100 010 111 110 001 011 100 101 111 010 111 111 010 111 101 001 110 011 100 101 111 011 011 110 110 101 111 110 001 011 011 100 110 011 110 111 111 110 110 011 001 011 100 111 111 011 111 110 111 111 111 110 001 011 101 101 110 100 001 100 001 101 110 011 101 011 101 110 111 100 101 101 001 111 011 101 110 011 101 110 111 101 101 001 100 101 110 111 011 011 110 101 101 110 011 011 110 111 111 101 101 101 101 111 111 011 110 011 101 101 110 110 011 110 011 101 110 011 101 011 101 110 111 110 111 111 011 111 011 101 110 011 101 110 111 111 111 011 110 101 110 111 011 011 110 111 111 110 011 011 110 111 111 111 111 111 111 111 111 011 110 101 000 101 101 101 101 111 000 001 100 000 111 101 101 101 101 101 111 111 001 100 001 100 111 111 101 101 101 010 101 101 101 101 111 010 011 110 010 111 101 101 101 101 101 111 111 011 110 011 110 111 111 101 101 101 111 101 000 101 111 101 111 111 111 101 001 100 101 111 111 111 101 101 111 111 010 101 111 101 111 111 111 111 011 110 111 111 111 111 101 111 101 111 111 111 111 117 total congruence classes

..para 117 clases.

Primero, podemos ver dos golpes equivalentes, a excepción de una traducción, como rotaciones entre sí. Imagine que el patrón de perforación está en la superficie de una esfera: podemos "traducirla" girando la esfera a lo largo de los ejes horizontal y vertical (tal como se sostiene en nuestra mano).

Dos golpes que son equivalentes hasta la rotación (como un giro de 90 grados) también los capturamos girando nuestra esfera a lo largo del tercer eje restante.

Ahora hemos reducido el problema a "¿Cuántos patrones únicos de perforación hay en la superficie de una esfera, hasta la rotación?" Para contar objetos únicos hasta la simetría de esta manera, no quieres el lema de Burnside . Este libro es un buen manual.

Solo debemos considerar los patrones que tienen golpes en la primera fila y columna. Si la primera fila está vacía, el patrón se puede mover hacia arriba. Si la primera columna está vacía, el patrón se puede mover a la izquierda. En cualquier caso, podemos derivar un patrón similar que consideremos.

Para estos patrones, necesitamos verificar si las versiones giradas son idénticas. Hacemos esto aplicando hasta tres rotaciones de 90 grados, posiblemente desplazándonos a la izquierda para eliminar columnas vacías delanteras (la primera fila nunca está vacía) y encontrando el patrón con el valor numérico más bajo.

A continuación, podemos agregar este valor a un conjunto de hash, que solo mantendrá valores únicos.

El patrón vacío no está incluido porque todas sus filas están vacías.

Para implementar esto, codificamos patrones como bits sucesivos:

012 345 678

Las operaciones que necesitaremos son en su mayoría muy simples:

Test for an empty row: (n & 7) == 0 // bits 0,1,2 not set Test for an empty column: (n & 73) == 0 // bits 0,3,6 not set Shift pattern up: n -> (n >> 3) Shift pattern left: n -> (n >> 1)

La parte más difícil es la rotación, que en realidad está reorganizando todos los bits:

n -> ((n & 1) << 2) + ((n & 2) << 4) + ((n & 4) << 6) + ((n & 8) >> 2) + (n & 16) + ((n & 32) << 2) + ((n & 64) >> 6) + ((n & 128) >> 4) + ((n & 256) >> 2);

Cª#:

public static int Count3x3() { HashSet<int> patterns = new HashSet<int>(); for (int i = 0; i < 512; i++) { if ((i & 7) == 0 || (i & 73) == 0) continue; int nLowest = i; int n = i; do { nLowest = Math.Min(nLowest, n); n = ((n & 1) << 2) + ((n & 2) << 4) + ((n & 4) << 6) + ((n & 8) >> 2) + (n & 16) + ((n & 32) << 2) + ((n & 64) >> 6) + ((n & 128) >> 4) + ((n & 256) >> 2); while ((n & 73) == 0) n >>= 1; } while (n != i); patterns.Add(nLowest); } return patterns.Count; }

Esta función devuelve 116. El tiempo empleado en mi máquina fue de 0.023ms.

EDITAR : Puede obtener una mejora adicional de 7x al usar 4 observaciones:

  1. Podemos usar una matriz visitada simple en lugar de un conjunto de hash. Si se vio un patrón antes, no lo contamos. Esto también elimina la necesidad de realizar un seguimiento del patrón ''más bajo'' en el ciclo interno. Si se visitó un patrón, también se visitó su patrón más bajo girado.
  2. Si no tenemos una simetría de rotación de 180 grados, la tercera rotación no dará el patrón original. La cuarta rotación lo hará, siempre, por lo que es innecesario.
  3. La expresión de rotación puede ser ligeramente simplificada.

Entonces, si aplicamos estas observaciones y desenrollamos el ciclo interior do, obtenemos lo siguiente:

static int Rotate(int n) { n = ((n & (1+32)) << 2) + ((n & 2) << 4) + ((n & 4) << 6) + ((n & (8+256)) >> 2) + (n & 16) + ((n & 64) >> 6) + ((n & 128) >> 4); while ((n & 73) == 0) n >>= 1; return n; } public static int Count3x3_3() { bool[] visited = new bool[512]; int count = 0, r; for (int i = 0; i < 512; i++) { if (visited[i]) continue; if ((i & 7) == 0 || (i & 73) == 0) continue; count++; if ((r = Rotate(i)) == i) continue; visited[r] = true; if ((r = Rotate(r)) == i) continue; visited[r] = true; visited[Rotate(r)] = true; } return count; }

Esto se ejecuta en aproximadamente 3μs en la misma máquina.

Vale la pena señalar que si realmente necesita que cada forma se "parezca" única, sin importar cómo se gira o se desplaza, tiene muy pocos para elegir. Por ejemplo, un único golpe, sin importar DONDE se encuentre en la grilla, siempre tendrá el mismo aspecto. Además, suponiendo una cuadrícula cuadrada y alfileres redondos, y suponiendo que las diferencias menores de espaciado (√2) son insignificantes, entonces 2 agujeros diagonales en una fila se verán igual que dos pines adyacentes, ya que todo el espectador ve que hay 2 orificios muy juntos. Del mismo modo, 3 en diagonal se verá como 3 en línea recta, lo que limita drásticamente tus opciones.

Tenga en cuenta que la forma es probablemente una mejor palabra para lo que estamos buscando que para la combinación , ya que no nos importa cuál fue la combinación real, sino cuál es la forma resultante en el papel.

Creo que podemos plantear que, independientemente de la forma, se puede rotar y desplazar de manera que se perfora el pin superior izquierdo (específicamente si se permite la rotación en 45 grados), lo que nos permite restringir aún más nuestra búsqueda. Logramos esto usando las siguientes reglas:

  1. Si se perfora cualquier esquina, gire la rejilla hasta que la esquina perforada esté en la esquina superior izquierda.
  2. De lo contrario, desplace el patrón hacia arriba y hacia la izquierda como sea posible.
  3. Repita el paso 1
  4. Si llegamos tan lejos, entonces sabemos que solo se perfora la posición media superior (ya que sabemos que ninguna de las esquinas), en cuyo caso giramos el patrón 45 grados, haciendo que la mitad superior ahora sea la parte superior izquierda. QED.

Hice una búsqueda muy rápida de fuerza bruta de papel y lápiz para posibles formas y parece que la lista de opciones viables es tan pequeña que podría enumerarlas todas en pocos minutos.