Permutations/Derangements: Difference between revisions

=={{header|F_Sharp|F#}}==

===The Functions===

<lang fsharp>

// Generate derangements. Nigel Galloway: July 9th., 2019

let derange n=

let fG n i g=let e=Array.copy n in e.[i]<-n.[g]; e.[g]<-n.[i]; e

let rec derange n g α=seq{

match (α>0,n&&&(1<<<α)=0) with

(true,true)->for i in [0..α-1] do if n&&&(1<<<i)=0 then let g=(fG g α i) in yield! derange (n+(1<<<i)) g (α-1); yield! derange n g (α-1)

|(true,false)->yield! derange n g (α-1)

|(false,false)->yield g

|_->()}

derange 0 [|1..n|] (n-1)

</lang>

===The Task===

<lang fsharp>

derange 4 |> Seq.iter(printfn "%A");;

</lang>

{{out}}

<pre>

[|4; 3; 2; 1|]

[|2; 3; 4; 1|]

[|3; 4; 2; 1|]

[|3; 4; 1; 2|]

[|4; 3; 1; 2|]

[|3; 1; 4; 2|]

[|2; 1; 4; 3|]

[|2; 4; 1; 3|]

[|4; 1; 2; 3|]

</pre>

<lang fsharp>

let subFact n=let rec fN n g=match n with 0m->int64(round(g/2.7182818284590452353602874713526624978m))|_->fN (n-1m) (g*n) in if n=0 then 1L else fN (decimal n) 1m

[1..9] |> Seq.iter(fun n->printfn "items=%d !n=%d derangements=%d" n (subFact n) (derange n|>Seq.length))

</lang>

{{out}}

<pre>

items=1 !n=0 derangements=0

items=2 !n=1 derangements=1

items=3 !n=2 derangements=2

items=4 !n=9 derangements=9

items=5 !n=44 derangements=44

items=6 !n=265 derangements=265

items=7 !n=1854 derangements=1854

items=8 !n=14833 derangements=14833

items=9 !n=133496 derangements=133496

</pre>