Что происходит внутри моей петли?

Question

Я пытался запрограммировать Josephus problem, и по какой-то причине он работает только в некоторых ситуациях, я не уверен, почему. TL, DR, как это работает:

У вас есть группа людей в круге. Каждый N-й человек будет убит до тех пор, пока не останется только один последний человек. Так скажите, например, у вас 10 человек [AKA: X], и вы решили убить каждого третьего человека [AKA: Nth], он будет выглядеть так:

1-й тур: 1, 2, (3 матрицы), 4, 5, (6 штампов), 7, 8, (9 штампов), 10

2-й тур: 1, (2 умирает, потому что это непрерывный круг), 3, 5, (7 штампов), 8, 10

3-й этап: (1), 4, 5, (8), 10

4-й тур: 4, (5), 10

5-й тур: 4, (10)

И мы, наконец, остались с человеком №4 как одинокий выживший.

Моя программа делает это отлично. Однако, когда я вводил X как 55 и N как 17, я получаю неправильный ответ человека 27, когда он должен быть человеком 40. Может ли кто-нибудь сказать мне, где моя петля?

Исходный код:

def solveJosephus(specifics): 
    people = [int(x) for x in range(1,int(specifics[0])+1)] 
    killPosition = int(specifics[1]) 
    positionCounter = 0 
    sorted = False 

    while not sorted: 
     if len(people) == 1: 
      print(people[0]) # Pyschologically scarred Winner! 
      sorted = True 
     for person in people: 
      positionCounter += 1 
      if positionCounter == killPosition: 
       print(person) 
       people.remove(person) 
       positionCounter = 1 

solveJosephus(raw_input().split()) 

Answer 1

В дополнение ко всему otheranswers (сообщая вам сделать копию списка при повторе), другая проблема с вашим кодом заключается в том, что вы сбросили positionCounter на 1 в этой строке: positionCounter = 1. Он должен быть сброшен на 0. Вот полный рабочий код (работает до сих пор):

def solveJosephus(specifics): 
    people = [int(x) for x in range(1,int(specifics[0])+1)] 
    killPosition = int(specifics[1]) 
    positionCounter = 0 
    sorted = False 

    while not sorted: 
     if len(people) == 1: 
      print(people[0]) # Pyschologically scarred Winner! 
      sorted = True 
     for person in people[:]: #Make copy of iterating list 
      positionCounter += 1 
      if positionCounter == killPosition: 
       print(person) 
       people.remove(person) 
       positionCounter = 0 #Important! 0 != 1 

solveJosephus(raw_input().split()) 

Answer 2

Я не уверен, почему вы иногда получаете право или неправильный ответ, но я всегда бежать в чужие проблемы, если я пытаюсь изменить список в то время как итерация над ним, как ваш

for person in people: 
    ... 
    people.remove(person) 

не делает. Возможно, вы можете перебирать people.copy(), вместо этого вы не изменяете тот же список, который вы повторяете.

Answer 3

Проблема в том, что вы удаляете людей из списка, итерации через него.

Что происходит следующее:

Скажем, у вас есть X = 5 и N = 2. Ваш список: [1,2,3,4,5]. Вы добираетесь до index = 1 и человек 2 умирает. Теперь ваш список: [1,3,4,5]. Проблема в том, ваш индекс по-прежнему равен 1, но теперь указывает на человека 3. Когда вы идете еще два места (индекс = 3), вместо того, чтобы убить человека 4, вы убиваете человек 5.