Обобщенная длина сегмента Кантора

17

проблема

Давайте определим обобщенный набор Кантора путем итеративного удаления некоторых сегментов рациональной длины из середины всех интервалов, которые еще не были удалены, начиная с одного непрерывного интервала.

Учитывая относительную длину сегментов, которые нужно удалить или нет, и количество итераций, которые нужно сделать, проблема состоит в том, чтобы написать программу или функцию, которая выводит относительную длину сегментов, которые были или не были удалены после nитераций.

Пример 3,1,1,1,2

Пример: итеративно удалить 4-е и 6-е восьмое

Входные данные:

n - число итераций, индексируется начиная с 0 или 1

l- список длин сегментов в виде положительных целых чисел с gcd(l)=1нечетной длиной, представляющих относительную длину частей, которые либо остаются такими, какие они есть, либо удаляются, начиная с сегмента, который не удаляется. Поскольку длина списка нечетная, первый и последний сегменты никогда не удаляются. Например, для обычного набора Кантора это будет [1,1,1] для одной трети, которая остается, одна треть, которая удаляется, и снова одна треть, которая не удаляется.

Выход:

Целочисленный список o, gcd(o)=1относительной длины сегментов в nитерации, когда сегменты, которые не были удалены в предыдущей итерации, заменены уменьшенной копией списка l. Первая итерация просто [1]. Вы можете использовать любой однозначный метод вывода , даже унарный.

Примеры

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]

Вы можете предположить, что ввод действителен. Это код-гольф , поэтому выигрывает самая короткая программа, измеряемая в байтах.

code-golf sequence fractal recursion Angs
источник
Будет ли приемлемым вводить и выводить индексы не удаленных сегментов вместо длин? Например, [0, 1, 2, 4, 6, 7]вместо [3, 1, 1, 1, 2]?
@ Мнемоник, это не слишком далеко от унарного, так что я бы сказал, что все в порядке.
Ангс
Не могли бы вы добавить один (или несколько) тестовых примеров для списков ввода четного размера?
Кевин Круйссен
1
@KevinCruijssen входные списки гарантированно нечетного размера
Angs

Ответы:

6

Желе ,  15 13  12 байт

-2 благодаря Деннису (использование ссылки, а не цепочки позволяет неявно использовать право ¡; нет необходимости заключать 1в список из-за того, что Jelly печатает списки из одного элемента так же, как элемент)
-1 благодаря Эрик Outgolfer (используйте, Ɗчтобы сохранить новую строку от использования Ç)

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

Полная программа печати списка в формате Jelly (поэтому [1]печатается как 1)

Попробуйте онлайн!

Как?

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
Джонатан Аллан
источник
4

Haskell , 76 58 байт

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

Попробуйте онлайн!

Функция (%)принимает список длин строк в lкачестве первого аргумента и количество итераций в nкачестве второго ввода.

Спасибо Энгсу и Орджану Йохансену за -18 байт!

Laikoni
источник
Вы должны быть в состоянии сэкономить не менее 7 байтов, переключившись на рекурсию nи #полностью сбросив ее
Angs
Независимо от предложения @Angs, оригинал %может быть сокращен до l%a=do(x,m)<-zip a$a>>[l,[sum l]];(*x)<$>m .
Орджан Йохансен
3

JavaScript (Firefox 42-57), 80 байт

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]

Нуждаются в этих конкретных версиях, потому что он использует как массивы, так и возведения в степень.

Нил
источник
2

Java 10, 261 байт

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);}}}}

Изменяет input-List вместо того, чтобы возвращать новый для сохранения байтов.

Попробуйте онлайн.

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`
Кевин Круйссен
источник
2

Желе , 13 байт

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

Попробуйте онлайн!

Полная программа. Выходы 1вместо [1]. Раздражает, ḋне работает, как ×S¥в этом контексте, и ƭне работает с nilads. > _ <

Эрик Outgolfer
источник
2

К (нгн / к) , 27 байтов

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

Попробуйте онлайн!

{ }это функция с аргументами xиy

(y;+/y)пара yи ее сумма

{ }[(y;+/y)]проекция (карри или частичное применение) диадической функции с одним аргументом. xбудет (y;+/y)и yбудет аргументом при применении.

,1 синглтон список, содержащий 1

x{ }[ ]/применять проекционные xраз

(#y)#xизменить на длину текущего результата, т.е. чередовать между внешним yи его суммой

y* умножьте каждый элемент вышеупомянутого на соответствующий элемент текущего результата

,/ конкатенация

СПП
источник
1

Pyth , 20 байтов

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

Вводом является массив сегментов l, затем итерации n. Попробуйте онлайн здесь или проверьте все тестовые примеры сразу здесь .

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
источник