# Talk:Backshift

This doesn't work. Take `3124`

for example; it will try to move `4`

, but since the list is already of length 4, it halts, despite it being obviously unsorted. TuxCrafting (talk) 13:54, 12 June 2019 (UTC)

- Yes, I had previously discovered this bug and cannot fix it, so I left it alone... I will try my best to fix that bug.--
`A (talk)`

14:10, 12 June 2019 (UTC) - I cannot fix that bug; I encourage you to fix it. (Using that work-in-progress pseudo-code still did not help; it fell into an infinite loop.) --
`A (talk)`

14:12, 12 June 2019 (UTC)

def move_left(s, n): if n < 0: n = abs(n + len(s)) return s[:len(s)-n-1] + s[-1] + s[len(s)-n-1:-1]

I think this is the intended behaviour of `move_left()`

in python. It moves right on negative numbers. Salpynx (talk) 01:36, 13 June 2019 (UTC)

- TuxCrafting: I have devised a way to avoid this situation. Append the length of the list +1 before the rightmost digit:

3124 Add a "5". -> 53124 -> 53142 -> 52314 -> 52341 -> 15234 -> 15243 -> 15324 -> 15342 -> 12534 -> 12543 -> 12354 -> 12345

Now it halts. Copy the result back to this procedure with the 5 dropped (although it is evident that this is already sorted and does not need re-sorting, but I have devised it as part of the process). --`A (talk)`

08:20, 14 June 2019 (UTC)

I have an idea on improving the algorithm: the algorithm should halt when the rightmost item *mod* the item list's length *is equal to* 0.

## Modified version of the removed code from the main page

CODE REMOVED, see optimised "Condensed implementation" below

`backshift()`

takes a string number and optional radix. I have not even tried for elegance here, but it works. Salpynx (talk) 09:30, 13 June 2019 (UTC)

**Condensed implementation** code:

def move_left(s, n): if n < 0: n = abs(n + len(s)) n = n % len(s) return s[:len(s)-n-1] + s[-1] + s[len(s)-n-1:-1] def backshift(unsorted, radix=10): move_left_number = 1 i = 0 while move_left_number != 0: i += 1 c = unsorted[-1] rightmost_number = int(c, min(36, radix)) if ord(c) < 122 else ord(c) - 86 move_left_number=len(unsorted)-rightmost_number unsorted = move_left(unsorted, move_left_number) print(unsorted) print('Iter: %s' % i)

I've told you, the deleted program is equivalent to the original one. --`A (talk)`

08:27, 14 June 2019 (UTC)

## Computational class

This algorithm is definitely not Turing-complete, as it cannot modify unbounded memory; it can only operate in what the input of this algorithm supplies. So, this is at most a Linear bounded automaton. --`A (talk)`

11:11, 13 June 2019 (UTC)

## Graphing the function

Here is a graph of the terminating states of the first ~1M inputs (base10). It forms a Z-like fractal staircase with new "step" every power of the base. Salpynx (talk) 09:24, 14 June 2019 (UTC)

## Long cycle lengths

Non-terminating states can have quite long cycle lengths.

1123456789abcdefghijklmnopqrstuvwz

In base36 has a loop of cycle of length 1853020188851841 (if the following formula is correct)

112..{len-2}{len+1}

To produce a period of `3**{len-2}`

. This is not necessarily the longest period possible for any length, but is a way to generate long cycle periods of a known length. Salpynx (talk) 09:24, 14 June 2019 (UTC)