Skip to content

Add derangements #946

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.

Sign up for GitHub

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

Jump to bottom
Merged
merged 19 commits into from
May 6, 2025
Merged

Add derangements #946

merged 19 commits into from
May 6, 2025

Conversation

debruijn
Copy link
Contributor

@debruijn debruijn commented Jan 12, 2025 •
edited
Loading

Issue reference

Follow-up from #938
Implementing some recommendations from #937
I aim to keep this PR up to date in case the discussions there lead to required changes.
I keep this PR as a Draft until 10.6.0 is released (unless the maintainers want to include this in there still).

Changes

Following the discussion in #937:

  • Changed default behavior of derangements to be based on the input index of each element, instead of its value (thanks bbayles)
  • The original behavior is available by toggling by_index to False. (If other ways are preferred, let me know)
  • Underlying algorithm is sped up based on suggestions by pochmann3
  • distinct_derangements is updated in a similar way
  • Tests and stubs are updated accordingly

Checks and tests

I confirm to have run make all-checks (with everything passing) before submitting this PR.

Update per 17 jan

  • Merged master into this branch
  • Updated contents to the current state in the linked issue
  • Made sure make all-checks still works
  • Removed the Draft status

@debruijn
Copy link
Contributor Author

Note that the improved algorithm for derangements and distinct_derangements is not the same one: the algorithm for derangements is a slightly faster one which uses two permutations iterators that run in sync (one on the actual input, and one on its associated indices) - this is not transferable to distinct_permutations since the indices iterator wouldn't know when a duplicate is skipped by distinct_permutations on the input.

@debruijn
Copy link
Contributor Author

Update per 17 jan

  • Merged master into this branch
  • Updated contents to the current state in the linked issue
  • Made sure make all-checks still works
  • Removed the Draft status

@debruijn debruijn marked this pull request as ready for review January 18, 2025 00:46
@debruijn debruijn mentioned this pull request Jan 18, 2025
Closed
@bbayles bbayles mentioned this pull request May 1, 2025
Merged
@bbayles bbayles merged commit 3167e9c into more-itertools:master May 6, 2025
6 checks passed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers
No reviews
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.
2 participants
@debruijn @bbayles