How to solve the Josephus puzzle in python?

Question

I am trying to represent the Josephus problem in Python. Briefly, given a list items, every kth element is visited/marked until there are no items "untouched". How do I loop through the list in that manner and see what the last untouched element is?

My code is:

def josephus(items,k):
    while len(items)>1:
        del items[k]
    return items

But, when I am trying to

print(josephus([1,2,3,4,5,6,7,8,9,10],2))

It returns:

  line 3, in josephus
    del items[k]
IndexError: list assignment index out of range

Could you help me. Whats wrong with that code?

Answer 1

You are trying to delete the item at index 2, but you deleted that item already.

Python indexes start at 0, not at 1, so 2 is the third item. In other words, the list [1, 2] has a length longer than 1 (there are 2 items), but only the index 0 and 1 exist in that list.

You could add printing to your loop to see what is happening:

def josephus(items, k):
    while len(items) > 1:
        print(items)
        del items[k]
    return items

and call the function with a slightly shorter list to keep the output manageable:

>>> josephus([1,2,3,4], 2)
[1, 2, 3, 4]
[1, 2, 4]
[1, 2]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 4, in josephus
IndexError: list assignment index out of range

This shows you are deleting the 3rd item each time, and the error is thrown when there are only 2 items left.

Instead of hardcoding the length, you could test for a length greater than k:

def josephus(items, k):
    while len(items) > k:
        del items[k]
    return items

Now the loop condition guarantees there is an element at index k to delete:

>>> def josephus(items, k):
...     while len(items) > k:
...         del items[k]
...     return items
... 
>>> josephus([1,2,3,4], 2)
[1, 2]

This is a lot of work to delete everything from a given index onwards however. Just use a slice:

def josephus(items, k):
     del items[k:]
     return items

The [k:] notation tells Python to address all items starting at index k until the end of the list (there is no value after the :).

However, if you are supposed to delete every kth element (so every 2nd or 3rd, etc.) then you are going about it the wrong way. Use slice notation again:

del items[::k]

I filled in the 3rd slot of a slice, the stride. This will delete element 0 + 0 * k, and 0 + 1 * k, and 0 + 2 * k, etc:

>>> items = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
>>> items[::2]
[1, 3, 5, 7, 9]
>>> del items[::2]
>>> items
[2, 4, 6, 8, 10]

If you are trying to implement the Josephus problem you cannot use this to delete items as the deletion has to be circular, at least not without calculating a new starting point for the next 'round' of eliminations. Use the % modulus operator to go around the circle, adjusting for the changing length:

def josephus(items, k):
    skip = k - 1  # deletion removes the item, so skip k - 1
    index = skip % len(items)
    while len(items) > 1:
        del items[index]
        index = (index + skip) % len(items) 
    return items[0]

Note that I now return the one surviving item, not the list.

The code keeps track of the next item to delete in index. We start at k - 1 to adjust for 0-based indexing; the second item is at 1. We then go around the 'circle' by incrementing by k - 1 steps as we just removed the kth item and everything after will have moved up a step around the circle, and by using % to wrap back to the start of the list.

Answer 2

If you want to delete every k value in your original list starting at index i, just do

del items[i::k]

In your specific case, it looks like you want to delete item k first, so do:

del items[k-1::k]

This is so simple that you wouldn't wrap it in a function but if you want to:

To wrap it in a function:

def josephus(items,k):
    del items[k-1::k]
    return items

Answer 3

You need > k:

 while len(items) > k:

The last value items before the error is [1, 2] so items[2]-> IndexError as you are trying to index the third element of a two element list.

def josephus(items, k):
    while len(items) > k:
        del items[k]
    return items

Output:

In [27]: josephus([1,2,3,4,5,6,7,8,9,10],2)
Out[27]: [1, 2]

If you wanted to 2 to mean the second index you would need to -1 from k:

def josephus(items, k):
    while len(items) >= k:
        del items[k-1]
    return items

Now you would get a single element:

In [29]: josephus([1,2,3,4,5,6,7,8,9,10],2)
Out[29]: [1]

To just delete the k'th element:

def josephus(items, k):
    if 0 <= k < len(items):
        del items[k]
    return items