Factorial base numbers indexing permutations of a collection: Difference between revisions
m →{{header|zkl}}: fix part 4 |
m →{{header|zkl}}: change example to show hit max base |
||
Line 279: | Line 279: | ||
<pre> |
<pre> |
||
Part 4: Generate a random shuffle: |
Part 4: Generate a random shuffle: |
||
36.21.48.31.19.37.16.39.43.1.27.23.30.22.14.32.31.2.27.11.5.24.28.20.23.20.17.19.23.13.11.12.3.12.1.0.11.1.8.10.6.2.8.3.7.1.1.4.2.2.1 |
|||
4♦6♥3♣8♦8♥Q♣J♥8♣2♣K♠9♦K♦2♦A♦Q♥9♣10♣J♠A♣A♥7♠3♦5♣10♦K♣7♦2♥6♦4♣7♥10♥5♥9♠3♥Q♠A♠J♦8♠4♥J♣K♥5♠7♣3♠6♣6♠4♠5♦9♥Q♦2♠10♠ |
|||
9♠6♥5♣10♣A♦J♣3♠A♣10♦8♥4♣4♦8♠7♥J♥3♦5♠9♥Q♣A♥K♠K♦J♦3♥2♦2♠9♦8♣Q♥7♣8♦10♠A♠J♠4♥5♥6♣K♣4♠2♥6♠7♠6♦2♣7♦9♣K♥Q♦5♦Q♠3♣10♥ |
|||
</pre> |
</pre> |
Revision as of 18:47, 9 December 2018
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:-
0.0.0 -> 0123 0.0.1 -> 0132 0.1.0 -> 0213 0.1.1 -> 0231 0.2.0 -> 0312 0.2.1 -> 0321 1.0.0 -> 1023 1.0.1 -> 1032 1.1.0 -> 1203 1.1.1 -> 1230 1.2.0 -> 1302 1.2.1 -> 1320 2.0.0 -> 2013 2.0.1 -> 2031 2.1.0 -> 2103 2.1.1 -> 2130 2.2.0 -> 2301 2.2.1 -> 2310 3.0.0 -> 3012 3.0.1 -> 3021 3.1.0 -> 3102 3.1.1 -> 3120 3.2.0 -> 3201 3.2.1 -> 3210
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 1. if g is greater than zero rotate the elements from n to n+g in Ω (see example) 2. increment n and goto 1 using the next most significant digit until the factorial base number is exhausted.
Let me work 2.0.1 and 0123
step 1 n=0 g=2 Ω=2013 step 2 n=1 g=0 so no action step 3 n=2 g=1 Ω=2031
The task:
First use your function to recreate the above table. Secondly use your function to generate all permutaions of 11 digits, perhaps count them don't display them, compare this method with methods in rc's permutations task. Thirdly here following are two ramdom 51 digit factorial base numbers I prepared earlier: 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 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: 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
F#
- The Functıons
<lang fsharp> // Factorial base numbers indexing permutations of a collection
- 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 α =
let n=Array.zeroCreate α 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}
</lang>
- Re-create the table
<lang fsharp> lN 3 |> Seq.iter (fun n->printfn "%A -> %A" n (lN2p n [|0;1;2;3|]));; </lang>
- Output:
[|0; 0; 0|] -> [|0; 1; 2; 3|] [|0; 0; 1|] -> [|0; 1; 3; 2|] [|0; 1; 0|] -> [|0; 2; 1; 3|] [|0; 1; 1|] -> [|0; 2; 3; 1|] [|0; 2; 0|] -> [|0; 3; 1; 2|] [|0; 2; 1|] -> [|0; 3; 2; 1|] [|1; 0; 0|] -> [|1; 0; 2; 3|] [|1; 0; 1|] -> [|1; 0; 3; 2|] [|1; 1; 0|] -> [|1; 2; 0; 3|] [|1; 1; 1|] -> [|1; 2; 3; 0|] [|1; 2; 0|] -> [|1; 3; 0; 2|] [|1; 2; 1|] -> [|1; 3; 2; 0|] [|2; 0; 0|] -> [|2; 0; 1; 3|] [|2; 0; 1|] -> [|2; 0; 3; 1|] [|2; 1; 0|] -> [|2; 1; 0; 3|] [|2; 1; 1|] -> [|2; 1; 3; 0|] [|2; 2; 0|] -> [|2; 3; 0; 1|] [|2; 2; 1|] -> [|2; 3; 1; 0|] [|3; 0; 0|] -> [|3; 0; 1; 2|] [|3; 0; 1|] -> [|3; 0; 2; 1|] [|3; 1; 0|] -> [|3; 1; 0; 2|] [|3; 1; 1|] -> [|3; 1; 2; 0|] [|3; 2; 0|] -> [|3; 2; 0; 1|] [|3; 2; 1|] -> [|3; 2; 1; 0|]
- Shuffles
<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♣";|] //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 "" </lang>
- Output:
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♦ 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â™
- Comparıson wıth [Permutations(F#)]
<lang fsharp> let g=[|0..10|] lC 10 |> Seq.map(fun n->lc2p n g) |> Seq.length </lang>
- Output:
Real: 00:01:08.430, CPU: 00:01:08.970, GC gen0: 9086, gen1: 0 val it : int = 39916800
8GB of memory is insufficient for rc's perm task
Perl 6
Using my interpretation of the task instructions as shown on the discussion page.
<lang perl6>sub postfix:<!> (Int $n) { (flat 1, [\*] 1..*)[$n] }
multi base (Int $n is copy, 'F', $length? is copy) {
constant @fact = [\*] 1 .. *; my $i = $length // @fact.first: * > $n, :k; my $f; [ @fact[^$i].reverse.map: { ($n, $f) = $n.polymod($_); $f } ]
}
sub fpermute (@a is copy, *@f) { (^@f).map: { @a[$_ .. $_ + @f[$_]].=rotate(-1) }; @a }
put "Part 1: Generate table"; put $_.&base('F', 3).join('.') ~ ' -> ' ~ [0,1,2,3].&fpermute($_.&base('F', 3)).join for ^24;
put "\nPart 2: Compare 11! to 11! " ~ '¯\_(ツ)_/¯';
- This is kind of a weird request. Since we don't actually need to _generate_
- the permutations, only _count_ them: compare count of 11! vs count of 11!
put "11! === 11! : {11! === 11!}";
put "\nPart 3: Generate the given task shuffles"; my \Ω = <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♣
>;
my @books = <
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 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
>;
put "Original deck:"; put Ω.join;
put "\n$_\n" ~ Ω[(^Ω).&fpermute($_.split: '.')].join for @books;
put "\nPart 4: Generate a random shuffle"; my @shoe = (+Ω … 2).map: { (^$_).pick }; put @shoe.join('.'); put Ω[(^Ω).&fpermute(@shoe)].join;
put "\nSeems to me it would be easier to just say: Ω.pick(*).join"; put Ω.pick(*).join;</lang>
- Output:
Part 1: Generate table 0.0.0 -> 0123 0.0.1 -> 0132 0.1.0 -> 0213 0.1.1 -> 0231 0.2.0 -> 0312 0.2.1 -> 0321 1.0.0 -> 1023 1.0.1 -> 1032 1.1.0 -> 1203 1.1.1 -> 1230 1.2.0 -> 1302 1.2.1 -> 1320 2.0.0 -> 2013 2.0.1 -> 2031 2.1.0 -> 2103 2.1.1 -> 2130 2.2.0 -> 2301 2.2.1 -> 2310 3.0.0 -> 3012 3.0.1 -> 3021 3.1.0 -> 3102 3.1.1 -> 3120 3.2.0 -> 3201 3.2.1 -> 3210 Part 2: Compare 11! to 11! ¯\_(ツ)_/¯ 11! === 11! : True Part 3: Generate the given task shuffles Original deck: 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♣ 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 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♦ 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 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♠ Part 4: Generate a random shuffle 47.9.46.16.28.8.36.27.29.1.9.27.1.16.21.22.28.34.30.8.19.27.18.22.3.25.15.20.12.14.8.9.11.1.4.0.3.5.4.2.2.10.8.1.6.1.2.4.1.2.1 6♣5♠5♣10♥10♦6♠K♣9♦6♦K♠2♠5♦Q♠5♥Q♦8♦J♣2♣8♣A♥K♦9♣A♦2♦9♠4♣3♥A♣7♥2♥Q♥9♥4♥J♠4♠A♠3♠8♥J♥7♠K♥3♣10♣8♠Q♣6♥7♦7♣J♦3♦4♦10♠ Seems to me it would be easier to just say: Ω.pick(*).join 5♦3♠8♦10♦2♥7♠7♦Q♦A♠5♣8♣Q♠4♠2♦K♦5♠Q♥7♣10♠2♠K♠J♣9♣3♣4♥3♥4♦3♦Q♣2♣4♣J♦9♠A♣J♠10♣6♣9♦6♠10♥6♥9♥J♥7♥K♥A♦8♠A♥5♥8♥K♣6♦
zkl
<lang zkl>fcn fpermute(omega,num){ // eg (0,1,2,3), (0,0,0)..(3,2,1)
omega=omega.copy(); // omega gonna be mutated foreach m,g in ([0..].zip(num)){ if(g) omega.insert(m,omega.pop(m+g)) } omega
}</lang> <lang zkl>println("Part 1: Generate table:"); foreach a,b,c in (4,3,2){
println("%d.%d.%d --> %s".fmt(a,b,c,fpermute(L(0,1,2,3),T(a,b,c)).concat()));
}</lang>
- Output:
Part 1: Generate table: 0.0.0 --> 0123 0.0.1 --> 0132 0.1.0 --> 0213 0.1.1 --> 0231 0.2.0 --> 0312 0.2.1 --> 0321 1.0.0 --> 1023 1.0.1 --> 1032 1.1.0 --> 1203 1.1.1 --> 1230 1.2.0 --> 1302 1.2.1 --> 1320 2.0.0 --> 2013 2.0.1 --> 2031 2.1.0 --> 2103 2.1.1 --> 2130 2.2.0 --> 2301 2.2.1 --> 2310 3.0.0 --> 3012 3.0.1 --> 3021 3.1.0 --> 3102 3.1.1 --> 3120 3.2.0 --> 3201 3.2.1 --> 3210
<lang zkl>println("Part 3: Generate the given task shuffles:"); deck:=List(); foreach s,c in ("\u2660 \u2665 \u2666 \u2663".split(),
"A K Q J 10 9 8 7 6 5 4 3 2".split()){ deck.append(c+s) }
books:=List(
"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", "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") .apply(fcn(s){ s.split(".").apply("toInt") });
foreach book in (books){ println(fpermute(deck,book).concat("")); }</lang>
- Output:
Part 3: Generate the given task shuffles: 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♠
<lang zkl>println("Part 4: Generate a random shuffle:"); r:=[52..2,-1].pump(List,(0).random); println(r.concat("."),"\n",fpermute(deck,r).concat(""));</lang>
- Output:
Part 4: Generate a random shuffle: 36.21.48.31.19.37.16.39.43.1.27.23.30.22.14.32.31.2.27.11.5.24.28.20.23.20.17.19.23.13.11.12.3.12.1.0.11.1.8.10.6.2.8.3.7.1.1.4.2.2.1 4♦6♥3♣8♦8♥Q♣J♥8♣2♣K♠9♦K♦2♦A♦Q♥9♣10♣J♠A♣A♥7♠3♦5♣10♦K♣7♦2♥6♦4♣7♥10♥5♥9♠3♥Q♠A♠J♦8♠4♥J♣K♥5♠7♣3♠6♣6♠4♠5♦9♥Q♦2♠10♠