How to resolve the algorithm Factorial base numbers indexing permutations of a collection step by step in the F# programming language

Published on 12 May 2024 09:40 PM
#F_Sharp

How to resolve the algorithm Factorial base numbers indexing permutations of a collection step by step in the F# programming language

Table of Contents

Problem Statement

You need a random arrangement of a deck of cards, you are sick of lame ways of doing this. This task is a super-cool way of doing this using factorial base numbers. The first 25 factorial base numbers in increasing order are: 0.0.0, 0.0.1, 0.1.0, 0.1.1, 0.2.0, 0.2.1, 1.0.0, 1.0.1, 1.1.0, 1.1.1,1.2.0, 1.2.1, 2.0.0, 2.0.1, 2.1.0, 2.1.1, 2.2.0, 2.2.1, 3.0.0, 3.0.1, 3.1.0, 3.1.1, 3.2.0, 3.2.1, 1.0.0.0 Observe that the least significant digit is base 2 the next base 3, in general an n-digit factorial base number has digits n..1 in base n+1..2. I want to produce a 1 to 1 mapping between these numbers and permutations:- The following psudo-code will do this: Starting with m=0 and Ω, an array of elements to be permutated, for each digit g starting with the most significant digit in the factorial base number. If g is greater than zero, rotate the elements from m to m+g in Ω (see example) Increment m and repeat the first step using the next most significant digit until the factorial base number is exhausted. For example: using the factorial base number 2.0.1 and Ω = 0 1 2 3 where place 0 in both is the most significant (left-most) digit/element. Step 1: m=0 g=2; Rotate places 0 through 2. 0 1 2 3 becomes 2 0 1 3 Step 2: m=1 g=0; No action. Step 3: m=2 g=1; Rotate places 2 through 3. 2 0 1 3 becomes 2 0 3 1 Let me work 2.0.1 and 0123 The task:

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Factorial base numbers indexing permutations of a collection step by step in the F# programming language

Source code in the fsharp programming language

// Factorial base numbers indexing permutations of a collection
// Nigel Galloway: December 7th., 2018
let lN2p (c:int[]) (Ω:'Ω[])=
  let Ω=Array.copy Ω
  let rec fN i g e l=match l-i with 0->Ω.[i]<-e |_->Ω.[l]<-Ω.[l-1]; fN i g e (l-1)// rotate right
  [0..((Array.length Ω)-2)]|>List.iter(fun n->let i=c.[n] in if i>0 then fN n (i+n) Ω.[i+n] (i+n)); Ω
let lN n =
  let    Ω=(Array.length n)
  let fN g=if n.[g]=Ω-g then n.[g]<-0; false else n.[g]<-n.[g]+1; true
  seq{yield n; while [1..Ω]|>List.exists(fun g->fN (Ω-g)) do yield n}


lN [|0;0;0|] |> Seq.iter (fun n->printfn "%A -> %A" n (lN2p n [|0;1;2;3|]));;


let shoe==[|"A♠";"K♠";"Q♠";"J♠";"10♠";"9♠";"8♠";"7♠";"6♠";"5♠";"4♠";"3♠";"2♠";"A♥";"K♥";"Q♥";"J♥";"10♥";"9♥";"8♥";"7♥";"6♥";"5♥";"4♥";"3♥";"2♥";"A♦";"K♦";"Q♦";"J♦";"10♦";"9♦";"8♦";"7♦";"6♦";"5♦";"4♦";"3♦";"2♦";"A♣";"K♣";"Q♣";"J♣";"10♣";"9♣";"8♣";"7♣";"6♣";"5♣";"4♣";"3♣";"2♣";|]
//Random Shuffle
let N=System.Random() in lc2p [|for n in 52..-1..2 do yield N.Next(n)|] shoe|>Array.iter (printf "%s ");printfn ""
//Task Shuffles
lN2p [|39;49;7;47;29;30;2;12;10;3;29;37;33;17;12;31;29;34;17;25;2;4;25;4;1;14;20;6;21;18;1;1;1;4;0;5;15;12;4;3;10;10;9;1;6;5;5;3;0;0;0|] shoe|>Array.iter (printf "%s ");printfn ""
lN2p [|51;48;16;22;3;0;19;34;29;1;36;30;12;32;12;29;30;26;14;21;8;12;1;3;10;4;7;17;6;21;8;12;15;15;13;15;7;3;12;11;9;5;5;6;6;3;4;0;3;2;1|] shoe|>Array.iter (printf "%s ");printfn ""


let g=[|0..10|]
lC 10 |> Seq.map(fun n->lc2p n g) |>  Seq.length

You may also check:How to resolve the algorithm GUI enabling/disabling of controls step by step in the Ring programming language
You may also check:How to resolve the algorithm Semiprime step by step in the Pascal programming language
You may also check:How to resolve the algorithm Sequence: smallest number greater than previous term with exactly n divisors step by step in the R programming language
You may also check:How to resolve the algorithm Convert seconds to compound duration step by step in the AppleScript programming language
You may also check:How to resolve the algorithm Entropy/Narcissist step by step in the J programming language