Skip to content

Add derangements#946

Merged
bbayles merged 19 commits intomore-itertools:masterfrom
debruijn:add_derangements
May 6, 2025
Merged

Add derangements#946
bbayles merged 19 commits intomore-itertools:masterfrom
debruijn:add_derangements

Conversation

@debruijn
Copy link
Copy Markdown
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
Copy Markdown
Contributor Author

debruijn commented Jan 12, 2025

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
Copy Markdown
Contributor Author

debruijn commented Jan 18, 2025

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