[Tutor] Python code trouble!

[Dave Angel]

On 11/21/2011 06:57 PM, Steven D'Aprano wrote:
> Hello John,
>
>
> You are still posting from the future. Please fix your computer so 
> that it is no longer set 12 hours in the future. Or perhaps your 
> computer is just set in the wrong time zone.
>
>
> John wrote:
>> Hi all,
>>
>> I have attempted to create a programme which removes every Nth person 
>> from the list until there is only one name remaining. N is inputted 
>> by the user.
>
> Ah, the Josephus problem! Trickier than it seems.
>
> http://en.wikipedia.org/wiki/Josephus_permutation
>
>
>> Here is the code:
>>
>> def survivor(names, step):
>>     next = names
>
> This line is pointless. It just assigns a new name to the same list. 
> Why not just work directly with "names" instead of the misleading 
> "next"? (Next what?)
>
>>     while len(next) > 1:
>>      index = step - 1
>>      next.remove (next[index])
>
> This does not do what you think it does, but even when it does, it 
> doesn't it slowly and inefficiently.
>
> You start of with an index. You want to delete the item at that index. 
> So you start by retrieving the item at that index, then instruct the 
> list to search from the beginning of the list for something which 
> matches, then delete that. So consider what happens if you have a 
> really huge list, with tens of thousands of items, and ask to delete 
> the last one: even though you know you want to delete the last item, 
> the remove() method has to check every single item first.
>
> Worse, what if there are duplicates? The *first* duplicate found will 
> be removed, instead of the one at the given index.
>
> If you want to delete the name at an index, you should just directly 
> delete the name at the index:
>
> del names[index]
>
>
>>         index = index + step - 1
>
> This line is wrong. It means that you take one fewer step each time 
> than you expect. For instance, if you take step = 4, you should step 
> along indexes 3, 3+4=7, 7+4=11, 11+4=15, ... but instead you step 
> along indexes 3, 3+4-1=6, 6+4-1=9, 9+4-1=12, ...
Actually, this one is the one he got right.  Since he just deleted an 
item from the list, he should base the step off one *before* the present 
one.
         index = (index-1) + step
>
>
>>         while index > len(next):
>>             index = index - len(next)
>>         if index == len(next):
>>             index = 0
>
> You can combine both of those with a single test:
>
>     while index >= len(names):
>         index = index - len(names)
>
He could simplify that using the modulo operator.
>
>>     return names[0]
>>
>>
I'm not familiar with the Josephus problem, and I don't have time right 
now to research it.  So I can't help with the rest.



-- 

DaveA