Cantor generalizado establece longitudes de segmento

17

Problema

Definamos un conjunto de Cantor generalizado eliminando iterativamente algunos segmentos de longitud racional del medio de todos los intervalos que aún no se han eliminado, comenzando desde un único intervalo continuo.

Dadas las longitudes relativas de los segmentos a eliminar o no, y el número de iteraciones a realizar, el problema es escribir un programa o función que genere las longitudes relativas de los segmentos que se han eliminado o no después de las niteraciones.

Ejemplo 3,1,1,1,2

Ejemplo: eliminar iterativamente el cuarto y sexto octavo

Entrada:

n - número de iteraciones, indexadas a partir de 0 o 1

l- lista de longitudes de segmento como enteros positivos con gcd(l)=1longitud impar, que representan las longitudes relativas de las partes que permanecen como están o se eliminan, comenzando desde un segmento que no se elimina. Como la longitud de la lista es impar, el primer y el último segmento nunca se eliminan. Por ejemplo, para el conjunto regular de Cantor, esto sería [1,1,1] para un tercio que se queda, un tercio que se elimina y nuevamente un tercio que no.

Salida:

Lista de números enteros o, gcd(o)=1, de longitudes de segmento relativas en el nº iteración cuando los segmentos que no se eliminaron en la iteración anterior se sustituyen por una copia reducida de la lista l. La primera iteración es justa [1]. Puede usar cualquier método de salida inequívoco , incluso unario.

Ejemplos

n=0, l=[3,1,1,1,2] →                 [1]
n=1, l=[3,1,1,1,2] →     [3,    1,    1,    1,    2]
n=2, l=[3,1,1,1,2] → [9,3,3,3,6,8,3,1,1,1,2,8,6,2,2,2,4]

n=3, l=[5,2,3]     → [125,50,75,100,75,30,45,200,75,30,45,60,45,18,27]
n=3, l=[1,1,1]     → [1,1,1,3,1,1,1,9,1,1,1,3,1,1,1]

Puede asumir que la entrada es válida. Este es el , por lo que gana el programa más corto medido en bytes.

Angs
fuente
¿Sería aceptable ingresar y generar los índices de segmentos no eliminados en lugar de las longitudes? Por ejemplo, en [0, 1, 2, 4, 6, 7]lugar de [3, 1, 1, 1, 2]?
@Mnemonic no está muy lejos de ser unario, así que diría que está bien.
Angs
¿Podría agregar uno (o varios) casos de prueba para listas de entrada de tamaño par?
Kevin Cruijssen
1
@KevinCruijssen, las listas de entrada tienen un tamaño impar
Angs,

Respuestas:

6

Jalea ,  15 13  12 bytes

-2 gracias a Dennis (el uso de un Enlace en lugar de una cadena permite que el derecho sea utilizado implícitamente por ¡; No es necesario envolverlo 1en una lista debido al hecho de que Jelly imprime las listas de un elemento igual que el elemento)
-1 gracias a Erik the Outgolfer (use Ɗpara guardar el uso de la nueva línea Ç)

1×€³§JḤ$¦ẎƊ¡

Un programa completo que imprime una lista en formato Jelly ( [1]se imprime como 1)

Pruébalo en línea!

¿Cómo?

1×€³§JḤ$¦ẎƊ¡ - Main link: segmentLengths; iterations
1            - literal 1 (start with a single segment of length 1)
           ¡ - repeat...
             - ...times: implicitly use chain's right argument, iterations
          Ɗ  - ...do: last 3 links as a monad (with 1 then the previous output):
   ³         - (1) program's 3rd argument = segmentLengths
 ×€          -  1  multiply €ach (e.g. [1,2,3] ×€ [1,2,1] = [[1,4,3],[2,4,2],[3,6,3]])
        ¦    -  2  sparse application... 
       $     - (2) ...to: indices: last two links as a monad:
     J       - (2)          range of length = [1,2,3,...,numberOfLists]
      Ḥ      - (2)          double            [2,4,6,...] (note: out-of bounds are ignored by ¦)
    §        - (2) ...of: sum each (i.e. total the now split empty spaces)
         Ẏ   -  3  tighten (e.g. [[1,2,3],4,[5,6,7]] -> [1,2,3,4,5,6,7])
             - implicit print
Jonathan Allan
fuente
4

Python 2 , 120 107 104 103 100 99 89 bytes

f=lambda n,l:n and[x*y for i,x in enumerate(l)for y in[f(n-1,l),[sum(l)**~-n]][i%2]]or[1]

Pruébalo en línea!


Salvado

  • -10 bytes, gracias a Neil
TFeld
fuente
1
89 bytes
Neil
@Neil, gracias :)
TFeld
4

R , 94 bytes

f=function(n,a)"if"(n,unlist(Map(function(g,i)g(i),c(c,sum),split(m<-a%o%f(n-1,a),row(m)))),1)

Pruébalo en línea!

Kirill L.
fuente
4

Haskell , 76 58 bytes

l%0=[1]
l%n=do(x,m)<-l%(n-1)`zip`cycle[l,[sum l]];map(*x)m

Pruébalo en línea!

La función (%)toma la lista de longitudes de línea lcomo primer argumento y el número de iteraciones ncomo segunda entrada.

¡Gracias a Angs y Ørjan Johansen por -18 bytes!

Laikoni
fuente
Debería poder guardar al menos 7 bytes cambiando a una recursión ny soltándola por #completo
Angs
Independientemente de la sugerencia de @Angs, el original %se puede acortar a l%a=do(x,m)<-zip a$a>>[l,[sum l]];(*x)<$>m .
Ørjan Johansen
3

JavaScript (Firefox 42-57), 80 bytes

f=(n,l,i=0)=>n--?[for(x of l)for(y of(i^=1)?f(n,l):[eval(l.join`+`)**n])x*y]:[1]

Necesita esas versiones específicas porque utiliza tanto la comprensión de matriz como la exponenciación.

Neil
fuente
2

Java 10, 261 bytes

L->n->{if(n<1){L.clear();L.add(1);}else if(n>1){var C=new java.util.ArrayList<Integer>(L);for(int l=C.size(),i,x,t,s;n-->1;)for(i=x=0;i<L.size();){t=L.remove(i);if(i%2<1)for(;i%-~l<l;)L.add(i,C.get((i++-x)%l)*t);else{x++;s=0;for(int c:C)s+=c;L.add(i++,t*s);}}}}

Modifica la lista de entrada en lugar de devolver una nueva para guardar bytes.

Pruébalo en línea.

L->n->{                       // Method with List and integer parameters and no return-type
  if(n<1){                    //  If `n` is 0:
    L.clear();                //   Remove everything from the List
    L.add(1);}                //   And only add a single 1
                              //  Else-if `n` is 1: Leave the List as is
  else if(n>1){               //  Else-if `n` is 2 or larger:
    var C=new java.util.ArrayList<Integer>(L);
                              //   Create a copy of the input-List
    for(int l=C.size(),       //   Set `l` to the size of the input-List
        i,x,t,s;              //   Index and temp integers
        n-->1;)               //   Loop `n-1` times:
      for(i=x=0;              //    Reset `x` to 0
          i<L.size();){       //    Inner loop `i` over the input-List
        t=L.remove(i);        //     Remove the current item, saving its value in `t`
        if(i%2<1)             //     If the current iteration is even:
          for(;i%-~l<l;)      //      Loop over the copy-List
            L.add(i,C.get((i++-x)%l)*t);
                              //       And add the values multiplied by `t`
                              //       at index `i` to the List `L`
        else{                 //     Else (the current iteration is odd):
          x++;                //      Increase `x` by 1
          s=0;for(int c:C)s+=c;
                              //      Calculate the sum of the copy-List
          L.add(i++,t*s);}}}} //      Add this sum multiplied by `t`
                              //      at index `i` to the List `L`
Kevin Cruijssen
fuente
2

Jalea , 13 bytes

Ø1××S¥ƭ€³Ẏ$¡Ṗ

Pruébalo en línea!

Programa completo Salidas en 1lugar de [1]. Molesto, no funciona como ×S¥en este contexto, y ƭno funciona bien con nilads. > _ <

Erik el Outgolfer
fuente
2

K (ngn / k) , 27 bytes

{x{,/y*(#y)#x}[(y;+/y)]/,1}

Pruébalo en línea!

{ }es una función con argumentos xyy

(y;+/y)un par de yy su suma

{ }[(y;+/y)]proyección (también conocida como curry o aplicación parcial) de una función diádica con un argumento. xserá (y;+/y)y yserá el argumento cuando se aplique.

,1 lista singleton que contiene 1

x{ }[ ]/ aplicar la proyección x tiempos de

(#y)#xremodelar a la longitud del resultado actual, es decir, alternar entre el exterior yy su suma

y* multiplique cada elemento de lo anterior con el elemento correspondiente del resultado actual

,/ concatenar

ngn
fuente
1

Pyth , 20 bytes

us.e?%k2*bsQ*LbQGE]1

La entrada es una matriz de segmentos l, luego iteraciones n. Pruébelo en línea aquí , o verifique todos los casos de prueba a la vez aquí .

us.e?%k2*bsQ*LbQGE]1   Implicit, Q=1st arg (segment array), E=2nd arg (iterations)
u                E     Execute E times, with current value G...
                  ]1   ... and initial value [1]:
  .e            G        Map G, with element b and index k:
        *bsQ               Multiply b and the sum of Q {A}
            *LbQ           Multiply each value of Q by b {B}
    ?%k2                   If k is odd, yield {A}, otherwise yield {B}
 s                       Flatten the resulting nested array
Sok
fuente