Permutations/Derangements: Difference between revisions

!20 = 895014631192902121

</pre>

=={{header|Wren}}==

{{trans|Kotlin}}

{{libheader|Wren-fmt}}

{{libheader|Wren-big}}

<lang ecmascript>import "/fmt" for Fmt

import "/big" for BigInt

var permute // recursive

permute = Fn.new { |input|

if (input.count == 1) return [input]

var perms = []

var toInsert = input[0]

for (perm in permute.call(input[1..-1])) {

for (i in 0..perm.count) {

var newPerm = perm.toList

newPerm.insert(i, toInsert)

perms.add(newPerm)

}

}

return perms

}

var derange = Fn.new { |input|

if (input.isEmpty) return [input]

var perms = permute.call(input)

var derangements = []

for (perm in perms) {

var deranged = true

for (i in 0...perm.count) {

if (perm[i] == i) {

deranged = false

break

}

}

if (deranged) derangements.add(perm)

}

return derangements

}

var subFactorial // recursive

subFactorial = Fn.new { |n|

if (n == 0) return BigInt.one

if (n == 1) return BigInt.zero

return (subFactorial.call(n-1) + subFactorial.call(n-2)) * (n - 1)

}

var input = [0, 1, 2, 3]

var derangements = derange.call(input)

System.print("There are %(derangements.count) derangements of %(input), namely:\n")

System.print(derangements.join("\n"))

System.print("\nN Counted Calculated")

System.print("- ------- ----------")

for (n in 0..9) {

var list = List.filled(n, 0)

for (i in 0...n) list[i] = i

var counted = derange.call(list).count

Fmt.print("$d $-9d $-9i", n, counted, subFactorial.call(n))

}

System.print("\n!20 = %(subFactorial.call(20))")</lang>

{{out}}

<pre>

There are 9 derangements of [0, 1, 2, 3], namely:

[1, 2, 3, 0]

[2, 0, 3, 1]

[2, 3, 0, 1]

[2, 3, 1, 0]

[1, 0, 3, 2]

[1, 3, 0, 2]

[3, 0, 1, 2]

[3, 2, 0, 1]

[3, 2, 1, 0]

N Counted Calculated

- ------- ----------

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