Skip to content

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

Merged
merged 11 commits into from
Jan 3, 2025
Merged

Add derangements #938

merged 11 commits into from
Jan 3, 2025

Conversation

debruijn
Copy link
Contributor

@debruijn debruijn commented Dec 27, 2024

Issue reference

#937

Changes

Include derangements, derangements_range and distinct_derangements into more_itertools as presented in the linked issue.

Some explanations:

  • I have tried to make this as similar to distinct_permutations as possible regarding usage and documentation. Because of this, I have put it close to that function in more.py.
  • For 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 of derangements(range(n)).
    • This is done using a Dynamic Programming solution, that uses the output of n-1 and n-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 possible
    • The other solutions are all those in which the new element swaps out with a single element in the n-1 case that violates the restriction. To construct these, use an adjusted n-2 solution and extend it by swapping in the two missing elements.
  • For derangements and distinct_derangements the current implementation is simply filtering out non-deranged elements of permutations or distinct_permutations. In this case, the benefit for the user is in convenience and clarity.
    • Further speed-up of these two might be possible as well. Initial exploration of this ended up with an algorithm that was about as fast as this filtering solution but way more convoluted, but I might give that another try at some point. (Unless someone else beat me to it)

Checks and tests

Done, all pass.

@bbayles
Copy link
Collaborator

bbayles commented Dec 31, 2024

Thanks for the suggestion. I'm good with derangements and distinct_derangements, but the range variant is probably out of scope for this library. If you can update the PR with those two in it, I'll include them in the next release.

@debruijn debruijn marked this pull request as ready for review December 31, 2024 19:42
@debruijn
Copy link
Contributor Author

Thank you! I have removed derangements_range.

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).

@bbayles bbayles merged commit c83cff7 into more-itertools:master Jan 3, 2025
@bbayles
Copy link
Collaborator

bbayles commented Jan 7, 2025

Your original issue gave a great motivating example - secret Santa - for the derangements. So that one I think makes sense to include. But the generalization I think is better suited for a more specialized library.

@debruijn
Copy link
Contributor Author

debruijn commented Jan 7, 2025

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 derangements_range function was just a utility function to generate classical derangements when the input is a range of numbers 0 to k, but faster than derangements. So derangements_range(k) == derangements(range(k)) for all k, but the default derangements function can also deal with input that is not just [0, 1, 2, 3], such as [0, 4, 13] or [0, 0, 1, 1] or ["blue", "red", 0, 1, -5]), at the sacrifice of being slower because of filtering permutations instead of making use of the assumptions that derangements_range does. (Edit: so the secret santa movitation applies to both derangements and derangements_range)

If that changes your mind, let me know, then I can add them back.

@debruijn debruijn mentioned this pull request Jan 12, 2025
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

2 participants