This is an explanation of my answer to the code golf question "Algorithmic Braiding - for mother's day". The problem asks this:
Your task is to create a program that, when given a number of strands and number of iterations of a braid, will tell where each strand goes.
We'll call the number of strands N and the number of iterations I. Let's start by looking at some simple outputs. The classic example is 3 strands:
1 2 3
\ iteration 1
2 1 3
/ iteration 2
2 3 1
\ iteration 3
3 2 1
That's interesting - after N iterations, we've exactly reversed the order! (This makes sense because we've now touched all N strands, and the pattern involves moving the outside to the middle, then slowly pushing them back out).
Next is a sanity check with N=5 and N=7. I've labelled each column with a letter to avoid confusing too many numbers.
A B C D E A B C D E F G
1 2 3 4 5 1 2 3 4 5 6 7
2 3 1 4 5 2 3 4 1 5 6 7
2 3 5 1 4 2 3 4 7 1 5 6
3 5 2 1 4 3 4 7 2 1 5 6
3 5 4 2 1 3 4 7 6 2 1 5
5 4 3 2 1 4 7 6 3 2 1 5
5 4 1 3 2 4 7 6 5 3 2 1
4 1 5 3 2 7 6 5 4 3 2 1
4 1 2 5 3 7 6 5 1 4 3 2
1 2 4 5 3 6 5 1 7 4 3 2
1 2 3 4 5 6 5 1 2 7 4 3
5 1 2 6 7 4 3
5 1 2 3 6 7 4
1 2 3 5 6 7 4
1 2 3 4 5 6 7
Ok so we've at least confirmed that after 2*N iterations, the cycle will repeat. Sanity checked. But another very interesting pattern has appeared! Looking at each column (ignore the middle one for a minute), we see this pattern:
(N=3) 1 1 2 2 3 3 [repeat]
(N=5) 1 1 2 2 3 3 5 5 4 4 [repeat]
(N=7) 1 1 2 2 3 3 4 4 7 7 6 6 5 5 [repeat]
(N=?) 1 1 2 2 ... N/2+1 N/2+1 N N N-1 N-1 N-2 N-2 ... N/2+2 N/2+2
In other words, we count up to half of N (rounding up), then count down for the rest. The rest of this will work with just the N=5 example and make some extrapolations from there. Let's create an array P which holds these values, and a function f(p) which computes the value of P at index p:
f(p) = { p if p <= N/2+1
{ N-p+N/2+1 otherwise
-or-
f(p) = { p if p <= N/2+1
{ 3N/2-p+1 otherwise
P = [f(p) for p in range(1,N+1)] # P = [1 2 3 5 4]
P = reduce(lambda array, pair: array+pair, [[x,x] for x in p]) # duplicate each entry and append them all together
-or-
P = [f(p/2) for p in range(1,2*N+1)] # using integer division to get duplicates in one step
To summarize, up to now we've come up with a repeating pattern for all but the central column, which we will continue to ignore for a while longer. Given the array P, surely we can just index into it to find where each strand is at iteration i.
strand s after i iterations = P[(start(s) + i) % 2N]
where start(s) is the starting index into P of strand s
Now for start(s).. For this we'll try some ASCII visualizations. Here, I've labelled where each column A-E starts in the cycle:
A 1 D
1 4
2 4
2 5
B E
3 5
3
C
That's actually not too bad. A B C E D uses the same ordering function as 1 2 3 5 4, so we'll just reuse that logic. Confusing, I know, but remember that A-E are just an alias for columns 1-5. Note that everything gets doubled since |P|=2N.
{ 2*s-1 if s <= N/2+1
start(s) = { 3N-2*s+2 otherwise
Awesome - we have an O(1) solution for each column except the middle one! So let's finally take a closer look at the middle:
(N=3) 2 1 3 [repeat]
(N=5) 3 1 5 2 4 [repeat]
(N=7) 4 1 7 2 6 3 5 [repeat]
Here's the cool part:
v v v v v v
3 3 5 5 4 4 1 1 2 2 3 3 5 5 4 4 1 1 2 2 3 3 5 5 4 4 1 1 2 2 3 3 5 5 4 4
Those are extremely well spaced-out. In fact, they are 6 spaces apart when N=5 and 8 spaces apart when N=7. Pattern found!
since middle index is N/2+1..
middle(i) = P[start((N/2+1) + (N+1) * i) % 2N]
So that's pretty much it. I was inconsistent about zero-indexing and some other formatting, but hopefully you now get the general idea of how to compute the position of strands in a braid after some number of iterations. Go tell all your friends.