Factorial base numbers indexing permutations of a collection: Difference between revisions

← Older editNewer edit →
Content deleted Content added
PureFox (talk | contribs)
9,506 edits
→‎{{header|Go}}: Approx. 30% speed-up for 'count only' scenario.
Corrected per dıscussıon page
Line 1: Line 1:
{{draft task}}
{{task}}
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.
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
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
Line 31: Line 31:


The following psudo-code will do this:
The following psudo-code will do this:
Starting with n=0 and Ω=an array of elements to be permutated, for each digit g starting with the most significant in the factorial base nubmer
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.

1. if g is greater than zero rotate the elements from n to n+g in Ω (see example)
If g is greater than zero, rotate the elements from m to m+g in Ω (see example)
2. increment n and goto 1 using the next most significant digit until the factorial base number is exhausted.
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
Let me work 2.0.1 and 0123
step 1 n=0 g=2 Ω=2013
step 1 n=0 g=2 Ω=2013
step 2 n=1 g=0 so no action
step 2 n=1 g=0 so no action
step 3 n=2 g=1 Ω=2031
step 3 n=2 g=1 Ω=2031


The task:
The task:
Line 49: Line 55:
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
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
use your function to crate the corresponding permutation of the following shoe of cards:
use your function to crate the corresponding permutation of the following shoe of cards:
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♣
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♣
Finally create your own 51 digit factorial base number and produce the corresponding permutation of the above shoe
Finally create your own 51 digit factorial base number and produce the corresponding permutation of the above shoe
=={{header|F_Sharp|F#}}==
=={{header|F_Sharp|F#}}==
Line 56: Line 62:
// Factorial base numbers indexing permutations of a collection
// Factorial base numbers indexing permutations of a collection
: December 7th., 2018
: December 7th., 2018
let lN2p (c:int[]) (Ω:'Ω[])=
let lN2p (c:int[]) (Ω:'Ω[])=
let Ω=Array.copy Ω
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
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)); Ω
[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 α =
let lN Ω =
let n=Array.zeroCreate α
let n=Array.zeroCreate Ω
let fN g=if n.[g]=α-g then n.[g]<-0; false else n.[g]<-n.[g]+1; true
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}
seq{yield n; while [1..Ω]|>List.exists(fun g->fN (Ω-g)) do yield n}
</lang>
</lang>


Line 100: Line 106:
;Shuffles:
;Shuffles:
<lang fsharp>
<lang fsharp>
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♣";|]
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
//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 ""
let N=System.Random() in lc2p [|for n in 52..-1..2 do yield N.Next(n)|] shoe|>Array.iter (printf "%s ");printfn ""
Line 109: Line 115:
{{out}}
{{out}}
<pre>
<pre>
J♣ Q♦ 10♣ 10♠ 3♥ 7♠ 8♥ 7♥ 8♦ 10♦ 4♥ 9♥ 8♠ K♥ 4♣ 5♥ K♣ Q♥ 9♠ A♦ Q♠ 6♦ K♦ K♠ 2♣ 6♠ 7♦ J♦ 2♥ 5♠ 4♦ 3♦ 6♣ J♥ 9♦ 4♠ 3♣ 2♠ 3♠ 10♥ Q♣ A♥ 2♦ A♠ 7♣ A♣ 9♣ 6♥ 5♦ 5♣ J♠ 8♣
J♣ Q♦ 10♣ 10♠ 3♥ 7♠ 8♥ 7♥ 8♦ 10♦ 4♥ 9♥ 8♠ K♥ 4♣ 5♥ K♣ Q♥ 9♠ A♦ Q♠ 6♦ K♦ K♠ 2♣ 6♠ 7♦ J♦ 2♥ 5♠ 4♦ 3♦ 6♣ J♥ 9♦ 4♠ 3♣ 2♠ 3♠ 10♥ Q♣ A♥ 2♦ A♠ 7♣ A♣ 9♣ 6♥ 5♦ 5♣ J♠ 8♣


A♣ 3♣ 7♠ 4♣ 10♦ 8♦ Q♠ K♥ 2♠ 10♠ 4♦ 7♣ J♣ 5♥ 10♥ 10♣ K♣ 2♣ 3♥ 5♦ J♠ 6♠ Q♣ 5♠ K♠ A♦ 3♦ Q♥ 8♣ 6♦ 9♠ 8♠ 4♠ 9♥ A♠ 6♥ 5♣ 2♦ 7♥ 8♥ 9♣ 6♣ 7♦ A♥ J♦ Q♦ 9♦ 2♥ 3♠ J♥ 4♥ K♦
A♣ 3♣ 7♠4♣ 10♦ 8♦ Q♠K♥ 2♠10♠4♦ 7♣ J♣ 5♥ 10♥ 10♣ K♣ 2♣ 3♥ 5♦ J♠6♠Q♣ 5♠K♠A♦ 3♦ Q♥ 8♣ 6♦ 9♠8♠4♠9♥ A♠6♥ 5♣ 2♦ 7♥ 8♥ 9♣ 6♣ 7♦ A♥ J♦ Q♦ 9♦ 2♥ 3♠J♥ 4♥ K♦


2♣ 5♣ J♥ 4♥ J♠ A♠ 5♥ A♣ 6♦ Q♠ 9♣ 3♦ Q♥ J♣ 10♥ K♣ 10♣ 5♦ 7♥ 10♦ 3♠ 8♥ 10♠ 7♠ 6♥ 5♠ K♥ 4♦ A♥ 4♣ 2♥ 9♦ Q♣ 8♣ 7♦ 6♣ 3♥ 6♠ 7♣ 2♦ J♦ 9♥ A♦ Q♦ 8♦ 4♠ K♦ K♠ 3♣ 2♠ 8♠ 9♠</pre>
2♣ 5♣ J♥ 4♥ Jâ™ Aâ™ 5♥ A♣ 6♦ Qâ™ 9♣ 3♦ Q♥ J♣ 10♥ K♣ 10♣ 5♦ 7♥ 10♦ 3â™ 8♥ 10â™ 7â™ 6♥ 5â™ K♥ 4♦ A♥ 4♣ 2♥ 9♦ Q♣ 8♣ 7♦ 6♣ 3♥ 6â™ 7♣ 2♦ J♦ 9♥ A♦ Q♦ 8♦ 4â™ K♦ Kâ™ 3♣ 2â™ 8â™ 9â™
</pre>


;Comparıson wıth [[http://www.rosettacode.org/wiki/Permutations#F.23 Permutations(F#)]]:
;Comparıson wıth [[http://www.rosettacode.org/wiki/Permutations#F.23 Permutations(F#)]]:
Retrieved from "https://rosettacode.org/wiki/Factorial_base_numbers_indexing_permutations_of_a_collection"