From 718c15fa9558efcdbe49aa729cfac8b796bc5968 Mon Sep 17 00:00:00 2001 From: Raymond Hettinger Date: Sat, 10 Jan 2026 19:47:27 -0600 Subject: [PATCH] Add derangements() recipe (gh-143671) --- Doc/library/itertools.rst | 42 ++++++++++++++++++++++++++++++++++++++- 1 file changed, 41 insertions(+), 1 deletion(-) diff --git a/Doc/library/itertools.rst b/Doc/library/itertools.rst index aa46920d3526..0bc9b933d892 100644 --- a/Doc/library/itertools.rst +++ b/Doc/library/itertools.rst @@ -842,7 +842,7 @@ and :term:`generators ` which incur interpreter overhead. from contextlib import suppress from functools import reduce from math import comb, prod, sumprod, isqrt - from operator import itemgetter, getitem, mul, neg + from operator import is_not, itemgetter, getitem, mul, neg def take(n, iterable): "Return first n items of the iterable as a list." @@ -978,6 +978,16 @@ and :term:`generators ` which incur interpreter overhead. slices = starmap(slice, combinations(range(len(seq) + 1), 2)) return map(getitem, repeat(seq), slices) + def derangements(iterable, r=None): + "Produce r length permutations without fixed points." + # derangements('ABCD') → BADC BCDA BDAC CADB CDAB CDBA DABC DCAB DCBA + # Algorithm credited to Stefan Pochmann + seq = tuple(iterable) + pos = tuple(range(len(seq))) + have_moved = map(map, repeat(is_not), repeat(pos), permutations(pos, r=r)) + valid_derangements = map(all, have_moved) + return compress(permutations(seq, r=r), valid_derangements) + def iter_index(iterable, value, start=0, stop=None): "Return indices where a value occurs in a sequence or iterable." # iter_index('AABCADEAF', 'A') → 0 1 4 7 @@ -1663,6 +1673,36 @@ The following recipes have a more mathematical flavor: ['A', 'AB', 'ABC', 'ABCD', 'B', 'BC', 'BCD', 'C', 'CD', 'D'] + >>> ' '.join(map(''.join, derangements('ABCD'))) + 'BADC BCDA BDAC CADB CDAB CDBA DABC DCAB DCBA' + >>> ' '.join(map(''.join, derangements('ABCD', 3))) + 'BAD BCA BCD BDA CAB CAD CDA CDB DAB DCA DCB' + >>> ' '.join(map(''.join, derangements('ABCD', 2))) + 'BA BC BD CA CD DA DC' + >>> ' '.join(map(''.join, derangements('ABCD', 1))) + 'B C D' + >>> ' '.join(map(''.join, derangements('ABCD', 0))) + '' + >>> # Compare number of derangements to https://oeis.org/A000166 + >>> [len(list(derangements(range(n)))) for n in range(10)] + [1, 0, 1, 2, 9, 44, 265, 1854, 14833, 133496] + >>> # Verify that identical objects are treated as unique by position + >>> identical = 'X' + >>> distinct = 'x' + >>> seq1 = ('A', identical, 'B', identical) + >>> result1 = ' '.join(map(''.join, derangements(seq1))) + >>> result1 + 'XAXB XBXA XXAB BAXX BXAX BXXA XAXB XBAX XBXA' + >>> seq2 = ('A', identical, 'B', distinct) + >>> result2 = ' '.join(map(''.join, derangements(seq2))) + >>> result2 + 'XAxB XBxA XxAB BAxX BxAX BxXA xAXB xBAX xBXA' + >>> result1 == result2 + False + >>> result1.casefold() == result2.casefold() + True + + >>> list(powerset([1,2,3])) [(), (1,), (2,), (3,), (1, 2), (1, 3), (2, 3), (1, 2, 3)] >>> all(len(list(powerset(range(n)))) == 2**n for n in range(18)) -- 2.47.3