Encontrar factores de subconjunto

14

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 , 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.

*                -> *
*.*.*            -> *, *.*.*
*.*.*.*          -> *, *.*, *...*, *.*.*.*
******           -> *, **, *..*, ***, *.*.*, ******
*..*.**..***.*.* -> *, *..*.*, *.....*...*, *..*.**..***.*.*
*...*****.**.**  -> *, *...**.**, *.....*, *...*****.**.**
Post Rock Garf Hunter
fuente
Si tomamos el conjunto como una lista de números (por ejemplo, [1,3,5,7]para *.*.*.*), ¿podemos suponer que está ordenado?
Martin Ender
1
¿Es esto equivalente a encontrar divisores de polinomios cuyos coeficientes están restringidos a 0 y 1?
xnor
1
@xnor no estoy seguro. Si *.*.*= x+x^2+x^4, entonces 1+x+x^2= ***sería un divisor, ¿verdad? x+x^2+x^4 = (1-x+x^2)(1+x+x^2)
mbomb007
1
@JonathanAllan Para sus ejemplos, *aparece como un factor que representa el mismo subconjunto que *.o *...
Martin Ender
1
@JonathanAllan Dice generar todos los conjuntos, no generar todas las representaciones ASCII de los conjuntos válidos.
Martin Ender

Respuestas:

3

Mathematica, 71 68 bytes

#&@@@Cases[(s=Subsets)@s@#,x_/;Sort[Join@@x]==#&&Equal@@(#&@@@x-x)]&

Entrada 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).

Martin Ender
fuente
2

Jalea , 12 bytes

;÷@DỊȦ
ÆDçÐf

Uso de entrada y salida 1y en 0lugar de *y ..

Pruébalo en línea!

Cómo funciona

ÆDçÐf   Main link. Argument: n (integer with decimal digits 1 and 0)

ÆD      Compute all divisors of n.
  çÐf   Filter; call the helper link with left argument d and right argument n for
        all divisors d of n. Return the array of d's for which the helper link
        returns a truthy value.


;÷@DỊȦ  Helper link. Left argument: d. Right argument: n

 ÷@     Divide n by d.
;       Concatenate, yielding [d, n÷d].
   D    Decimal; convert both integers in the pair to base 10.
    Ị   Insignificant; map 1 and 0 to 1, all other positive integers to 0.
     Ȧ  All; return 1 iff the result contains no zeroes.
Dennis
fuente