Cadenas Gozinta

(Inspirado por el Proyecto Euler # 606 )

Una cadena de gozinta para n es una secuencia {1,a,b,...,n}en la que cada elemento divide adecuadamente al siguiente. Por ejemplo, hay ocho cadenas de gozinta distintas para 12:

{1,12}, {1,2,12}, {1,2,4,12}, {1,2,6,12}, {1,3,12}, {1,3,6,12}, {1,4,12} and {1,6,12}.

El reto

Escriba un programa o función que acepte un entero positivo ( n > 1) y genere o devuelva todas las cadenas de gozinta distintas para el número dado.

1. El orden en las cadenas importa (ascendente), el orden de las cadenas no.
2. En el caso de que exista una posibilidad remota, no puede usar un dispositivo incorporado que resuelva el desafío.
3. Este es el código de golf .

Editar: Eliminar 1como una entrada potencial.

Python 3 , 68 65 bytes

Editar: -3 bytes gracias a @notjagan

f=lambda x:[y+[x]for k in range(1,x)if x%k<1for y in f(k)]or[[x]]

Pruébalo en línea!

Explicación

Cada cadena de gozinta consiste en el número xal final de la cadena, con al menos un divisor a la izquierda de la misma. Para cada divisor kde xlas cadenas [1,...,k,x]son distintas. Podemos por lo tanto para cada divisor kencontrar todos sus distintas cadenas gozinta y anexar xal final de las mismas, para obtener todas las distintas cadenas gozinta con kdirectamente a la izquierda de x. Esto se hace de forma recursiva hasta x = 1donde [[1]]se devuelve, ya que todas las cadenas de gozinta comienzan con 1, lo que significa que la recursión ha tocado fondo.

El código se vuelve tan corto debido a la comprensión de la lista de Python que permite la doble iteración. Esto significa que los valores encontrados en f(k)se pueden agregar a la misma lista para todos los divisores diferentes k.

Casco , 13 bytes

ufo=ḣ⁰…ġ¦ΣṖḣ⁰

Un enfoque algo diferente al de H.PWiz , aunque todavía por fuerza bruta. Pruébalo en línea!

Explicación

La idea básica es concatenar todas las subsecuencias [1,...,n]y dividir el resultado en sublistas donde cada elemento divide al siguiente. De estos, mantenemos aquellos que comienzan 1, terminan ny no contienen duplicados. Esto se hace con el "rangify" incorporado …. Luego queda descartar duplicados.

ufo=ḣ⁰…ġ¦ΣṖḣ⁰  Input is n=12.
           ḣ⁰  Range from 1: [1,2,..,12]
          Ṗ    Powerset: [[],[1],[2],[1,2],[3],..,[1,2,..,12]]
         Σ     Concatenate: [1,2,1,2,3,..,1,2,..,12]
       ġ¦      Split into slices where each number divides next: [[1,2],[1,2],[3],..,[12]]
 fo            Filter by
      …        rangified
   =ḣ⁰         equals [1,...,n].
u              Remove duplicates.

Jalea , 9 8 bytes

ÆḌ߀Ẏ;€ȯ

Pruébalo en línea!

Utiliza una técnica similar a mi respuesta de Japt y, por lo tanto, se ejecuta muy rápidamente en casos de prueba más grandes.

Cómo funciona

ÆḌ߀Ẏ;€ȯ    Main link. Argument: n (integer)
ÆḌ          Yield the proper divisors of n.
       ȯ    If there are no divisors, return n. Only happens when n is 1.
  ߀        Otherwise, run each divisor through this link again. Yields
            a list of lists of Gozinta chains.
    Ẏ       Tighten; bring each chain into the main list.
     ;€     Append n to each chain.

Mathematica, 77 bytes

FindPath[Graph@Cases[Divisors@#~Subsets~{2},{m_,n_}/;m∣n:>m->n],1,#,#,All]&

Forma a Graphdonde los vértices son los Divisorsde la entrada #, y los bordes representan la divisibilidad adecuada, luego encuentra Allcaminos desde el vértice 1hasta el vértice #.

Jalea , 12 bytes

ŒPµḍ2\×ISµÐṀ

Un enlace monádico que acepta un entero y devuelve una lista de listas de enteros.

Pruébalo en línea!

¿Cómo?

Queremos todas las listas ordenadas de enteros únicos entre uno y N, de modo que el primero sea uno, el último sea N y todos los pares se dividan. El código logra este filtro al verificar que los criterios de división por pares se satisfacen sobre el conjunto de potencia del rango en cuestión, pero solo selecciona aquellos con sumas máximas de diferencia incremental (los que comienzan con uno y terminan con N tendrán una suma de diferencias incrementales de N-1, otros tendrán menos).

ŒPµḍ2\×ISµÐṀ - Link: number N
ŒP           - power-set (implicit range of input) = [[1],[2],...,[N],[1,2],[1,3],...,[1,N],[1,2,3],...]
          ÐṀ - filter keep those for which the result of the link to the left is maximal:
  µ      µ   - (a monadic chain)
    2\       -   pairwise overlapping reduce with:
   ḍ         -     divides? (1 if so, 0 otherwise)
       I     -   increments  e.g. for [1,2,4,12] -> [2-1,4-2,12-4] = [1,2,8]
      ×      -   multiply (vectorises) (no effect if all divide,
             -                          otherwise at least one gets set to 0)
        S    -   sum         e.g. for [1,2,4,12] -> 1+2+8 = 11 (=12-1)

Japt , 17 bytes

⬣ßX m+S+UR÷ª'1

¡Pruébelo en línea!

Extrañamente, generar la salida como una cadena fue mucho más fácil que generarlo como una matriz de matrices ...

Explicación

 ⬠£  ßX m+S+URà ·  ª '1
Uâq mX{ßX m+S+UR} qR ||'1   Ungolfed
                            Implicit: U = input number, R = newline, S = space
Uâ                          Find all divisors of U,
  q                           leaving out U itself.
    mX{         }           Map each divisor X to
       ßX                     The divisor chains of X (literally "run the program on X")
          m    R              with each chain mapped to
           +S+U                 the chain, plus a space, plus U.
                  qR        Join on newlines.
                     ||     If the result is empty (only happens when there are no factors, i.e. U == 1)
                       '1     return the string "1".
                            Otherwise, return the generated string.
                            Implicit: output result of last expression

Mathematica, 60 bytes

Cases[Subsets@Divisors@#,x:{1,___,#}/;Divisible@@Reverse@{x}]&

Utiliza la forma multi-arg indocumentado de Divisibledonde Divisible[n1,n2,...]vuelve Truesi n2∣n1, n3∣n2y así sucesivamente, y Falsede lo contrario. Tomamos toda Subsetsla lista de Divisorsla entrada #, luego devolvemos Casesla forma {1,___,#}tal que Divisibleda Truela Reversesecuencia d de divisores.

Haskell, 51 bytes

f 1=[[1]]
f n=[g++[n]|k<-[1..n-1],n`mod`k<1,g<-f k]

Recurrentemente encuentre cadenas de gozinta de divisores apropiados y anexe n.

Pruébalo en línea!

Haskell (Lambdabot), 92 85 bytes

x#y|x==y=[[x]]|1>0=(guard(mod x y<1)>>(y:).map(y*)<$>div x y#2)++x#(y+1)
map(1:).(#2)

Necesita Lambdabot Haskell ya que guardrequiereControl.Monad ser importado. La función principal es una función anónima, que me han dicho que está permitida y elimina un par de bytes.

Gracias a Laikoni por guardar siete bytes.

Explicación:

Las mónadas son muy útiles.

x # y

Esta es nuestra función recursiva que hace todo el trabajo real. xes el número sobre el que estamos acumulando (el producto de los divisores que permanecen en el valor), y yes el siguiente número en el que deberíamos intentar dividirlo.

 | x == y = [[x]]

Si xes igual, yentonces hemos terminado de recurrir. Solo xúselo como el final de la cadena actual de gozinta y devuélvalo.

 | 1 > 0 =

Haskell golf-ism para "Verdadero". Es decir, este es el caso predeterminado.

(guard (mod x y < 1) >>

Estamos operando dentro de la lista mónada ahora. Dentro de la lista de mónadas, tenemos la capacidad de tomar múltiples decisiones al mismo tiempo. Esto es muy útil cuando se encuentra "todo lo posible" de algo por agotamiento. La guarddeclaración dice "solo considere la siguiente opción si una condición es verdadera". En este caso, solo considere la siguiente opción si se ydivide x.

(y:) . map (y *) <$> div x y#2)

Si se ydivide x, tenemos la opción de agregar ya la cadena de gozinta. En este caso, llame recursivamente (#), comenzando de nuevo y = 2con xigual a x / y, ya que queremos "factorizar" lo que yacabamos de agregar a la cadena. Luego, cualquiera que sea el resultado de esta llamada recursiva, multiplique sus valores por los yque acabamos de factorizar y yagreguemos oficialmente a la cadena de gozinta.

++

Considere la siguiente opción también. Esto simplemente agrega las dos listas juntas, pero monádicamente podemos pensar que dice "elegir entre hacer esto o lo otro".

x # (y + 1)

La otra opción es simplemente continuar recurriendo y no usar el valor y. Si yno se divide x, esta es la única opción. Si se ydivide, xentonces se tomará esta opción, así como la otra opción, y los resultados se combinarán.

map (1 :) . (# 2)

Esta es la función principal de gozinta. Comienza la recursión llamando (#)con su argumento. A 1se antepone a cada cadena de gozinta, porque la (#)función nunca los pone en las cadenas.

Haskell, 107 100 95 bytes

f n=until(all(<2).map head)(>>=h)[[n]]
h l@(x:_)|x<2=[l]|1<2=map(:l)$filter((<1).mod x)[1..x-1]

Tal vez hay una mejor condición de terminación (probé algo como

f n=i[[n]]
i x|g x==x=x|1<2=i$g x
g=(>>=h)

pero es más largo) La comprobación de 1parece prudente ya que la limpieza de repeticiones 1o duplicados ( nubno en Prelude) es más bytes.

Pruébalo en línea.

JavaScript (Firefox 30-57), 73 bytes

f=n=>n>1?[for(i of Array(n).keys())if(n%i<1)for(j of f(i))[...j,n]]:[[1]]

Convenientemente n%0<1es falso.

Jalea , 17 bytes

ḊṖŒP1ppWF€ḍ2\Ạ$Ðf

Pruébalo en línea!

Mathematica, 104 bytes

(S=Select)[Rest@S[Subsets@Divisors[t=#],FreeQ[#∣#2&@@@Partition[#,2,1],1>2]&],First@#==1&&Last@#==t&]&

Mathematica, 72 bytes

Cases[Subsets@Divisors@#,{1,___,#}?(And@@BlockMap[#∣#2&@@#&,#,2,1]&)]&

Explicación

Divisors@#

Encuentra todos los divisores de la entrada.

Subsets@ ...

Genere todos los subconjuntos de esa lista.

Cases[ ... ]

Elija todos los casos que coincidan con el patrón ...

{1,___,#}

Comenzando con 1 y terminando con <input>...

?( ... )

y satisface la condición ...

And@@BlockMap[#∣#2&@@#&,#,2,1]&

El elemento izquierdo divide el elemento derecho para todas las 2 particiones de la lista, desplazamiento 1.

TI-BASIC, 76 bytes

Input N
1→L1(1
Repeat Ans=2
While Ans<N
2Ans→L1(1+dim(L1
End
If Ans=N:Disp L1
dim(L1)-1→dim(L1
L1(Ans)+L1(Ans-(Ans>1→L1(Ans
End

Explicación

Input N                       Prompt user for N.
1→L1(1                        Initialize L1 to {1}, and also set Ans to 1.

Repeat Ans=2                  Loop until Ans is 2.
                              At this point in the loop, Ans holds the
                              last element of L1.

While Ans<N                   While the last element is less than N,
2Ans→L1(1+dim(L1              extend the list with twice that value.
End

If Ans=N:Disp L1              If the last element is N, display the list.

dim(L1)-1→dim(L1              Remove the last element, and place the new
                              list size in Ans.

L1(Ans)+L1(Ans-(Ans>1→L1(Ans  Add the second-to-last element to the last
                              element, thereby advancing to the next
                              multiple of the second-to-last element.
                              Avoid erroring when only one element remains
                              by adding the last element to itself.

End                           When the 1 is added to itself, stop looping.

Podría guardar otros 5 bytes si se permite salir con un error en lugar de con gracia, eliminando la verificación Ans> 1 y la condición del bucle. Pero no estoy seguro de que eso esté permitido.

Mathematica 86 77 Bytes

Select[Subsets@Divisors@#~Cases~{1,___,#},And@@BlockMap[#∣#2&@@#&,#,2,1]&]&

Fuerza bruta por la definición.

Deseando que hubiera una forma más corta de hacer una comparación de elementos secuenciales por pares de una lista.

Gracias a @Jenny_mathy y @JungHwanMin por las sugerencias para guardar 9 bytes

Casco , 17 16 bytes

-1 byte, gracias a Zgarb

foEẊ¦m`Je1⁰Ṗthḣ⁰

Pruébalo en línea!

PHP 147 141

Editado para eliminar una prueba redundante

function g($i){$r=[[1]];for($j=2;$j<=$i;$j++)foreach($r as$c)if($j%end($c)<1&&$c[]=$j)$r[]=$c;foreach($r as$c)end($c)<$i?0:$R[]=$c;return$R;}

Explicado:

function g($i) {

15 caracteres de repetitivo :(

    $r = [[1]];

Inicie el conjunto de resultados a [[1]]medida que cada cadena comience con 1. Esto también lleva a admitir 1 como entrada.

    for ($j = 2; $j <= $i; $j++) {
        foreach ($r as $c) {
            if ($j % end($c) < 1) {
                $c[] = $j;
                $r[] = $c;
            }
        }
    }

Para cada número del 2 al $i, vamos a extender cada cadena en nuestro conjunto por el número actual si va a ser , luego, agrega la cadena extendida a nuestro conjunto de resultados.

    foreach ($r as $c) {
        end($c) < $i ? 0 : $R[] = $c;
    }

Filtra nuestras cadenas intermedias que no llegaron a $i

    return $R;
}

10 caracteres de repetitivo :(

Mathematica

f[1] = {{1}};
f[n_] := f[n] = Append[n] /@ Apply[Join, Map[f, Most@Divisors@n]]

La respuesta se almacena en caché para llamadas adicionales.