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)

Agreed, this version is better. It removes the redundant while and break from the original, and my except on ValueError didn't really add any functionality. Salpynx (talk) 04:20, 15 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)