Factorial base numbers indexing permutations of a collection: Difference between revisions
Content deleted Content added
→{{header|Go}}: Approx. 30% speed-up for 'count only' scenario. |
Corrected per dıscussıon page |
||
Line 1: | Line 1: | ||
{{ |
{{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 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 |
Let me work 2.0.1 and 0123 |
||
step 1 n=0 g=2 |
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 |
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 |
let Ω=Array.copy Ω |
||
let rec fN i g e l=match l-i with 0-> |
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 |
[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]= |
let fN g=if n.[g]=Ω-g then n.[g]<-0; false else n.[g]<-n.[g]+1; true |
||
seq{yield n; while [1.. |
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=[|" |
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#)]]: |