Anonymous user
Talk:Sort disjoint sublist: Difference between revisions
→Indices as collection: I'' modify the task description.
(→Indices as collection: I'' modify the task description.) |
|||
| (2 intermediate revisions by 2 users not shown) | |||
Line 13:
:::The problem is that the repeated indices will not, in general, correspond to the location of the repeated data, once the data is sorted. --[[User:Rdm|Rdm]] 18:25, 14 February 2011 (UTC)
::::You're right. I tried the example on the main page using "6, 6, 1, 7" for the indices. Another solution would be to sort the indices after they come in. You could use the same sort function for that as you do for the data. Either way, it's an extra step. I vote for progrmamer's choice and let the indices come in however they will. --[[User:Mwn3d|Mwn3d]] 19:00, 14 February 2011 (UTC)
:::::I'm even more wrong. It's not good enough just to sort the indices. You should probably set-ify the indices as they come in to be sure. --[[User:Mwn3d|Mwn3d]] 21:58, 14 February 2011 (UTC)
:::::I confirmed that the Python-type algo's aren't upset by repeated terms - it just gives rise to extra, redundant work. You do, however have to eventually sort the indices and I think that this should be part of any correct answer that uses this type of algorithm rather than the Go-type algo. But even if duplicates did matter, I would read the task as ''not'' giving you duplicates. --[[User:Paddy3118|Paddy3118]] 19:49, 14 February 2011 (UTC)
Line 30:
[7, 0, 5, 4, 3, 2, 0, 6]</lang>
::::::--[[User:Rdm|Rdm]] 20:05, 14 February 2011 (UTC)
::::::: Just goes to show... I tried [6,6,6,1,7], and [6,7,6,1,6,1,7] and just assumed ...
::::::: I'll tighten the task description. --[[User:Paddy3118|Paddy3118]] 00:36, 15 February 2011 (UTC)
:: I only asked because I couldn't see whether having duplicates and not filtering could guarantee a correct result or not. If I can't see why a property might hold, I suspect it doesn't (an application of the Paranoid Principle). It should be reasonably simple to fix by adding a unique-ing step to the processing of the index list. (Fun problem overall! Short and not quite as obvious as it looks at first glance.) –[[User:Dkf|Donal Fellows]] 00:10, 15 February 2011 (UTC)
| |||