Longueurs de segment d'ensemble Cantor généralisées

17

Problème

Définissons un ensemble de Cantor généralisé en supprimant de manière itérative certains segments de longueur rationnelle du milieu de tous les intervalles qui n'ont pas encore été supprimés, à partir d'un seul intervalle continu.

Compte tenu des longueurs relatives des segments à supprimer ou non, et du nombre d'itérations à effectuer, le problème est d'écrire un programme ou une fonction qui génère les longueurs relatives des segments qui ont ou non été supprimés après les nitérations.

Exemple 3,1,1,1,2

Exemple: supprimer de manière itérative les 4e et 6e huitième

Contribution:

n - nombre d'itérations, indexées à partir de 0 ou 1

l- liste des longueurs de segments sous forme d'entiers positifs avec gcd(l)=1et longueur impaire, représentant les longueurs relatives des parties qui restent telles quelles ou sont supprimées, en commençant par un segment qui n'est pas supprimé. Étant donné que la longueur de la liste est impaire, les premier et dernier segments ne sont jamais supprimés. Par exemple, pour l'ensemble Cantor normal, ce serait [1,1,1] pour un tiers qui reste, un tiers qui est supprimé et encore un tiers qui ne le reste pas.

Production:

Liste entier o, gcd(o)=1, de longueurs de segment par rapport à la nième itération lorsque les segments qui ne sont pas supprimés dans l'itération précédente , sont remplacés par une copie réduite de la liste l. La première itération est juste [1]. Vous pouvez utiliser n'importe quelle méthode de sortie sans ambiguïté , même unaire.

Exemples

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]

Vous pouvez supposer que l'entrée est valide. C'est le , donc le programme le plus court mesuré en octets l'emporte.

Angs
la source
Serait-il acceptable d'entrer et de sortir les indices des segments non supprimés au lieu des longueurs? Par exemple, [0, 1, 2, 4, 6, 7]au lieu de [3, 1, 1, 1, 2]?
@Mnemonic ce n'est pas loin d'être unaire, donc je dirais que ça va.
Angs
Pourriez-vous ajouter un (ou plusieurs) test (s) pour des listes d'entrée de taille égale?
Kevin Cruijssen
1
@KevinCruijssen les listes d'entrées sont garanties de taille impaire
Angs

Réponses:

6

Gelée ,  15 13  12 octets

-2 merci à Dennis (utiliser un lien plutôt qu'une chaîne permet d'utiliser le droit implicitement par ¡; pas besoin d'envelopper le 1dans une liste car Jelly imprime les listes d'un article de la même manière que l'article)
-1 merci à Erik the Outgolfer (à utiliser Ɗpour éviter l' utilisation de la nouvelle ligne Ç)

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

Un programme complet imprimant une liste au format Jelly (donc [1]est imprimé comme 1)

Essayez-le en ligne!

Comment?

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
la source
4

Python 2 , 120 107 104 103 100 99 89 octets

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]

Essayez-le en ligne!


Enregistré

  • -10 octets, merci à Neil
TFeld
la source
1
89 octets
Neil
@Neil, merci :)
TFeld
4

R , 94 octets

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)

Essayez-le en ligne!

Kirill L.
la source
4

Haskell , 76 58 octets

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

Essayez-le en ligne!

La fonction (%)prend la liste des longueurs de ligne lcomme premier argument et le nombre d'itérations ncomme deuxième entrée.

Merci à Angs et Ørjan Johansen pour -18 octets!

Laikoni
la source
Vous devriez être en mesure d'économiser au moins 7 octets en passant à une récursivité net #en
supprimant
Indépendamment de la suggestion de @Angs, l'original %peut être raccourci l%a=do(x,m)<-zip a$a>>[l,[sum l]];(*x)<$>m .
Ørjan Johansen
3

JavaScript (Firefox 42-57), 80 octets

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]

A besoin de ces versions spécifiques car il utilise à la fois les compréhensions de tableaux et l'exponentiation.

Neil
la source
2

Java 10, 261 octets

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

Modifie la liste d'entrée au lieu d'en renvoyer une nouvelle pour enregistrer les octets.

Essayez-le en ligne.

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
la source
2

Gelée , 13 octets

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

Essayez-le en ligne!

Programme complet. Sorties 1au lieu de [1]. Chose ennuyeuse, ne fonctionne pas comme ×S¥dans ce contexte et ƭne fonctionne pas bien avec les nilades. > _ <

Erik le Outgolfer
la source
2

K (ngn / k) , 27 octets

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

Essayez-le en ligne!

{ }est une fonction avec des arguments xety

(y;+/y)une paire de yet sa somme

{ }[(y;+/y)]projection (aka currying ou application partielle) d'une fonction dyadique avec un argument. xsera (y;+/y)et ysera l'argument lorsqu'il sera appliqué.

,1 liste singleton contenant 1

x{ }[ ]/appliquer les xtemps de projection

(#y)#xremodeler à la longueur du résultat actuel, c'est-à-dire alterner entre l'extérieur yet sa somme

y* multipliez chaque élément de ce qui précède par l'élément correspondant du résultat actuel

,/ enchaîner

ngn
la source
1

Pyth , 20 octets

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

L'entrée est un tableau de segments l, puis des itérations n. Essayez-le en ligne ici ou vérifiez tous les cas de test en même temps ici .

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
la source