Re: [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

_______________________________________________
Tutor maillist  -  Tutor@python.org
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor