-
Notifications
You must be signed in to change notification settings - Fork 306
Add derangements #938
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Add derangements #938
Conversation
Thanks for the suggestion. I'm good with |
Thank you! I have removed For my understanding: is it out of scope because it doesn't take an iterable as input? If so, I think that makes sense, and I might look for a combinatorics package to include it in (or make one myself). |
Your original issue gave a great motivating example - secret Santa - for the |
Ah, I think I had confused you by my later comment in the linked issue. The generalizations were not part of this PR but something I thought of afterwards and included as suggestion in the issue to discuss (and I agree with you that these generalizations would be out of scope here since there is not a documented definition of them). On the other hand, the removed If that changes your mind, let me know, then I can add them back. |
Issue reference
#937
Changes
Include
derangements
,derangements_range
anddistinct_derangements
intomore_itertools
as presented in the linked issue.Some explanations:
distinct_permutations
as possible regarding usage and documentation. Because of this, I have put it close to that function inmore.py
.derangements_range(n)
there is an implementation that makes use of knowing the input to avoid testing each element, and achieves a runtime of about 1/4th to 1/3rd ofderangements(range(n))
.n-1
andn-2
:n-1
is extended with this new element by putting it on each position with the displaced element put at the back which is always possiblen-1
case that violates the restriction. To construct these, use an adjustedn-2
solution and extend it by swapping in the two missing elements.derangements
anddistinct_derangements
the current implementation is simply filtering out non-deranged elements ofpermutations
ordistinct_permutations
. In this case, the benefit for the user is in convenience and clarity.Checks and tests
Done, all pass.