First odd then even indices

Question

Your task is to find out how often you need to "shuffle" a given list with the following operation until you get back the original list.

start with a list:
(1 2 3 4 5 6 7 8 9) 
split it into the elements at odd and even indices
(1 3 5 7 9) (2 4 6 8)
concatenate these two list
(1 3 5 7 9 2 4 6 8)

Input: A list

Output: The number of iterations it takes until you get back the original list

Examples

(1 2 3) -> (1 3 2) -> (1 2 3)               => 2
(1 2 3 4 3 2 1) -> (1 3 3 1 2 4 2) -> ...   => 3
(1 2 3 4 5 6 7 8 9 10) -> ...               => 6
(1 2 3 4 5 6 7 8 9 10 11) -> ...            => 10
"abab" -> "aabb" -> "abab"                  => 2
"Hello, World!" -> "Hlo ol!el,Wrd" -> ...   => 12
(1 0 1 1 0 0 0 1 1 1) -> ...                => 6
(1 0 0 1 1 1 0 0 0 0 1) -> ...              => 10
(1 1 1 1 1 1 1) -> (1 1 1 1 1 1 1)          => 1

Rules

• You can use lists of any type (that supports at least two distinct values)
• You can assume the the list has at least two elements
• The odd/even indices are determined using 1-based indexing
• You have to apply the operation at least once
• If your language has a built-in for finding fixed points consider adding a non-builtin solution as well
• This is code-golf the shortest solution (per language) wins

Answer 1

K (ngn/k), 12 bytes

#{x@<2!!#x}\

Try it online!

{ ... }\ Iterate until reaching the first value again (or a fixed point). Collect intermediate values.
2!!#x 2 mod range of length x. Sequence of alternating 0s and 1s the same length as x.
x@< Grade up, then index into x. Sorts x by that sequence.

# Length. Counts the number of intermediate results.

Answer 2

Thunno 2 L, 4 bytes

µ¥zS

Try it online! or verify all test cases

µ¥zḞ

Try it online! or verify all test cases

µ¥^ḥ

Try it online! or verify all test cases

---

Don't worry, the stack languages with single-byte uninterleave operators are going to be even shorter :P

lol

Explanation

      # Implicit input

µ¥    # Collect while unique:

  z   #  Uninterleave into two pieces
      #   [1,2,3,4,5,6]  ->  [[1,3,5],[2,4,6]]
   S  #  Then flatten the nested list
      #   [[1,3,5],[2,4,6]]  ->  [1,3,5,2,4,6]
   Ḟ  #  Alternative flatten built-in
      #   [[1,3,5],[2,4,6]]  ->  [1,3,5,2,4,6]

  ^   #  Or, uninterleave and push separately
      #   [1,2,3,4,5,6]  ->  [1,3,5] [2,4,6]
   ḥ  #  Then concatenate the two lists
      #   [1,3,5] [2,4,6]  ->  [1,3,5,2,4,6]

      # Finally, the L flag takes the length
      # Implicit output

Answer 3

J, ²⁶ 24 bytes

i.~_:0}(\:2|#\)^:(3<@^#)

Try it online!

Accepts numeric lists

The maximum number of iterations until we return to the input is bounded by Landau's function \$g(n)\$, and it can be shown that:

$$ {\displaystyle g(n)\leq e^{n/e}} $$

For golf reasons, I simply round that to:

$$ {\displaystyle g(n)\leq 3^{n}} $$

and iterate that many times. Note I could trade bytes for efficiency here and iterate until I see the input again, but this approach was shorter.

• (\:2|#\) Apply the needed permutation -- equivalent to sorting down by 1 0 1 0...
• ^:(3<@^#) Do that \$3^n\$ times, saving results
• _:0} Convert the first item on the list, which is the input itself, to infinity, so that match will be skipped.
• i.~ Index of the input within that list.

Answer 4

Jelly, 6 bytes

ŒœẎ$ƬL

Try it online!

Don't worry, the stack languages with single-byte uninterleave operators are going to be even shorter :P

    Ƭ     Repeat while unique, collecting all results:
Œœ        Split into odd and even-indexed elements,
  Ẏ$      and concatenate.
     L    How many results are there?

Answer 5

05AB1E, 8 bytes

vDÅ≠})Ùg

Try it online or verify all test cases (the test suite uses the faster alternative ι˜ instead of Å≠).

Explanation:

Although 05AB1E has an unshuffle builtin Å≠ (even though ι˜ does the same and is faster..), it unfortunately lacks a "Repeat until unique" builtin..

v     # Loop the (implicit) input-length amount of times:
 D    #  Duplicate the current list
      #  (which will be the implicit input-list in the first iteration)
  Å≠  #  Unshuffle it
})    # After the loop: wrap all lists on the stack into a list
  Ù   # Uniquify this list of lists
   g  # Pop and push its length
      # (which is output implicitly as result)

  ι   #  Uninterleave it into a pair of lists
   ˜  #  Flatten it to a single list

Answer 6

Google Sheets, 107 bytes

=let(d,torow(A:A,3),_,lambda(_,a,n,sort(let(b,torow(wrapcols(a,2),3),if(and(b=d),n,_(_,b,1+n))))),_(_,d,1))

Put the input in cells A1:A and the formula in B1.

The formula is self-contained. Uses singularize(wrap()) like the Excel answer but does not depend on named functions or named ranges.

Try it.

Answer 7

Python, 65 bytes

lambda s,j=1:j*((t:=s[:len(s)-1|1])==(t*2**j)[::2**j])or f(s,j+1)

Attempt This Online!

How?

This is based on the observation that in zero-based indexing the reshuffle can be written as n -> 2n mod N where N is the largest odd number not greater than the length of the input. (If the length is even the last point is a fixed point, so it can be ignored.)

Answer 8

Nekomata + -n, 6 bytes

ᶦ{ĭ,ᵖ≠

Attempt This Online!

Nekomata has a single-byte uninterleave operator, but still can't beat Jelly, because it doesn't have a "repeat while unique" operator.

ᶦ{ĭ,ᵖ≠
ᶦ{          Repeat until failure:
  ĭ             Uniterleave
   ,            Join
    ᵖ≠          Check if the result is unequal to the input

-n counts the number of iterations.

Answer 9

Excel, 93 bytes

Define:

a as =$A$1# (7 bytes)

z as =LAMBDA(p,q,LET(x,TOCOL(WRAPROWS(p,2),2,1),y,q+1,IF(SUM(N(x<>a))=0,y,z(x,y)))) (79 bytes)

Within the worksheet: =z(a,0) (7 bytes)

$A$1# is a spilled, vertical range comprising the list entries.

Answer 10

R, 70 bytes

f=\(x,l=0,y=c(x[!0:1],x[!1:0]),`-`=list)`if`(-y%in%l,0,1+f(y,c(l,-y)))

Attempt This Online!

Answer 11

Ruby, 55 bytes

->l{k=*l;1.step.find{w=-2;l==k=k.map{k[w+=2]||k[w=1]}}}

Try it online!

Answer 12

Vyxal l, 31 bits^v2, 3.875 bytes

yJ)↲

Try it Online!

the stack languages with single-byte uninterleave operators are going to be even shorter

~ some jelly answer, probably

Answer 13

R, 54 52 51 bytes

Edit: -3 bytes thanks to @Dominic van Essen.

\(x,y=x){while(sd((y[]=matrix(y,2,,T))-x))T=T+1;+T}

Attempt This Online!

Answer 14

Charcoal, 27 bytes

⊞υθＷ‹№υθ²⊞υ⭆²Φ§υ±¹﹪⁺κν²Ｉ⊖Ｌυ

Try it online! Link is to verbose version of code. Only works on strings. Explanation:

⊞υθ

Push the string to the predefined empty list.

Ｗ‹№υθ²

Repeat until a second copy of the string is found.

⊞υ⭆²Φ§υ±¹﹪⁺κν²

Shuffle the most recent string and push it to the list.

Ｉ⊖Ｌυ

Output the number of shuffles taken.

28 bytes to work on strings or lists:

⊞υθＷ‹№υθ²⊞υΣＥ²Φ§υ±¹﹪⁺κν²Ｉ⊖Ｌυ

Attempt This Online! Link is to verbose version of code.

Answer 15

sclin, 45 bytes

=$a $a"2/` tpose flat"itr1dp"$a !=`"tk* len1+

Try it here! Takes a list.

For testing purposes:

[1 2 3 4 5 6 7 8 9 10 11] ;
=$a $a"2/` tpose flat"itr1dp"$a !=`"tk* len1+

NOTE: for string-based inputs, use e.g. ["a" "b" "a" "b"].

Explanation

Prettified code:

=$a $a.
( 2/` tpose flat ) itr 1dp ( $a !=` ) tk* len 1+

• =$a $a Input list a
• (...) itr generate infinite list from successive modifications of a...
  • 2/` tpose flat chunk into pairs, transpose, flatten
• 1dp drop first item to prevent tk* from exiting early
• ( $a !=` ) tk* take while not equal to a
• len 1+ length + 1

Answer 16

JavaScript (ES6), 64 bytes

Expects a list of positive integers.

a=>(g=a=>(g[a]^=i=-2)&&1+g(a.map(_=>a[!a[i+=2]|i%a.length])))(a)

Try it online!

How?

We can apply the shuffle by doing:

a.map((_, i) => a[!a[i * 2] | i * 2 % a.length])

This code first collects all values at even (0-based) indices. When a[i * 2] is not defined anymore, it starts collecting values at odd indices.

For golfing reasons, we rather start with \$i=-2\$ and do:

a.map(_ => a[!a[i += 2] | i % a.length])

We stop as soon as the same array has been encountered twice and return the number of iterations.

Answer 17

Arturo, 49 bytes

$->a[1x:a while[i:0arrange'x=>[i%2'i+1]x<>a][1+]]

Try it!

$->a[                         ; a function taking an input a
    1                         ; push 1 -- this is our output (count)
    x:a                       ; assign a to x
    while[                    ; while...
        i:0                   ; assign 0 to i
        arrange'x=>[i%2'i+1]  ; sort x by its indices' parities
        x<>a                  ; x doesn't equal a...
    ]                         ; end while predicate
    [1+]                      ; ...then increment the output
]                             ; end function

Answer 18

Haskell, 77 bytes

o(x:s)=x:e s
o _=[]
e=o.drop 1
a!b|a==b=1|0<1=1+a!(o b++e b)
f a=a!(o a++e a)

Try it online!