Generalized Cantor set segment lengths

Question

Problem

Let's define a generalized Cantor set by iteratively deleting some rational length segments from the middle of all intervals that haven't yet been deleted, starting from a single continuous interval.

Given the relative lengths of segments to delete or not, and the number of iterations to do, the problem is to write a program or function that outputs the relative lengths of the segments that have or have not been deleted after n iterations.

Example 3,1,1,1,2

Example: Iteratively delete the 4th and 6th eighth

Input:

n – number of iterations, indexed starting from 0 or 1

l – list of segment lengths as positive integers with gcd(l)=1 and odd length, representing the relative lengths of the parts that either stay as they are or get deleted, starting from a segment that doesn't get deleted. Since the list length is odd, the first and last segments never get deleted. For example for the regular Cantor set this would be [1,1,1] for one third that stays, one third that gets deleted and again one third that doesn't.

Output:

Integer list o, gcd(o)=1, of relative segment lengths in the nth iteration when the segments that weren't deleted in the previous iteration are replaced by a scaled down copy of the list l. The first iteration is just [1]. You can use any unambiguous output method, even unary.

Examples

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]

You can assume the input is valid. This is code-golf, so the shortest program measured in bytes wins.

• user48543: Would it be acceptable to input and output the indices of non-deleted segments instead of the lengths? For instance, [0, 1, 2, 4, 6, 7] instead of [3, 1, 1, 1, 2]?
• Angs: @Mnemonic it's not too far from unary, so I'd say it's fine.
• Kevin Cruijssen: Could you add one (or multiple) test case(s) for even-sized input-lists?
• Angs: @KevinCruijssen the input lists are guaranteed to be odd-sized

Answer 1

Jelly, (削除) 15 13 (削除ここまで) 12 bytes

-2 thanks to Dennis (using a Link rather than a chain allows right to be used implicitly by ¡; No need to wrap the 1 in a list due to the fact that Jelly prints lists of one item the same as the item)
-1 thanks to Erik the Outgolfer (use Ɗ to save the newline from using Ç)

×ばつ3ドル§JḤ$¦ẎƊ¡

A full program printing a list in Jelly format (so [1] is printed as 1)

Try it online!

How?

×ばつ3ドル§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):
 3 - (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

Answer 2

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]

Try it online!

---

Saved

• -10 bytes, thanks to Neil

• Neil: 89 bytes

Answer 3

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)

Try it online!

Answer 4

Haskell, (削除) 76 (削除ここまで) 58 bytes

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

Try it online!

The function (%) takes the list of line lengths l as first argument and the number of iterations n as second input.

Thanks to Angs and Ørjan Johansen for -18 bytes!

• Angs: You should be able to save at least 7 bytes by switching to a recursion on n and dropping # altogether
• Ørjan Johansen: Independently of @Angs 's suggestion, the original % can be shortened to l%a=do(x,m)<-zip a$a>>[l,[sum l]];(*x)<$>m .

Answer 5

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]

Needs those specific versions because it uses both array comprehensions and exponentiation.

Answer 6

JavaScript (Node.js), 71 bytes

l=>f=(n,c=1,e)=>n--?''+l.map(_=>(e=!e)?f(n,c*_):eval(l.join`+`)**n*c):c

Try it online!

Answer 7

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

Modifies the input-List instead of returning a new one to save bytes.

Try it online.

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`

Answer 8

Jelly, 13 bytes

×ばつS\ƭ3ドルẎ$¡Ṗ

Try it online!

Full program. Outputs 1 instead of [1]. Annoyingly, ḋ doesn't work like ×ばつS\ in this context, and ƭ doesn't work well with nilads.>_<

Answer 9

APL (Dyalog Classic), 20 bytes

{(×ばつ⍵(+/⍵)⍴⍨≢)⍣⍺,1}

Try it online!

Answer 10

K (ngn/k), 27 bytes

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

Try it online!

{ } is a function with arguments x and y

(y;+/y) a pair of y and its sum

{ }[(y;+/y)] projection (aka currying or partial application) of a dyadic function with one argument. x will be (y;+/y) and y will be the argument when applied.

,1 singleton list containing 1

x{ }[ ]/ apply the projection x times

(#y)#x reshape to the length of the current result, i.e. alternate between the outer y and its sum

y* multiply each element of the above with the corresponding element of the current result

,/ concatenate

Answer 11

Ruby, 73 bytes

->a,l{r=[1];a.times{s=p;r=r.flat_map{|x|(s=!s)?l.map{|y|x*y}:x*l.sum}};r}

Try it online!

Answer 12

Pyth, 20 bytes

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

Input is segment array l, then iterations n. Try it online here, or verify all the test cases at once here.

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