Description

I'd like to propose to add derangements (and a few variants) to more_itertools. Derangements of x are the subset of all permutations of x for which no element has index equal to its value (e.g. exclude (0, 2, 1) since 0 is at index-0 but include (1, 2, 0) since no element has index equal to its value).

More detailed, my proposal is to add three functions:

• derangements(iterable, r) that gets all derangements incl duplicates, like permutations(iterable, r)
• distinct_derangements(iterable, r) that removes duplicates, analog to distinct_permutations's relation to permutations
• derangements_range(n) that deals with the specific common case of generating derangements from a range, which allows for a faster implementation

References

Derangements can come up in a variety of applications, such as finding all ways to do Secret Santa without individuals getting to buy a present for themselves (which was the motivation for me thinking about this over Christmas due to a Standupmaths video) or all ways to let students correct each others tests. This can be generalized to use cases with duplicate numbers in the input, such as assigning a batch of Pull Requests to reviewers not reviewing their own PR.

Example code

The core idea can be coded by filtering out from all permutations:

def derangements(iterable, r=None):
  for p in permutations(iterable, r=r):
      if any(x == i for i, x in enumerate(p)): continue
      yield p

Example output

>>> sorted(derangements_range(4))
[(1, 0, 3, 2), (1, 2, 3, 0), (1, 3, 0, 2), (2, 0, 3, 1), (2, 3, 0, 1), (2, 3, 1, 0), (3, 0, 1, 2), (3, 2, 0, 1), (3, 2, 1, 0)]
>>> sorted(derangements(range(4), r=3))
[(1, 0, 3), (1, 2, 0), (1, 2, 3), (1, 3, 0), (2, 0, 1), (2, 0, 3), (2, 3, 0), (2, 3, 1), (3, 0, 1), (3, 2, 0), (3, 2, 1)]

>>> sorted(derangements([0, 0, 1, 2]))
[(1, 0, 0, 2), (1, 0, 0, 2), (1, 2, 0, 0), (1, 2, 0, 0), (2, 0, 0, 1), (2, 0, 0, 1), (2, 0, 1, 0), (2, 0, 1, 0)]
>>> sorted(distinct_derangements([0, 0, 1, 2]))
[(1, 0, 0, 2), (1, 2, 0, 0), (2, 0, 0, 1), (2, 0, 1, 0)]

Related work

If this would be accepted, then later on we can add random_derangement as well (analog to random_permutation and others), but I imagined it would be good to split up that discussion and deal with this part first.

Also, the method can be generalized to exclude a number from multiple positions, with or without overlap with other numbers. For example, [0, 0, 1, 2] could be permuted while excluding it from its original positions in the input, resulting in [(1, 2, 0, 0), (2, 1, 0, 0)] (actually twice, so this result is the distinct version). There would be a point where such a generalization is not officially a derangement anymore, so we might need to use another name (such as displacement).

Note

I have already worked on this over the past few days (my Christmas brain couldn't let it go) so I will open a PR with my implementation of these three proposed functions. Of course, feel free to propose adjustments/adjust however it would fit in this repository (including not at all or just a subset of it).