We have an array of unique elements. A special kind of permutation is the one that has all of its elements in a different position than the original.

Let's see how many of these permutations may be generated from an array of four elements. We put the original array with square brackets and the wanted permutations with parentheses. 
```
arr = [1, 2, 3, 4]
      (2, 1, 4, 3)
      (2, 3, 4, 1)
      (2, 4, 1, 3)
      (3, 1, 4, 2)
      (3, 4, 1, 2)
      (3, 4, 2, 1)
      (4, 1, 2, 3)
      (4, 3, 1, 2)
      (4, 3, 2, 1)
      _____________
A total of 9 permutations with all their elements in different positions than arr
```

The task for this kata would be to create a code to count all these permutations for an array of certain length.

Features of the random tests:
```
l = length of the array
10 ≤ l ≤ 5000
```

See the example tests.

Enjoy it!

Source: codewars | Difficulty: EASY
Tags: Number theory

Combinatorics

Mathematics

Starter code: def all_permuted(n):
	

Solutions:
def all_permuted(n):
	(a, b) = (0, 1)
	for i in range(1, n):
		(a, b) = (b, (i + 1) * (a + b))
	return a


from itertools import islice

def A000166():
	(a, b, n) = (1, 0, 1)
	while True:
		yield a
		(a, b) = (b, n * (a + b))
		n += 1
all_permuted = dict(enumerate(islice(A000166(), 5000))).get


subfactorial = [1, 0]
for n in range(1, 10 ** 4):
	subfactorial.append(n * (subfactorial[-1] + subfactorial[-2]))
all_permuted = subfactorial.__getitem__


def f(n):
	if n == 0:
		return 1
	else:
		return n * f(n - 1) + (1 if n % 2 == 0 else -1)

def all_permuted(array_length):
	return f(array_length)


import math

def all_permuted(n):
	return n * all_permuted(n - 1) + (-1) ** n if n > 2 else n - 1


from functools import lru_cache

@lru_cache(maxsize=None)
def all_permuted(n):
	if n == 0:
		return 1
	if n == 1:
		return 0
	return (n - 1) * (all_permuted(n - 1) + all_permuted(n - 2))


M = [1, 0]
for V in range(1, 9487):
	M.append(V * (M[V] + M[V - 1]))
all_permuted = lambda Q: M[Q]


def all_permuted(array_length):
	a = [1, 0]
	for x in range(2, array_length + 1):
		(a[0], a[1]) = (a[1], (x - 1) * (a[1] + a[0]))
	return a[1]


all_permuted = a = lambda n: (0, 0, 1)[n] if n < 3 else n * a(n - 1) + (-1) ** n


import math

def all_permuted(n):
	if n == 0:
		return 1
	return n * all_permuted(n - 1) + (-1) ** n