Solution of Josephus problem with negative count-CodePudding

I would like to find the simplest algorithm for the general Josephus problem, i.e. with a count in any direction.
The combined "recursive-list" algorithm is taken as a basis (Python).
It works well with positive shift and starts well with negative, but then something goes wrong.

def add(x):
    if x >= 0:
        return 1
    return -1


def josephus(arr, start, shift):
    if len(arr) == 1:
        return arr
    else:
        start = (start   shift - add(shift)) % len(arr)
        arr.pop(start)
        print(arr)
        return josephus(arr, start, shift)

size = int(input())
people = list(range(1, size   1))
start = int(input()) - 1
shift = int(input())
print(people)
josephus(people, start, shift)

Adding several "if" statements could help, but I would not like to do so.

CodePudding user response：

The reason for the different behaviour with negative values is that after executing arr.pop(start), the value at the start index (modulo the new size) will always be the next element in "clockwise" (right) direction.

This effect should be mirrored when the shift is negative.

So when shift is negative, subtract one from start after executing the pop:

    arr.pop(start)
    if shift < 0: 
        start -= 1