On 11/21/2011 06:57 PM, Steven D'Aprano wrote:
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.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_permutationHere is the code: def survivor(names, step): next = namesThis 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 - 1This 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, ...
index = (index-1) + step
while index > len(next): index = index - len(next) if index == len(next): index = 0You 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.
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.return names[0]
-- DaveA _______________________________________________ Tutor maillist - [email protected] To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
