Permutations/Derangements: Difference between revisions
New draft task and Python solution. |
J: brute force implementation |
||
Line 15: | Line 15: | ||
As an optional stretch goal: |
As an optional stretch goal: |
||
* Calculate !''20''. |
* Calculate !''20''. |
||
=={{header|J}}== |
|||
Note: !n in J denotes factorial (or gamma n+1), and not subfactorial. |
|||
<lang j>derangement=: (A.&i.~ !)~ (*/ .~: # [) i. NB. task item 1 |
|||
subfactorial=: ! * +/@(_1&^ % !)@i.@>:</lang> NB. task item 3 |
|||
Required examples: |
|||
<lang j> (,subfactorial,#@derangement)"0 i.10 NB. task item 2 |
|||
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 |
|||
subfactorial 20 NB. task item 4 |
|||
8.95015e17 |
|||
subfactorial 20x NB. using extended precision |
|||
895014631192902121</lang> |
|||
Note that derangement 10 was painfully slow (almost 3 seconds, about 10 times slower than derangement 9 and 100 times slower than derangement 8) -- this is a brute force approach. |
|||
=={{header|Python}}== |
=={{header|Python}}== |
Revision as of 11:20, 14 May 2011
A derangement is a permutation of the order of distinct items in which no item appears in its original place.
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:
- Create a named function/method/subroutine/... to generate derangements of the integers 0..n-1, (or 1..n if you prefer).
- Generate and show all the derangements of 4 integers using the above routine.
- Create a function that calculates the subfactorial of n, !n.
- 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.
J
Note: !n in J denotes factorial (or gamma n+1), and not subfactorial.
<lang j>derangement=: (A.&i.~ !)~ (*/ .~: # [) i. NB. task item 1 subfactorial=: ! * +/@(_1&^ % !)@i.@>:</lang> NB. task item 3
Required examples:
<lang j> (,subfactorial,#@derangement)"0 i.10 NB. task item 2 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
subfactorial 20 NB. task item 4
8.95015e17
subfactorial 20x NB. using extended precision
895014631192902121</lang>
Note that derangement 10 was painfully slow (almost 3 seconds, about 10 times slower than derangement 9 and 100 times slower than derangement 8) -- this is a brute force approach.
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