Imaginemos que tenemos un conjunto finito de enteros positivos. Este conjunto se puede representar como una línea de puntos donde cada número entero presente en el conjunto se rellena como un scantron o una tarjeta perforada . Por ejemplo, el conjunto {1,3,4,6}podría representarse como:
*.**.*
*representa un miembro de nuestro conjunto y .representa un número entero que no es miembro del conjunto.
Estos conjuntos tienen "factores". En términos generales, x es un factor de y si y puede construirse a partir de copias de x. Más rigurosamente, nuestra definición de factor es la siguiente:
- x es un factor de y si y solo si y es la unión de varios conjuntos disjuntos , todos los cuales son x con un desplazamiento.
Que llamaríamos *.*un factor de de *.**.*, ya que está bastante claro compone de dos copias de *.*extremo a extremo puesto.
*.**.*
------
*.*...
...*.*
Los factores no tienen que ser de principio a fin, también diríamos que *.*es un factor de*.*.*.*
*.*.*.*
-------
*.*....
....*.*
Los factores también pueden superponerse. Esto significa *.*que también es un factor de****
****
----
*.*.
.*.*
Sin embargo, un número no puede ser cubierto por un factor más de una vez. Por ejemplo, no*.* es un factor de .*.*.*
Aquí hay un ejemplo más complicado:
*..*.**..***.*.*
Esto tiene *..*.*como factor. Puede ver eso a continuación, donde he alineado las tres instancias de *..*.*.
*..*.**..***.*.*
----------------
*..*.*..........
......*..*.*....
..........*..*.*
Tarea
Dado un conjunto por cualquier representación razonable, todos los conjuntos son factores de la entrada.
Puede indexar por cualquier valor (es decir, puede seleccionar un número más pequeño que pueda estar presente en la entrada). También puede suponer que el conjunto de entrada siempre contendrá ese valor más pequeño.
Esta es una pregunta de código de golf , por lo que debe intentar hacerlo en la menor cantidad de bytes posible.
Casos de prueba
Estos casos de prueba se hicieron a mano, puede haber un error o dos en los más grandes.
* -> *
*.*.* -> *, *.*.*
*.*.*.* -> *, *.*, *...*, *.*.*.*
****** -> *, **, *..*, ***, *.*.*, ******
*..*.**..***.*.* -> *, *..*.*, *.....*...*, *..*.**..***.*.*
*...*****.**.** -> *, *...**.**, *.....*, *...*****.**.**
fuente
[1,3,5,7]para*.*.*.*), ¿podemos suponer que está ordenado?*.*.*=x+x^2+x^4, entonces1+x+x^2=***sería un divisor, ¿verdad?x+x^2+x^4 = (1-x+x^2)(1+x+x^2)*aparece como un factor que representa el mismo subconjunto que*.o*...Respuestas:
Mathematica,
7168 bytesEntrada como
{1,3,5,7}(ordenada) y salida como{{1, 3, 5, 7}, {1, 3}, {1, 5}, {1}}. La función arrojará un montón de mensajes.Esto es O (2 2 No ) (donde N es la longitud de la entrada y o = p = e = 1 ...). Genera todos los subconjuntos de subconjuntos, luego selecciona aquellos que resultan en el envío de entrada cuando se unen (asegurando que solo estamos considerando particiones) y donde todos los elementos son iguales si restamos el valor más pequeño de cada subconjunto).
fuente
Jalea , 12 bytes
Uso de entrada y salida
1y en0lugar de*y..Pruébalo en línea!
Cómo funciona
fuente