Timeline for Total Derangement (Difficulty Level: Hard)
Current License: CC BY-SA 3.0
22 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 25, 2022 at 4:39 | answer | added | Anders Kaseorg | timeline score: 2 | |
| Jun 24, 2022 at 19:02 | answer | added | Ajax1234 | timeline score: 1 | |
| Feb 8, 2018 at 10:52 | comment | added | user74201 | Is it fine to use built-in combinatorial functions? | |
| Jan 24, 2017 at 23:19 | comment | added | Peter Taylor | chat.stackexchange.com/rooms/52408/cyclic-mutual-derangements | |
| Jan 24, 2017 at 14:01 | history | tweeted | twitter.com/StackCodeGolf/status/823893483211649024 | ||
| Jan 24, 2017 at 5:29 | comment | added | Alecto | If n is an odd number than m can be n-1 but that isn't covered in the challenge | |
| Jan 24, 2017 at 5:18 | comment | added | Alecto | The worst case time complexity will always be when m=n-2 (since that's the maximum value m can take on for the challenge). Different algorithms will be compared for that case. | |
| Jan 24, 2017 at 5:11 | comment | added | xnor | "The fastest algorithm (in time complexity) wins." There's two parameters here, m and n, so it's not clear how to compare tradeoffs between these. If you mean for m to be linear in n, that would resolve it. | |
| Jan 24, 2017 at 2:17 | comment | added | Alecto | If you'd like I could share all the code I've produced so far working on this problem. | |
| Jan 24, 2017 at 2:12 | history | edited | Alecto | CC BY-SA 3.0 | edited title |
| Jan 24, 2017 at 2:05 | comment | added | Alecto | I cleared up ambiguity and stated that all the different ways of doing it with m cycles of length n should have the same probability of occurring | |
| Jan 24, 2017 at 2:04 | history | edited | Alecto | CC BY-SA 3.0 | added 113 characters in body |
| Jan 24, 2017 at 1:57 | comment | added | Alecto | An answer for n=9, m=7 is {{5, 3, 4, 2, 0, 7, 8, 6, 1}, {2, 0, 8, 6, 5, 3, 1, 4, 7}, {1, 4, 6, 7, 8, 2, 3, 0, 5}, {8, 6, 0, 4, 7, 1, 2, 5, 3}, {3, 7, 5, 1, 2, 0, 4, 8, 6}, {4, 5, 7, 8, 3, 6, 0, 1, 2}, {6, 8, 3, 5, 1, 4, 7, 2, 0}} | |
| Jan 24, 2017 at 0:44 | history | reopened | CommunityBot mbomb007 JungHwan Min FlipTack Alecto | ||
| Jan 23, 2017 at 23:17 | comment | added | Peter Taylor | Can you give an example with n=9, m=7? (If you can then there's a further ambiguity, which is what the distribution of the random cycles should be: I presume it's selecting a random set of valid derangements such that each set is selected with equal probability assuming a perfect random number generator, but that's not entirely clear; however, the task being actually possible is a much bigger problem). | |
| Jan 23, 2017 at 23:07 | comment | added | Alecto | Please either clarify what the ambiguity is that remains or remove the hold on my question. I believe I have corrected everything you asked, and aside from that I don't believe it violates the rules in any way. | |
| Jan 23, 2017 at 21:47 | review | Reopen votes | |||
| Jan 23, 2017 at 23:02 | |||||
| Jan 23, 2017 at 21:32 | history | edited | Alecto | CC BY-SA 3.0 | added 616 characters in body |
| Jan 23, 2017 at 21:18 | history | edited | Alecto | CC BY-SA 3.0 | added 53 characters in body |
| Jan 23, 2017 at 19:52 | history | closed | Peter Taylor Conor O'Brien mbomb007 Blue Riker | Needs details or clarity | |
| Jan 23, 2017 at 19:39 | review | Close votes | |||
| Jan 23, 2017 at 19:52 | |||||
| Jan 23, 2017 at 19:01 | history | asked | Alecto | CC BY-SA 3.0 |