https://github.com/python/cpython/commit/92a13a00a5a6190626f68afc71241194a66dcc02
commit: 92a13a00a5a6190626f68afc71241194a66dcc02
branch: 3.14
author: Miss Islington (bot) <[email protected]>
committer: rhettinger <[email protected]>
date: 2026-01-10T22:06:37-06:00
summary:
[3.14] Add derangements() recipe (gh-143671) (gh-143677)
files:
M Doc/library/itertools.rst
diff --git a/Doc/library/itertools.rst b/Doc/library/itertools.rst
index aa46920d3526f0..0bc9b933d89227 100644
--- a/Doc/library/itertools.rst
+++ b/Doc/library/itertools.rst
@@ -842,7 +842,7 @@ and :term:`generators <generator>` 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 <generator>` 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))
_______________________________________________
Python-checkins mailing list -- [email protected]
To unsubscribe send an email to [email protected]
https://mail.python.org/mailman3//lists/python-checkins.python.org
Member address: [email protected]
