Timeline for Swaps to Sort an Array
Current License: CC BY-SA 4.0
23 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 3, 2020 at 7:53 | vote | accept | CommunityBot | ||
| Jan 1, 2020 at 14:27 | history | edited | Nick Kennedy | CC BY-SA 4.0 |
added 2564 characters in body; added 202 characters in body
|
| Dec 31, 2019 at 22:16 | history | edited | Nick Kennedy | CC BY-SA 4.0 |
deleted 13 characters in body
|
| Dec 31, 2019 at 20:47 | history | edited | Nick Kennedy | CC BY-SA 4.0 |
added 1 character in body
|
| Dec 31, 2019 at 20:18 | history | edited | Nick Kennedy | CC BY-SA 4.0 |
deleted 19 characters in body
|
| Dec 30, 2019 at 17:48 | comment | added | Jonah | Thanks Nick! I was kinda hoping you'd do a Jelly one -- was curious how compact it would be. My J solution could be golfed further but I think it will be somewhat long no matter what because these procedural algorithms aren't a great fit for J. | |
| Dec 30, 2019 at 17:44 | comment | added | Nick Kennedy | @Jonah Very clever! I’ve rewritten your algorithm in Jelly. The implementation is different in places, but the overall idea is the same. | |
| Dec 30, 2019 at 17:43 | history | undeleted | Nick Kennedy | ||
| Dec 30, 2019 at 17:43 | history | edited | Nick Kennedy | CC BY-SA 4.0 |
added 2891 characters in body
|
| Dec 30, 2019 at 7:28 | history | deleted | Nick Kennedy | via Vote | |
| Dec 29, 2019 at 22:19 | comment | added | Jonah | Okay I believe I have a correct algorithm that is fast in all cases. See my (very ungolfed) edit. In addition, note that the longer test case anwers provided in the OP were incorrect: My algorithm found shorter solutions. | |
| Dec 28, 2019 at 20:13 | comment | added | Nick Kennedy | @Jonah I haven’t checked, but would this work even for multiple sets of clumped dups which partially swap with each other? | |
| Dec 28, 2019 at 19:56 | comment | added | Jonah | My only other idea, which I don't have time to explore atm, is to first remove the "clumped dups", then solve, then add back in the swaps for the clumped dups, because (I think) the clumped dups always move as a chunk of swaps. | |
| Dec 28, 2019 at 19:54 | comment | added | Nick Kennedy | @Jonah quite right. I’ll leave my two previous answers up for now; one works for any lists without duplicates, the other works for any list but becomes very slow with multiple repeated values. | |
| Dec 28, 2019 at 19:53 | history | rollback | Nick Kennedy |
Rollback to Revision 2
|
|
| Dec 28, 2019 at 19:48 | comment | added | Jonah |
I believe this one 4,5,2,1,3,3,10,9,7,6,8,8 can be done in 8. Ie, sometimes you need it to go one way, sometimes the other way. Try it online!
|
|
| Dec 28, 2019 at 19:18 | comment | added | Nick Kennedy | @Jonah what do you think of what I’ve done? I noticed that the problem arose when the items that ultimately needed swapping with the duplicates were not in ascending order from left-to-right, so sort the duplicates on that basis. I’m not sure it will always work though. | |
| Dec 28, 2019 at 19:17 | history | edited | Nick Kennedy | CC BY-SA 4.0 |
deleted 2176 characters in body
|
| Dec 28, 2019 at 18:52 | history | edited | Nick Kennedy | CC BY-SA 4.0 |
added 2668 characters in body
|
| Dec 28, 2019 at 18:45 | comment | added | Jonah | Yep. I'm stuck on exactly the same thing. | |
| Dec 28, 2019 at 18:45 | comment | added | Nick Kennedy | @Jonah indeed. I’ve tried testing the Cartesian product of all permutations of identical ones but it fails for the last two examples because there are too many possibilities. I’ll give it some more thought. | |
| Dec 28, 2019 at 17:13 | comment | added | Jonah | Looks like this fails on the same one that mine does: 4 5 2 1 3 3 (courtesy of Neil) | |
| Dec 28, 2019 at 17:06 | history | answered | Nick Kennedy | CC BY-SA 4.0 |