Permutations/Derangements

A derangement is a permutation of the order of distinct items in which no item appears in its original place.

Permutations/Derangements is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

For example, the only two derangements of the three items (0, 1, 2) are (1, 2, 0), and (2, 0, 1).

The number of derangements of n distinct items is known as the suubfactorial of n, sometimes written as !n. There are various ways to calculate !n.

Task

The task is to:

1. Create a named function/method/subroutine/... to generate derangements of the integers 0..n-1, (or 1..n if you prefer).
2. Generate and show all the derangements of 4 integers using the above routine.
3. Create a function that calculates the subfactorial of n, !n.
4. Print and show a table of the counted number of derangements of n vs. the calculated !n for n from 0..9 inclusive.

As an optional stretch goal:

• Calculate !20.

Python

Includes stretch goal. <lang python>from itertools import permutations import math

def derangements(n):

   'All deranged permutations of the integers 0..n-1 inclusive'
   return ( perm for perm in permutations(range(n))
            if all(indx != p for indx, p in enumerate(perm)) )

def subfact(n):

   if n == 2 or n == 0:
       return 1
   elif n == 1:
       return 0
   elif  1 <= n <=18:
       return round(math.factorial(n) / math.e)
   elif n.imag == 0 and n.real == int(n.real) and n > 0:
       return (n-1) * ( subfact(n - 1) + subfact(n - 2) )
   else:
       raise ValueError()

def _iterlen(iter):

   'length of an iterator without taking much memory'
   l = 0
   for x in iter:
       l += 1
   return l

if __name__ == '__main__':

   n = 4
   print("Derangements of %s" % (tuple(range(n)),))
   for d in derangements(n):
       print("  %s" % (d,))

   print("\nTable of n vs counted vs calculated derangements")
   for n in range(10):
       print("%2i %-5i %-5i" %
             (n, _iterlen(derangements(n)), subfact(n)))

   n = 20
   print("\n!%i = %i" % (n, subfact(n)))</lang>

Sample output

Derangements of (0, 1, 2, 3)
  (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)

Table of n vs counted vs calculated derangements
 0 1     1    
 1 0     0    
 2 1     1    
 3 2     2    
 4 9     9    
 5 44    44   
 6 265   265  
 7 1854  1854 
 8 14833 14833
 9 133496 133496

!20 = 895014631192902121