Generalisierte Cantor-Segmentlängen

17

Problem

Definieren wir einen verallgemeinerten Cantor-Satz, indem wir iterativ einige Segmente mit rationaler Länge aus der Mitte aller Intervalle löschen, die noch nicht gelöscht wurden, beginnend mit einem einzelnen fortlaufenden Intervall.

Angesichts der relativen Länge der zu löschenden oder nicht zu löschenden Segmente und der Anzahl der auszuführenden Iterationen besteht das Problem darin, ein Programm oder eine Funktion zu schreiben , die die relativen Längen der Segmente ausgibt, die nach nIterationen gelöscht wurden oder nicht .

Beispiel 3,1,1,1,2

Beispiel: Löschen Sie iterativ die 4. und 6. Achtel

Eingang:

n - Anzahl der Iterationen, indiziert ab 0 oder 1

l- Liste der Segmentlängen als positive Ganzzahlen mit gcd(l)=1und ungerade Länge, die die relativen Längen der Teile darstellen, die entweder unverändert bleiben oder gelöscht werden, beginnend mit einem Segment, das nicht gelöscht wird. Da die Listenlänge ungerade ist, werden das erste und das letzte Segment niemals gelöscht. Für das reguläre Cantor-Set wäre dies beispielsweise [1,1,1] für ein Drittel, das verbleibt, ein Drittel, das gelöscht wird, und ein weiteres Drittel, das nicht gelöscht wird.

Ausgabe:

Integer - Liste o, gcd(o)=1aus relativen Segmentlängen in der nten Iteration , wenn die Segmente , die nicht in der vorherige Iteration gelöscht wurden , werden durch eine verkleinerte Kopie der Liste ersetzt l. Die erste Iteration ist gerecht [1]. Sie können jede eindeutige , auch unäre Ausgabemethode verwenden.

Beispiele

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]

Sie können davon ausgehen, dass die Eingabe gültig ist. Das ist , also gewinnt das kürzeste in Bytes gemessene Programm.

Angs
quelle
Wäre es akzeptabel, die Indizes nicht gelöschter Segmente anstelle der Längen einzugeben und auszugeben? Zum Beispiel [0, 1, 2, 4, 6, 7]anstelle von [3, 1, 1, 1, 2]?
@Mnemonic Es ist nicht allzu weit von Unary entfernt, also würde ich sagen, dass es in Ordnung ist.
Angs
Könnten Sie einen (oder mehrere) Testfälle für Eingabelisten mit gerader Größe hinzufügen?
Kevin Cruijssen
1
@ KevinCruijssen die Eingabe-Listen sind garantiert ungerade Größe
Angs

Antworten:

6

Jelly ,  15 13  12 Bytes

-2 dank Dennis (die Verwendung eines Links anstelle einer Kette ermöglicht die implizite Verwendung des Rechtes durch ¡; Es ist nicht erforderlich, das 1in eine Liste einzufügen, da Jelly Listen mit einem Element druckt, das mit dem Element identisch ist)
-1 dank Dennis Erik the Outgolfer (verwenden Sie Ɗ, um die Newline vor der Verwendung zu schützen Ç)

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

Ein vollständiges Programm, das eine Liste im Jelly-Format [1]druckt (so wird gedruckt als 1)

Probieren Sie es online!

Wie?

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
quelle
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]

Probieren Sie es online!


Gerettet

  • -10 Bytes, danke an Neil
TFeld
quelle
1
89 Bytes
Neil
@ Neil, danke :)
TFeld
4

Haskell , 76-58 Bytes

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

Probieren Sie es online!

Die Funktion verwendet (%)die Liste der Zeilenlängen lals erstes Argument und die Anzahl der Iterationen nals zweite Eingabe.

Vielen Dank an Angs und Ørjan Johansen für -18 Bytes!

Laikoni
quelle
Sie sollten in der Lage sein, mindestens 7 Bytes zu speichern, indem Sie auf eine Rekursion umschalten nund diese #vollständig
löschen
Unabhängig von @Angs Vorschlag kann das Original %auf gekürzt werden l%a=do(x,m)<-zip a$a>>[l,[sum l]];(*x)<$>m .
Ørjan Johansen
3

JavaScript (Firefox 42-57), 80 Byte

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]

Benötigt diese spezifischen Versionen, da sowohl Array-Verständnis als auch Exponentiation verwendet werden.

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

Ändert die Eingabeliste, anstatt eine neue zurückzugeben, um Bytes zu sparen.

Probieren Sie es online aus.

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
quelle
2

Jelly , 13 Bytes

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

Probieren Sie es online!

Volles Programm. Ausgänge 1statt [1]. Ärgerlicherweise funktioniert das nicht ×S¥in diesem Kontext und ƭfunktioniert nicht gut mit Niladen. > _ <

Erik der Outgolfer
quelle
2

K (ngn / k) , 27 Bytes

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

Probieren Sie es online!

{ }ist eine Funktion mit Argumenten xundy

(y;+/y)ein Paar von yund seine Summe

{ }[(y;+/y)]Projektion (auch Currying oder Teilapplikation genannt) einer dyadischen Funktion mit einem Argument. xwird (y;+/y)und ywird das Argument sein, wenn angewendet.

,1 Singleton-Liste mit 1

x{ }[ ]/gelten die xProjektionszeiten

(#y)#xVerändern Sie die Form auf die Länge des aktuellen Ergebnisses, dh wechseln Sie zwischen dem Äußeren yund seiner Summe

y* Multiplizieren Sie jedes der oben genannten Elemente mit dem entsprechenden Element des aktuellen Ergebnisses

,/ verketten

ngn
quelle
1

Pyth , 20 Bytes

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

Die Eingabe erfolgt über ein Segmentarray lund anschließend über Iterationen n. Versuchen Sie es online hier oder überprüfen alle Testfälle auf einmal hier .

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
quelle