Factorial base numbers indexing permutations of a collection
You are encouraged to solve this task according to the task description, using any language you may know.
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 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
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
ALGOL 68
BEGIN # factorial base numbers indexing permutations of a collection #
# - translated from the Phix/FreeBASIC samples #
PROC print sequence = ( []INT s )VOID:
BEGIN
print( ( " " ) );
IF UPB s >= LWB s THEN
FOR j FROM LWB s TO UPB s DO
print( ( whole( s[ j ], 0 ) ) )
OD
FI;
print( ( newline ) )
END # print sequence # ;
PROC factorial = ( INT n )LONG INT: IF n <= 1 THEN 1 ELSE n * factorial( n - 1 ) FI;
PROC tagset = ( INT n )[]INT:
BEGIN
[ 1 : n ]INT result;
FOR i TO n DO result[ i ] := i OD;
result
END # tagset # ;
PROC show cards = ( []INT s )VOID:
BEGIN
STRING cards = "AKQJT98765432", suits = "SHDC";
FOR i FROM LWB s TO UPB s DO
INT c = s[ i ] - 1;
STRING card = cards[ ( c MOD 13 ) + 1 ] + suits[ ( c OVER 13 ) + 1 ];
print( ( card, IF i MOD 13 = 0 OR i = UPB s THEN newline ELSE space FI ) )
OD;
print( ( newline ) )
END # show cards # ;
PROC fperm = ( []INT fbn, omega )[]INT:
BEGIN
INT m := 0;
[ LWB omega : UPB omega ]INT result := omega;
FOR i FROM LWB fbn TO UPB fbn DO
INT g = fbn[ i ];
IF g > 0 THEN
INT tmp = result[ m + g + 1 ];
FOR j FROM m + g + 1 BY -1 TO m + 2 DO
result[ j ] := result[ j - 1 ]
OD;
result[ m + 1 ] := tmp
FI;
m +:= 1
OD;
result
END # fperm # ;
PROC factorial base numbers = ( INT size, BOOL count only )[]INT:
BEGIN
[ 1 : size ]INT res; FOR i TO size DO res[ i ] := 0 OD;
# count the number of results #
INT count := 0;
FOR n FROM 0 WHILE INT radix := 2;
INT k := n;
WHILE k > 0 DO
k OVERAB radix;
radix +:= 1
OD;
radix <= size + 2
DO count +:= 1
OD;
[ 1 : IF count only THEN 0 ELSE count * size FI ]INT results;
FOR i TO UPB results DO results[ i ] := 0 OD;
INT results pos := - size;
IF NOT count only THEN
# want the results, not just a count #
FOR n FROM 0 WHILE INT radix := 2;
INT k := n;
WHILE k > 0 DO
IF NOT count only AND radix <= size + 1 THEN
res[ size - radix + 2 ] := k MOD radix
FI;
k OVERAB radix;
radix +:= 1
OD;
radix <= size + 2
DO count +:= 1;
results pos +:= size;
results[ results pos + 1 : results pos + size ] := res
OD
FI;
IF count only THEN count ELSE results FI
END # factorial base numbers # ;
# Generate random factorial base number sequence #
PROC randfbn51 = []INT:
BEGIN
[ 1 : 51 ]INT fbn51;
FOR i TO 51 DO fbn51[ i ] := ENTIER ( next random * ( 52 - i ) ) + 1 OD;
fbn51
END # randfbn51 # ;
BEGIN
INT size = 3;
[]INT fbns = factorial base numbers( size, FALSE );
[]INT omega = ( 0, 1, 2, 3 );
FOR i TO UPB fbns OVER size DO
FOR j TO size DO
print( ( whole( fbns[ ( i - 1 ) * size + j ], 0 ), IF j = size THEN "" ELSE "." FI ) )
OD;
print( ( " ->" ) );
[ 1 : size ]INT tmp;
FOR j TO size DO tmp[ j ] := fbns[ ( i - 1 ) * size + j ] OD;
[]INT result = fperm( tmp, omega );
print sequence( result )
OD;
print( ( newline ) );
[]INT count = factorial base numbers( 10, TRUE );
print( ( "Permutations generated = ", whole( ( count )[ 1 ], 0 ), newline ) );
print( ( " compared to 11! which = ", whole( factorial( 11 ), 0 ), newline ) );
print( ( newline ) );
[][]INT fbn51s = ( ( 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
)
, rand fbn51
);
# Show all card arrangements #
FOR i FROM LWB fbn51s TO UPB fbn51s DO show cards( fperm( fbn51s[ i ], tagset( 52 ) ) ) OD
END
END- Output:
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 Permutations generated = 39916800 compared to 11! which = 39916800 AC 3C 7S 4C TD 8D QS KH 2S TS 4D 7C JC 5H TH TC KC 2C 3H 5D JS 6S QC 5S KS AD 3D QH 8C 6D 9S 8S 4S 9H AS 6H 5C 2D 7H 8H 9C 6C 7D AH JD QD 9D 2H 3S JH 4H KD 2C 5C JH 4H JS AS 5H AC 6D QS 9C 3D QH JC TH KC TC 5D 7H TD 3S 8H TS 7S 6H 5S KH 4D AH 4C 2H 9D QC 8C 7D 6C 3H 6S 7C 2D JD 9H AD QD 8D 4S KD KS 3C 2S 8S 9S TD 6D 5D 9S 8D KH 6S KD TC 3D 4D 4S 3S JH 4C 6C KC 4H 2S QC 6H KS JC 7D 9H 7C AD QS 3C 5H 5S 2H 5C QH 3H AH AC JS TH 7S JD 9C 7H 8S 2C 2D TS QD 8H 9D 8C AS
AppleScript
It's not clear from the description what part of the four subtasks "your function" is supposed to handle. It's also unclear whether "generate all permutaions of 11 digits" means "generate all 479,001,600 11-digit factorial base numbers" or "generate all permutations of an 11-integer array using the 39,916,800 10-digit factorial base numbers." However, both of the latter are out of the question with AppleScript.
-- Permutate a list according to a given factorial base number.
on FBNShuffle(|Ω|, fbn)
set astid to AppleScript's text item delimiters
set AppleScript's text item delimiters to "."
set fbnDigits to fbn's text items
set AppleScript's text item delimiters to astid
repeat with m from 1 to (count fbnDigits)
set m_plus_g to m + (item m of fbnDigits)
set v to item m_plus_g of |Ω|
repeat with i from (m_plus_g - 1) to m by -1
set item (i + 1) of |Ω| to item i of |Ω|
end repeat
set item m of |Ω| to v
end repeat
end FBNShuffle
-- Generate all the factorial base numbers having a given number of digits.
on generateFBNs(numberOfDigits)
script o
property partials : {}
property permutations : {}
end script
if (numberOfDigits > 0) then
repeat with i from 0 to numberOfDigits
set end of o's permutations to (i as text)
end repeat
repeat with maxDigit from (numberOfDigits - 1) to 1 by -1
set o's partials to o's permutations
set o's permutations to {}
repeat with i from 1 to (count o's partials)
set thisPartial to item i of o's partials
repeat with j from 0 to maxDigit
set end of o's permutations to (thisPartial & ("." & j))
end repeat
end repeat
end repeat
end if
return o's permutations
end generateFBNs
-- Generate a random factorial base number having a given number of digits.
on generateRandomFBN(numberOfDigits)
set fbnDigits to {}
repeat with maxDigit from numberOfDigits to 1 by -1
set end of fbnDigits to (random number maxDigit)
end repeat
set astid to AppleScript's text item delimiters
set AppleScript's text item delimiters to "."
set fbn to fbnDigits as text
set AppleScript's text item delimiters to astid
return fbn
end generateRandomFBN
(* Test code *)
set astid to AppleScript's text item delimiters
set AppleScript's text item delimiters to ""
-- 1. Reproduce table of {0, 1, 2, 3} permutations
set output to {"1. Reproduce table of {0, 1, 2, 3} permutations:"}
set elements to {0, 1, 2, 3}
set listOfFBNs to generateFBNs((count elements) - 1)
repeat with fbn in listOfFBNs
copy elements to |Ω|
FBNShuffle(|Ω|, fbn)
set end of output to fbn's contents & " -> " & |Ω|
end repeat
-- 2. Generate and count all 11-digit permutations. No way!
set end of output to ""
set numberOfDigits to 11
set numberOfPermutations to 1
repeat with base from 2 to (numberOfDigits + 1)
set numberOfPermutations to numberOfPermutations * base
end repeat
set end of output to "2. " & numberOfDigits & "-digit factorial base numbers have " & (numberOfPermutations div 1) & " possible permutations!"
-- 3. Card shoe permutations with the given FBNs.
set end of output to ""
set shoe to {"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♣"}
copy shoe to shoe1
copy shoe to shoe2
set fbn1 to "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"
set fbn2 to "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"
FBNShuffle(shoe1, fbn1)
FBNShuffle(shoe2, fbn2)
set end of output to "3. Shuffle " & shoe
set end of output to "With " & fbn1 & (linefeed & " -> " & shoe1)
set end of output to "With " & fbn2 & (linefeed & " -> " & shoe2)
-- 4. Card shoe permutation with randomly generated FBN.
set end of output to ""
set fbn3 to generateRandomFBN(51)
FBNShuffle(shoe, fbn3)
set end of output to "4. With randomly generated " & fbn3 & (linefeed & " -> " & shoe)
set AppleScript's text item delimiters to linefeed
set output to output as text
set AppleScript's text item delimiters to astid
return output
- Output:
"1. Reproduce table of {0, 1, 2, 3} 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
2. 11-digit factorial base numbers have 479001600 possible permutations!
3. Shuffle 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♣
With 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♦
With 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♠
4. With randomly generated 46.27.4.19.47.40.26.27.13.32.37.14.37.20.9.15.33.13.16.29.14.11.14.6.8.4.5.13.4.4.14.15.6.17.15.4.5.12.3.0.7.10.7.1.2.1.5.0.2.2.1
-> 7♣K♦10♠7♥2♣10♣J♦9♦K♥2♦8♣J♥5♣3♥4♠8♥6♣10♥4♥J♣6♥A♥2♥7♠3♠9♠6♠8♦8♠5♠4♦A♣9♥4♣Q♣2♠5♥K♣J♠A♠6♦3♣5♦Q♠A♦Q♥9♣K♠7♦3♦10♦Q♦"
C++
#include <cstdint>
#include <iostream>
#include <random>
#include <sstream>
#include <string>
#include <vector>
std::string stringify(const std::string& text) {
return text;
}
std::string stringify(const uint32_t& number) {
return std::to_string(number);
}
template<typename T>
std::string to_string(const std::vector<T>& factoradic, const std::string& delimiter) {
std::string result = "";
for ( uint32_t i = 0; i < factoradic.size() - 1; ++i ) {
result += stringify(factoradic[i]) + delimiter;
}
result += stringify(factoradic.back());
return result;
}
uint32_t factorial(const uint32_t& n) {
uint32_t factorial = 1;
for ( uint32_t i = 2; i <= n; ++i ) {
factorial *= i;
}
return factorial;
}
void increment(std::vector<uint32_t>& factoradic) {
uint64_t index = factoradic.size() - 1;
while ( index >= 0 && factoradic[index] == factoradic.size() - index ) {
factoradic[index] = 0;
index -= 1;
}
if ( index >= 0 ) {
factoradic[index] += 1;
}
}
std::vector<std::string> split_string(const std::string& text, const char& delimiter) {
std::vector<std::string> lines;
std::istringstream stream(text);
std::string line;
while ( std::getline(stream, line, delimiter) ) {
if ( ! line.empty() ) {
lines.emplace_back(line);
}
}
return lines;
}
std::vector<uint32_t> convert_to_vector_of_integer(const std::string& text) {
std::vector<uint32_t> result = { };
std::vector<std::string> numbers = split_string(text, '.');
for ( const std::string& number : numbers ) {
result.emplace_back(std::stoi(number));
}
return result;
}
template <typename T>
std::vector<T> permutation(std::vector<T> elements, const std::vector<uint32_t>& factoradic) {
uint32_t m = 0;
for ( const uint32_t& g : factoradic ) {
const T element = elements[m + g];
elements.erase(elements.begin() + m + g);
elements.insert(elements.begin() + m, element);
m += 1;
}
return elements;
}
int main() {
// Part 1
std::vector<uint32_t> elements = convert_to_vector_of_integer("0.1.2.3");
std::vector<uint32_t> factoradic = convert_to_vector_of_integer("0.0.0");
for ( uint32_t i = 0; i < factorial(4); ++i ) {
std::vector<uint32_t> rotated = permutation<uint32_t>(elements, factoradic);
std::cout << to_string<uint32_t>(factoradic, ".") + " --> " + to_string<uint32_t>(rotated, " ") << std::endl;
increment(factoradic);
}
std::cout << std::endl;
// Part 2
std::cout << "Generating the permutations of 11 digits:" << std::endl;
const uint32_t limit = factorial(11);
elements = convert_to_vector_of_integer("0.1.2.3.4.5.6.7.8.9.10");
factoradic = convert_to_vector_of_integer("0.0.0.0.0.0.0.0.0.0");
for ( uint32_t i = 0; i < limit; ++i ) {
std::vector<uint32_t> rotated = permutation<uint32_t>(elements, factoradic);
if ( i < 3 || i > limit - 4 ) {
std::cout << to_string<uint32_t>(factoradic, ".") + " --> " + to_string<uint32_t>(rotated, " ")
<< std::endl;
} else if ( i == 3 ) {
std::cout << " [ ... ] " << std::endl;
}
increment(factoradic);
}
std::cout << "Number of permutations is 11! = " << limit << std::endl << std::endl;
// Part 3
std::vector<std::string> codes = { "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" };
std::vector<std::string> 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♣"
};
std::cout << "Original deck of cards:" << std::endl;
std::cout << to_string<std::string>(cards, " ") << std::endl << std::endl;
std::cout << "Task shuffles:" << std::endl;
for ( const std::string& code : codes ) {
std::cout << code + " --> " << std::endl;
factoradic = convert_to_vector_of_integer(code);
std::cout << to_string<std::string>(permutation<std::string>(cards, factoradic), " ")
<< std::endl << std::endl;
}
std::cout << "Random shuffle:" << std::endl;;
std::random_device random;
std::mt19937 generator(random());
factoradic.clear();
for ( uint32_t i = 0; i < cards.size() - 1; ++i ) {
std::uniform_int_distribution<uint64_t> distribution(0, cards.size() - i - 1);
factoradic.emplace_back(distribution(generator));
}
std::cout << to_string<uint32_t>(factoradic, ".") + " --> " << std::endl;
std::cout << to_string<std::string>(permutation<std::string>(cards, factoradic), " ") << std::endl;
}
- 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 Generating the permutations of 11 digits: 0.0.0.0.0.0.0.0.0.0 --> 0 1 2 3 4 5 6 7 8 9 10 0.0.0.0.0.0.0.0.0.1 --> 0 1 2 3 4 5 6 7 8 10 9 0.0.0.0.0.0.0.0.1.0 --> 0 1 2 3 4 5 6 7 9 8 10 [ ... ] 10.9.8.7.6.5.4.3.1.1 --> 10 9 8 7 6 5 4 3 1 2 0 10.9.8.7.6.5.4.3.2.0 --> 10 9 8 7 6 5 4 3 2 0 1 10.9.8.7.6.5.4.3.2.1 --> 10 9 8 7 6 5 4 3 2 1 0 Number of permutations is 11! = 39916800 Original deck 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♣ Task shuffles: 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♠ Random shuffle: 13.47.42.24.33.0.37.23.14.32.5.17.4.11.21.15.21.30.25.22.5.8.20.0.25.23.25.17.21.14.18.4.4.4.7.8.4.11.10.2.2.6.4.7.7.1.1.4.1.2.0 --> A♥ 5♣ 10♣ 2♥ 5♦ A♠ Q♣ A♦ J♥ 2♦ 8♠ 6♥ 9♠ Q♥ 10♦ 5♥ 8♦ 7♣ A♣ 6♦ 6♠ 2♠ 4♦ K♠ 4♣ 8♣ 2♣ 9♦ 9♣ K♦ K♣ 5♠ 4♠ 3♠ 8♥ 4♥ K♥ 3♦ 7♦ 10♠ 7♠ Q♦ 7♥ 6♣ 3♣ J♠ 10♥ J♣ 9♥ J♦ Q♠ 3♥
F#
- The Functıons
// 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}
- Re-create the table
lN [|0;0;0|] |> Seq.iter (fun n->printfn "%A -> %A" n (lN2p n [|0;1;2;3|]));;
- 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
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 ""
- 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#)]
let g=[|0..10|]
lC 10 |> Seq.map(fun n->lc2p n g) |> Seq.length
- 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
Factor
USING: assocs io kernel literals math math.factorials
math.parser math.ranges prettyprint qw random sequences
splitting ;
RENAME: factoradic math.combinatorics.private => _factoradic
RENAME: rotate sequences.extras => _rotate
IN: rosetta-code.factorial-permutations
CONSTANT: shoe $[
qw{ A K Q J 10 9 8 7 6 5 4 3 2 } qw{ ♠ ♥ ♦ ♣ }
[ append ] cartesian-map flip concat
]
! Factor can already make factoradic numbers, but they always
! have a least-significant digit of 0 to remove.
: factoradic ( n -- seq )
_factoradic dup [ drop but-last ] unless-empty ;
! Convert "3.1.2.0" to { 3 1 2 0 }, for example.
: string>factoradic ( str -- seq )
"." split [ string>number ] map ;
! Rotate a subsequence.
! E.g. 0 2 { 3 1 2 0 } (rotate) -> { 2 3 1 0 }.
: (rotate) ( from to seq -- newseq )
[ 1 + ] dip [ snip ] [ subseq ] 3bi -1 _rotate glue ;
! Only rotate a subsequence if from does not equal to.
: rotate ( from to seq -- newseq )
2over = [ 2nip ] [ (rotate) ] if ;
! The pseudocode from the task description
: fpermute ( factoradic -- permutation )
dup length 1 + <iota> swap <enumerated>
[ over + rot rotate ] assoc-each ;
! Use a factoradic number to index permutations of a collection.
: findex ( factoradic seq -- permutation )
[ fpermute ] [ nths concat ] bi* ;
: .f ( seq -- ) [ "." write ] [ pprint ] interleave ; ! Print a factoradic number
: .p ( seq -- ) [ pprint ] each nl ; ! Print a permutation
: show-table ( -- )
"Generate table" print 24
[ factoradic 3 0 pad-head dup .f fpermute " -> " write .p ]
each-integer nl ;
: show-shuffles ( -- )
"Generate given task shuffles" print
"Original deck:" print shoe concat print nl
"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"
[ [ print ] [ string>factoradic shoe findex print nl ] bi ] bi@ ;
: show-random-shuffle ( -- )
"Random shuffle:" print
51 52 [ n! ] bi@ [a,b] random factoradic shoe findex print ;
: main ( -- ) show-table show-shuffles show-random-shuffle ;
MAIN: main
- Output:
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 Generate 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♠ Random shuffle: 5♠K♣K♠4♣8♥7♠Q♥J♦3♠A♦3♣8♣6♥A♥3♥A♣10♥9♠10♣5♣J♣J♠J♥2♣K♥Q♦Q♣7♣6♦7♥2♥5♥2♠10♦2♦A♠4♦8♠4♠7♦10♠6♣9♣5♦4♥8♦9♦3♦6♠K♦9♥Q♠
FreeBASIC
Type Sequence
longi As Integer
dato(1000) As Integer
End Type
Sub printSequence(s As Sequence)
Print " ";
For i As Integer = 1 To s.longi
Print Chr(8) & s.dato(i);
If i < s.longi Then Print ".";
Next i
Print
End Sub
Function factorial(n As Integer) As Longint
If n <= 1 Then Return 1
Return n * factorial(n - 1)
End Function
Function tagset(n As Integer) As Sequence
Dim As Sequence result
result.longi = n
For i As Integer = 1 To n
result.dato(i) = i
Next i
Return result
End Function
Sub showCards(s As Sequence)
Const cards = "AKQJT98765432"
Const suits = "SHDC"
For i As Integer = 1 To s.longi
Dim As Integer c = s.dato(i) - 1
Dim As String card = Mid(cards, (c Mod 13) + 1, 1) + Mid(suits, (c \ 13) + 1, 1)
Print card; Iif(((i Mod 13) = 0 Or i = s.longi), Chr(10), " ");
Next i
Print
End Sub
Function fperm(fbn As Sequence, omega As Sequence) As Sequence
Dim As Integer i, g, tmp, j, m = 0
Dim As Sequence result = omega
For i = 1 To fbn.longi
g = fbn.dato(i)
If g > 0 Then
tmp = result.dato(m + g + 1)
For j = m + g + 1 To m + 2 Step -1
result.dato(j) = result.dato(j - 1)
Next j
result.dato(m + 1) = tmp
End If
m += 1
Next i
result.longi = omega.longi
Return result
End Function
Function factorialBaseNumbers(size As Integer, cntOnly As Integer) As Sequence
Dim As Sequence results
Dim As Integer res(1000)
Dim As Integer cnt, n, radix, k, i
results.longi = 0
cnt = 0
n = 0
Do
radix = 2
k = n
For i = 1 To size
res(i) = 0
Next i
While k > 0
If cntOnly = 0 Andalso radix <= size + 1 Then
res(size - radix + 2) = k Mod radix
End If
k \= radix
radix += 1
Wend
If radix > size + 2 Then Exit Do
cnt += 1
If cntOnly = 0 Then
results.longi += 1
For i = 1 To size
results.dato((results.longi - 1) * size + i) = res(i)
Next i
End If
n += 1
Loop
If cntOnly Then
results.longi = 1
results.dato(1) = cnt
End If
Return results
End Function
' Generate random factorial base number sequence
Function randFBN51() As Sequence
Dim As Sequence fbn51
fbn51.longi = 51
For i As Integer = 1 To 51
fbn51.dato(i) = Int(Rnd * (52 - i)) + 1
Next i
Return fbn51
End Function
' Main program
Randomize Timer
Dim As Integer i, j
Dim As Sequence fbns = factorialBaseNumbers(3, 0)
Dim As Sequence omega
omega.longi = 4
For i = 0 To 3
omega.dato(i + 1) = i
Next i
For i = 1 To fbns.longi
For j = 1 To 3
Print fbns.dato((i-1)*3 + j) & ".";
Next j
Print Chr(8) & " ->";
Dim As Sequence tmp
tmp.longi = 3
For j = 1 To 3
tmp.dato(j) = fbns.dato((i-1)*3 + j)
Next j
Dim As Sequence result = fperm(tmp, omega)
printSequence(result)
Next i
Print
Dim As Sequence cnt = factorialBaseNumbers(10, 1)
Print "Permutations generated ="; cnt.dato(1)
Print " compared to 11! which ="; factorial(11)
Print
Dim As Sequence fbn51s(3)
' First predefined sequence
fbn51s(1).longi = 51
Data 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
For i = 1 To 51: Read fbn51s(1).dato(i): Next
' Second predefined sequence
fbn51s(2).longi = 51
Data 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
For i = 1 To 51: Read fbn51s(2).dato(i): Next
' Third random sequence
fbn51s(3) = randFBN51()
' Show all card arrangements
For i = 1 To 3
showCards(fperm(fbn51s(i), tagset(52)))
Next i
Sleep
- Output:
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 Permutations generated = 39916800 compared to 11! which = 39916800 AC 3C 7S 4C TD 8D QS KH 2S TS 4D 7C JC 5H TH TC KC 2C 3H 5D JS 6S QC 5S KS AD 3D QH 8C 6D 9S 8S 4S 9H AS 6H 5C 2D 7H 8H 9C 6C 7D AH JD QD 9D 2H 3S JH 4H KD 2C 5C JH 4H JS AS 5H AC 6D QS 9C 3D QH JC TH KC TC 5D 7H TD 3S 8H TS 7S 6H 5S KH 4D AH 4C 2H 9D QC 8C 7D 6C 3H 6S 7C 2D JD 9H AD QD 8D 4S KD KS 3C 2S 8S 9S 9D 3H AH KC QC KH TH 5C 3D 6H 9S TC 2S 8S AC 6S JD 9H 7D 8H 4D 3C AD 2D 4H 5D QD 2H 8C TD 4C 4S 7C JS TS 2C JC QH 8D 5S QS 6C JH 7S KD 7H 9C 3S 5H 6D KS AS
Go
package main
import (
"fmt"
"math/rand"
"strconv"
"strings"
"time"
)
func factorial(n int) int {
fact := 1
for i := 2; i <= n; i++ {
fact *= i
}
return fact
}
func genFactBaseNums(size int, countOnly bool) ([][]int, int) {
var results [][]int
count := 0
for n := 0; ; n++ {
radix := 2
var res []int = nil
if !countOnly {
res = make([]int, size)
}
k := n
for k > 0 {
div := k / radix
rem := k % radix
if !countOnly {
if radix <= size+1 {
res[size-radix+1] = rem
}
}
k = div
radix++
}
if radix > size+2 {
break
}
count++
if !countOnly {
results = append(results, res)
}
}
return results, count
}
func mapToPerms(factNums [][]int) [][]int {
var perms [][]int
psize := len(factNums[0]) + 1
start := make([]int, psize)
for i := 0; i < psize; i++ {
start[i] = i
}
for _, fn := range factNums {
perm := make([]int, psize)
copy(perm, start)
for m := 0; m < len(fn); m++ {
g := fn[m]
if g == 0 {
continue
}
first := m
last := m + g
for i := 1; i <= g; i++ {
temp := perm[first]
for j := first + 1; j <= last; j++ {
perm[j-1] = perm[j]
}
perm[last] = temp
}
}
perms = append(perms, perm)
}
return perms
}
func join(is []int, sep string) string {
ss := make([]string, len(is))
for i := 0; i < len(is); i++ {
ss[i] = strconv.Itoa(is[i])
}
return strings.Join(ss, sep)
}
func undot(s string) []int {
ss := strings.Split(s, ".")
is := make([]int, len(ss))
for i := 0; i < len(ss); i++ {
is[i], _ = strconv.Atoi(ss[i])
}
return is
}
func main() {
rand.Seed(time.Now().UnixNano())
// Recreate the table.
factNums, _ := genFactBaseNums(3, false)
perms := mapToPerms(factNums)
for i, fn := range factNums {
fmt.Printf("%v -> %v\n", join(fn, "."), join(perms[i], ""))
}
// Check that the number of perms generated is equal to 11! (this takes a while).
_, count := genFactBaseNums(10, true)
fmt.Println("\nPermutations generated =", count)
fmt.Println("compared to 11! which =", factorial(11))
fmt.Println()
// Generate shuffles for the 2 given 51 digit factorial base numbers.
fbn51s := []string{
"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",
}
factNums = [][]int{undot(fbn51s[0]), undot(fbn51s[1])}
perms = mapToPerms(factNums)
shoe := []rune("A♠K♠Q♠J♠T♠9♠8♠7♠6♠5♠4♠3♠2♠A♥K♥Q♥J♥T♥9♥8♥7♥6♥5♥4♥3♥2♥A♦K♦Q♦J♦T♦9♦8♦7♦6♦5♦4♦3♦2♦A♣K♣Q♣J♣T♣9♣8♣7♣6♣5♣4♣3♣2♣")
cards := make([]string, 52)
for i := 0; i < 52; i++ {
cards[i] = string(shoe[2*i : 2*i+2])
if cards[i][0] == 'T' {
cards[i] = "10" + cards[i][1:]
}
}
for i, fbn51 := range fbn51s {
fmt.Println(fbn51)
for _, d := range perms[i] {
fmt.Print(cards[d])
}
fmt.Println("\n")
}
// Create a random 51 digit factorial base number and produce a shuffle from that.
fbn51 := make([]int, 51)
for i := 0; i < 51; i++ {
fbn51[i] = rand.Intn(52 - i)
}
fmt.Println(join(fbn51, "."))
perms = mapToPerms([][]int{fbn51})
for _, d := range perms[0] {
fmt.Print(cards[d])
}
fmt.Println()
}
- Output:
Random for Part 4:
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 Permutations generated = 39916800 compared to 11! which = 39916800 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♠ 18.14.25.48.18.9.1.16.15.11.41.8.26.19.36.11.8.21.20.15.15.14.27.10.5.24.0.11.18.12.6.8.5.14.16.10.13.13.9.7.11.1.1.7.0.2.5.0.3.0.0 9♥K♥K♦2♣7♥5♠K♠6♥8♥A♥3♣4♠4♦J♦5♣J♥3♠6♦7♦A♦Q♦2♥7♣10♥8♠8♣A♠10♦Q♣8♦2♠4♥6♠J♣6♣3♦10♣9♣5♦3♥4♣J♠10♠A♣Q♠Q♥K♣9♠2♦7♠5♥9♦
Haskell
Factoradic representation of integer numbers in canonical form (with trailing zero).
import Data.List (unfoldr, intercalate)
newtype Fact = Fact [Int]
-- smart constructor
fact :: [Int] -> Fact
fact = Fact . zipWith min [0..] . reverse
instance Show Fact where
show (Fact ds) = intercalate "." $ show <$> reverse ds
toFact :: Integer -> Fact
toFact 0 = Fact [0]
toFact n = Fact $ unfoldr f (1, n)
where
f (b, 0) = Nothing
f (b, n) = let (q, r) = n `divMod` b
in Just (fromIntegral r, (b+1, q))
fromFact :: Fact -> Integer
fromFact (Fact ds) = foldr f 0 $ zip [1..] ds
where
f (b, d) r = r * b + fromIntegral d
λ> toFact 2021 2.4.4.0.2.1.0 λ> fromFact it 2021 λ> fact [2,2,1,0] 2.2.1.0
Correspondence with permutations:
toPermutation :: Fact -> [Int]
toPermutation (Fact ds) = go (reverse ds) [0.. length ds - 1]
where
go [] p = p
go (d:ds) p = case splitAt (fromIntegral d) p of
(a,x:b) -> x : go ds (a++b)
(a,[]) -> a
permute :: [a] -> [Int] -> [a]
permute s p = case splitAt (length s - length p) s of
(s1,s2) -> s1 ++ map (s2 !!) p
λ> toPermutation (fact [4,0,2,1,0]) [4,0,3,2,1] λ> permute "abcde" $ toPermutation (fact [4,0,2,1,0]) "eadcb" λ> permute "abcdefgh" $ toPermutation (fact [4,0,2,1,0]) "abchdgfe"
Given tasks
task1 = do
putStrLn "number\tfactoradic\tpermutation"
mapM_ display [0..23]
where
display n =
let f = toFact n
p = permute "0123" (toPermutation f)
in putStrLn $ show n ++ "\t" ++ show f ++ "\t\t(" ++ p ++ ")"
randomFactDigits seed = zipWith mod (random seed) [1..]
where
random = iterate $ \x -> (x * 1103515245 + 12345) `mod` (2^31-1)
task2 = do
putStrLn "-- First example --"
let n1 = toFact 61988771037597375208735783409763169805823569176280269403732950003152
let crate1 = permute crate $ toPermutation n1
putStrLn $ "Factoradic number:\n" ++ show n1
putStrLn $ "Corresponding crate permutation:\n" ++ unwords crate1
putStrLn "\n-- Second example --"
let n2 = toFact 80576939285541005152259046665383499297948014296200417968998877609223
let crate2 = permute crate $ toPermutation n2
putStrLn $ "Factoradic number:\n" ++ show n2
putStrLn $ "Corresponding crate permutation:\n" ++ unwords crate2
putStrLn "\n-- Random example --"
let n3 = Fact $ take 52 $ randomFactDigits 42
let crate3 = permute crate $ toPermutation n3
putStrLn $ "Factoradic number:\n" ++ show n3
putStrLn $ "Decimal representation of n:\n" ++ show (fromFact n3)
putStrLn $ "Corresponding crate permutation:\n" ++ unwords crate3
where
crate = words "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♣"
λ> task1 number factoradic permutation 0 0 (0123) 1 1.0 (0132) 2 1.0.0 (0213) 3 1.1.0 (0231) 4 2.0.0 (0312) 5 2.1.0 (0321) 6 1.0.0.0 (1023) 7 1.0.1.0 (1032) 8 1.1.0.0 (1203) 9 1.1.1.0 (1230) 10 1.2.0.0 (1302) 11 1.2.1.0 (1320) 12 2.0.0.0 (2013) 13 2.0.1.0 (2031) 14 2.1.0.0 (2103) 15 2.1.1.0 (2130) 16 2.2.0.0 (2301) 17 2.2.1.0 (2310) 18 3.0.0.0 (3012) 19 3.0.1.0 (3021) 20 3.1.0.0 (3102) 21 3.1.1.0 (3120) 22 3.2.0.0 (3201) 23 3.2.1.0 (3210) λ> task2 -- First example -- Factoradic number: 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.0 Corresponding crate permutation: 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♦ -- Second example -- Factoradic number: 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.0 Corresponding crate permutation: 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♠ -- Random example -- Factoradic number: 25.36.42.26.5.9.25.5.38.24.30.19.37.7.5.20.35.28.32.6.22.19.20.14.9.5.21.23.9.22.15.10.10.17.7.8.4.14.8.2.3.8.7.6.2.0.4.2.1.2.0.0 Decimal representation of n: 39898748133187068184262739663110406401085629856403860440579024763898 Corresponding crate permutation: 2♥ 3♦ 9♣ K♦ 9♠ 4♠ J♦ 8♠ 7♣ 10♦ 2♦ 5♥ 4♣ 5♠ 7♠ Q♦ 2♣ Q♣ 5♣ 3♠ 6♦ 9♦ 7♦ 7♥ Q♥ 6♠ J♣ 6♣ 10♥ 3♣ 8♦ 8♥ 6♥ 10♣ K♥ 9♥ 10♠ 8♣ 3♥ Q♠ 2♠ 4♦ 5♦ A♦ J♠ A♠ A♣ J♥ A♥ K♣ K♠ 4♥
J
Generalized base and antibase, and anagrams are j verbs making this project directly solvable.
NB. A is a numerical matrix corresponding to the input and output
A =: _&".;._2[0 :0
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
)
NB. generalized antibase converts the factorial base representation to integers
4 3 2 #. _ 3 {. A
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
EXPECT =: 10 10 10 10#:{:"1 A
NB. the 0 through 23 anagrams of 0 1 2 3 matches our expactation
EXPECT -: (4 3 2 #. _ 3 {. A) A. 0 1 2 3
1
NB. 6 take EXPECT, for you to see what's been matched
6{.EXPECT
0 1 2 3
0 1 3 2
0 2 1 3
0 2 3 1
0 3 1 2
0 3 2 1
Java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.concurrent.ThreadLocalRandom;
import java.util.stream.Collectors;
public final class FactorialBaseNumbersIndexingPermutations {
public static void main(String[] args) {
// Part 1
List<Integer> elements = convertToListInteger("0.1.2.3");
List<Integer> factoradic = convertToListInteger("0.0.0");
for ( int i = 0; i < factorial(4); i++ ) {
List<Integer> rotated = permutation(elements, factoradic);
System.out.println(toString(factoradic, ".") + " --> " + toString(rotated, " "));
increment(factoradic);
}
System.out.println();
// Part 2
System.out.println("Generating the permutations of 11 digits:");
final int limit = factorial(11);
elements = convertToListInteger("0.1.2.3.4.5.6.7.8.9.10");
factoradic = convertToListInteger("0.0.0.0.0.0.0.0.0.0");
for ( int i = 0; i < limit; i++ ) {
List<Integer> rotated = permutation(elements, factoradic);
if ( i < 3 || i > limit - 4 ) {
System.out.println(toString(factoradic, ".") + " --> " + toString(rotated, " "));
} else if ( i == 3 ) {
System.out.println(" [ ... ] ");
}
increment(factoradic);
}
System.out.println("Number of permutations is 11! = " + limit + System.lineSeparator());
// Part 3.
List<String> codes = List.of(
"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" );
List<String> cards = List.of( "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♣" );
System.out.println("Original deck of cards:");
System.out.println(toString(cards, " ") + System.lineSeparator());
System.out.println("Task shuffles:");
for ( String code : codes ) {
System.out.println(code + " --> ");
factoradic = convertToListInteger(code);
System.out.println(toString(permutation(cards, factoradic), " "));
System.out.println();
}
System.out.println("Random shuffle:");
ThreadLocalRandom random = ThreadLocalRandom.current();
factoradic.clear();
for ( int i = 0; i < cards.size() - 1; i++ ) {
factoradic.add(random.nextInt(cards.size() - i));
}
System.out.println(toString(factoradic, ".") + " --> ");
System.out.println(toString(permutation(cards, factoradic), " "));
}
private static <T> List<T> permutation(List<T> elements, List<Integer> factoradic) {
List<T> copy = new ArrayList<T>(elements);
int m = 0;
for ( int g : factoradic ) {
Collections.rotate(copy.subList(m, m + g + 1), 1);
m += 1;
}
return copy;
}
private static void increment(List<Integer> factoradic) {
int index = factoradic.size() - 1;
while ( index >= 0 && factoradic.get(index) == factoradic.size() - index ) {
factoradic.set(index, 0);
index -= 1;
}
if ( index >= 0 ) {
factoradic.set(index, factoradic.get(index) + 1);
}
}
private static List<Integer> convertToListInteger(String text) {
List<Integer> result = new ArrayList<Integer>();
String[] numbers = text.split("\\.");
for ( String number : numbers ) {
result.add(Integer.valueOf(number));
}
return result;
}
private static int factorial(int n) {
int factorial = 1;
for ( int i = 2; i <= n; i++ ) {
factorial *= i;
}
return factorial;
}
private static <T> String toString(List<T> factoradic, String delimiter) {
return factoradic.stream().map(String::valueOf).collect(Collectors.joining(delimiter));
}
}
- Output:
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 Generating the permutations of 11 digits: 0.0.0.0.0.0.0.0.0.0 --> 0 1 2 3 4 5 6 7 8 9 10 0.0.0.0.0.0.0.0.0.1 --> 0 1 2 3 4 5 6 7 8 10 9 0.0.0.0.0.0.0.0.1.0 --> 0 1 2 3 4 5 6 7 9 8 10 [ ... ] 10.9.8.7.6.5.4.3.1.1 --> 10 9 8 7 6 5 4 3 1 2 0 10.9.8.7.6.5.4.3.2.0 --> 10 9 8 7 6 5 4 3 2 0 1 10.9.8.7.6.5.4.3.2.1 --> 10 9 8 7 6 5 4 3 2 1 0 Number of permutations is 11! = 39916800 Original deck 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♣ Task shuffles: 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♠ Random shuffle: 24.45.8.6.12.29.39.31.8.0.25.27.27.5.29.32.4.31.0.1.27.22.3.13.22.13.11.17.7.8.12.5.19.18.10.2.9.12.7.2.6.9.7.6.0.2.2.1.1.0.1.0 --> 3♥ 7♣ 6♠ 8♠ K♥ 7♦ 9♣ 4♦ 4♠ A♠ 9♦ 5♦ 3♦ 7♠ Q♣ 6♣ 9♠ 5♣ K♠ J♠ 10♣ 6♦ 3♠ 4♥ K♣ 2♥ 6♥ 8♦ 10♥ 8♥ Q♦ Q♥ 2♣ 3♣ K♦ 5♠ J♦ J♣ 5♥ 2♠ A♦ 8♣ 2♦ 10♦ Q♠ J♥ 9♥ A♥ 7♥ 10♠ 4♣ A♣
Julia
function makefactorialbased(N, makelist)
listlist = Vector{Vector{Int}}()
count = 0
while true
divisor = 2
makelist && (lis = zeros(Int, N))
k = count
while k > 0
k, r = divrem(k, divisor)
makelist && (divisor <= N + 1) && (lis[N - divisor + 2] = r)
divisor += 1
end
if divisor > N + 2
break
end
count += 1
makelist && push!(listlist, lis)
end
return count, listlist
end
function facmap(factnumbase)
perm = [i for i in 0:length(factnumbase)]
for (n, g) in enumerate(factnumbase)
if g != 0
perm[n:n + g] .= circshift(perm[n:n + g], 1)
end
end
perm
end
function factbasenums()
fcount, factnums = makefactorialbased(3, true)
perms = map(facmap, factnums)
for (i, fn) = enumerate(factnums)
println("$(join(string.(fn), ".")) -> $(join(string(perms[i]), ""))")
end
fcount, _ = makefactorialbased(10, false)
println("\nPermutations generated = $fcount, and 11! = $(factorial(11))\n")
taskrandom = ["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"]
perms = map(s -> facmap([parse(Int, s) for s in split(s, ".")]), taskrandom)
cardshoe = split("A♠K♠Q♠J♠T♠9♠8♠7♠6♠5♠4♠3♠2♠A♥K♥Q♥J♥T♥9♥8♥7♥6♥5♥4♥3♥2♥A♦K♦Q♦J♦T♦9♦8♦7♦6♦5♦4♦3♦2♦A♣K♣Q♣J♣T♣9♣8♣7♣6♣5♣4♣3♣2♣", "")
cards = [cardshoe[2*i+1] * cardshoe[2*i+2] for i in 0:51]
printcardshuffle(t, c, o) = (println(t); for i in 1:length(o) print(c[o[i] + 1]) end; println())
println("\nTask shuffles:")
map(i -> printcardshuffle(taskrandom[i], cards, perms[i]), 1:2)
myran = [rand(collect(0:i)) for i in 51:-1:1]
perm = facmap(myran)
println("\nMy random shuffle:")
printcardshuffle(join(string.(myran), "."), cards, perm)
end
factbasenums()
- 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] Permutations generated = 39916800, and 11! = 39916800 Task shuffles: 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♣T♦8♦Q♠K♥2♠T♠4♦7♣J♣5♥T♥T♣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♣T♥K♣T♣5♦7♥T♦3♠8♥T♠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♠ My random shuffle: 29.18.33.22.0.5.10.1.12.18.3.7.39.7.5.12.8.16.28.4.19.18.19.12.4.15.22.3.13.0.5.16.2.16.0.5.10.11.7.0.2.8.9.4.1.6.0.4.1.0.0 J♦9♥5♦4♥A♠8♠2♠Q♠J♥2♥9♠3♠2♣A♥5♠5♥T♥9♦8♣6♠3♦4♦A♣K♦4♠6♦6♣7♠7♦K♠7♥9♣K♥5♣J♠A♦Q♣T♣8♦T♠6♥7♣3♣T♦8♥4♣Q♥J♣Q♦3♥2♦K♣
Nim
import algorithm, math, random, sequtils, strutils, unicode
# Representation of a factorial base number with N digits.
type FactorialBaseNumber[N: static Positive] = array[N, int]
#---------------------------------------------------------------------------------------------------
func permutation[T](elements: openArray[T]; n: FactorialBaseNumber): seq[T] =
## Return the permutation of "elements" associated to the factorial base number "n".
result = @elements
for m, g in n:
if g > 0:
result.rotateLeft(m.int..(m + g), -1)
#---------------------------------------------------------------------------------------------------
func incr(n: var FactorialBaseNumber): bool =
## Increment a factorial base number.
## Return false if an overflow occurred.
var base = 1
var k = 1
for i in countdown(n.high, 0):
inc base
inc n[i], k
if n[i] >= base:
n[i] = 0
k = 1
else:
k = 0
result = k == 0
#---------------------------------------------------------------------------------------------------
iterator fbnSeq(n: static Positive): auto =
## Yield the successive factorial base numbers of length "n".
var result: FactorialBaseNumber[n]
while true:
yield result
if not incr(result): break
#---------------------------------------------------------------------------------------------------
func `$`(n: FactorialBaseNumber): string {.inline.} =
## Return the string representation of a factorial base number.
n.join(".")
#———————————————————————————————————————————————————————————————————————————————————————————————————
# Part 1.
echo "Mapping between factorial base numbers and permutations:"
for n in fbnSeq(3):
echo n, " → ", "0123".permutation(n).join()
# Part 2.
echo ""
echo "Generating the permutations of 11 digits:"
const Target = fac(11)
var count = 0
for n in fbnSeq(10):
inc count
let perm = "0123456789A".permutation(n)
if count in 1..3 or count in (Target - 2)..Target:
echo n, " → ", perm.join()
elif count == 4:
echo "[...]"
echo "Number of permutations generated: ", count
echo "Number of permutations expected: ", Target
# Part 3.
const
FBNS = [
"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"]
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♣"]
M = Cards.len - 1
var fbns: array[3, FactorialBaseNumber[M]]
# Parse the given factorial base numbers.
for i in 0..1:
for j, n in map(FBNS[i].split('.'), parseInt):
fbns[i][j] = n
# Generate a random factorial base number.
randomize()
for j in 0..fbns[3].high:
fbns[2][j] = rand(0..(M - j))
echo ""
echo "Card permutations:"
for i in 0..2:
echo "– for ", fbns[i], ':'
echo " ", Cards.permutation(fbns[i]).join(" ")
- Output:
Mapping between factorial base 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 Generating the permutations of 11 digits: 0.0.0.0.0.0.0.0.0.0 → 0123456789A 0.0.0.0.0.0.0.0.0.1 → 012345678A9 0.0.0.0.0.0.0.0.1.0 → 0123456798A [...] 10.9.8.7.6.5.4.3.1.1 → A9876543120 10.9.8.7.6.5.4.3.2.0 → A9876543201 10.9.8.7.6.5.4.3.2.1 → A9876543210 Number of permutations generated: 39916800 Number of permutations expected: 39916800 Card permutations: – for 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♦ – for 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♠ – for 34.11.16.24.33.19.10.6.20.1.25.11.22.38.6.32.23.14.26.0.17.12.27.10.1.0.5.5.17.14.17.20.0.8.14.7.4.1.4.2.8.6.7.0.5.2.0.3.1.1.1: 6♦ 3♠ 10♥ A♦ 3♦ 6♥ 4♠ 8♠ 2♥ K♠ 7♦ Q♥ 9♦ 2♣ 6♠ 7♣ 4♦ 5♥ J♣ A♠ J♦ 7♥ 5♣ 9♥ J♠ Q♠ A♥ K♥ Q♣ 2♦ 9♣ 3♣ 10♠ K♦ 10♣ 3♥ J♥ 7♠ 4♥ 2♠ K♣ 5♦ 8♣ 9♠ A♣ Q♦ 5♠ 6♣ 10♦ 8♦ 4♣ 8♥
Perl
use strict;
use warnings;
use feature 'say';
sub fpermute {
my($f,@a) = @_;
my @f = split /\./, $f;
for (0..$#f) {
my @b = @a[$_ .. $_+$f[$_]];
unshift @b, splice @b, $#b, 1; # rotate(-1)
@a[$_ .. $_+$f[$_]] = @b;
}
join '', @a;
}
sub base {
my($n) = @_;
my @digits;
push(@digits, int $n/$_) and $n = $n % $_ for <6 2 1>; # reverse <1! 2! 3!>
join '.', @digits;
}
say 'Generate table';
for (0..23) {
my $x = base($_);
say $x . ' -> ' . fpermute($x, <0 1 2 3>)
}
say "\nGenerate the given task shuffles";
my @omega = qw<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'
);
say "Original deck:";
say join '', @omega;
say "\n$_\n" . fpermute($_,@omega) for @books;
say "\nGenerate a random shuffle";
say my $shoe = join '.', map { int rand($_) } reverse 0..$#omega;
say fpermute($shoe,@omega);
- Output:
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 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♠ Generate a random shuffle 47.33.30.9.2.13.9.43.23.40.11.15.15.1.2.11.23.5.21.30.30.14.27.26.7.20.24.13.10.21.1.10.9.2.10.0.12.11.11.11.10.8.2.0.3.4.4.2.0.1.0.0 6♣7♦10♦5♠Q♠Q♥3♠3♣K♦5♣K♥7♥6♥K♠10♠9♥4♦6♠5♦7♣4♣2♥9♣10♣A♥2♦8♣A♦5♥J♣J♠3♥4♥8♠9♦A♠A♣3♦K♣Q♣6♦J♦4♠9♠10♥Q♦8♦J♥7♠8♥2♠2♣
Phix
with javascript_semantics function fperm(sequence fbn, omega) integer m=0 for i=1 to length(fbn) do integer g = fbn[i] if g>0 then omega[m+1..m+g+1] = omega[m+g+1]&omega[m+1..m+g] end if m += 1 end for return omega end function function factorial_base_numbers(integer size, bool countOnly) -- translation of Go sequence results = {}, res = repeat(0,size) integer count = 0, n = 0 while true do integer radix = 2, k = n while k>0 do if not countOnly and radix <= size+1 then res[size-radix+2] = mod(k,radix) end if k = floor(k/radix) radix += 1 end while if radix > size+2 then exit end if count += 1 if not countOnly then results = append(results, deep_copy(res)) end if n += 1 end while return iff(countOnly?count:results) end function sequence fbns = factorial_base_numbers(3,false) for i=1 to length(fbns) do printf(1,"%v -> %v\n",{fbns[i],fperm(fbns[i],{0,1,2,3})}) end for printf(1,"\n") integer count = factorial_base_numbers(10,true) printf(1,"Permutations generated = %d\n", count) printf(1," versus factorial(11) = %d\n", factorial(11)) procedure show_cards(sequence s) printf(1,"\n") for i=1 to length(s) do integer c = s[i]-1 string sep = iff(mod(i,13)=0 or i=length(s)?"\n":" ") puts(1,"AKQJT98765432"[mod(c,13)+1]&"SHDC"[floor(c/13)+1]&sep) end for end procedure function rand_fbn51() sequence fbn51 = repeat(0,51) for i=1 to 51 do fbn51[i] = rand(52-i) end for return fbn51 end function sequence fbn51s = {{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}, rand_fbn51()} for i=1 to length(fbn51s) do show_cards(fperm(fbn51s[i],tagset(52))) end for
- 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}
Permutations generated = 39916800
versus factorial(11) = 39916800
AC 3C 7S 4C TD 8D QS KH 2S TS 4D 7C JC
5H TH TC KC 2C 3H 5D JS 6S QC 5S KS AD
3D QH 8C 6D 9S 8S 4S 9H AS 6H 5C 2D 7H
8H 9C 6C 7D AH JD QD 9D 2H 3S JH 4H KD
2C 5C JH 4H JS AS 5H AC 6D QS 9C 3D QH
JC TH KC TC 5D 7H TD 3S 8H TS 7S 6H 5S
KH 4D AH 4C 2H 9D QC 8C 7D 6C 3H 6S 7C
2D JD 9H AD QD 8D 4S KD KS 3C 2S 8S 9S
JS 4H JD 9H 2C 9C 3C KH 9S TH 6D 5S 3H
2H 3S JH 5H QD 4C 7D 4S QC 7C TS 5C 6H
KS 5D QH 2S AD AC 7S QS TC JC 7H 6C 8H
KC 9D 4D 8D KD 6S TD AH 8C 2D 8S 3D AS
Python
"""
http://rosettacode.org/wiki/Factorial_base_numbers_indexing_permutations_of_a_collection
https://en.wikipedia.org/wiki/Factorial_number_system
"""
import math
def apply_perm(omega,fbn):
"""
omega contains a list which will be permuted (scrambled)
based on fbm.
fbm is a list which represents a factorial base number.
This function just translates the pseudo code in the
Rosetta Code task.
"""
for m in range(len(fbn)):
g = fbn[m]
if g > 0:
# do rotation
# save last number
new_first = omega[m+g]
# move numbers right
omega[m+1:m+g+1] = omega[m:m+g]
# put last number first
omega[m] = new_first
return omega
def int_to_fbn(i):
"""
convert integer i to factorial based number
"""
current = i
divisor = 2
new_fbn = []
while current > 0:
remainder = current % divisor
current = current // divisor
new_fbn.append(remainder)
divisor += 1
return list(reversed(new_fbn))
def leading_zeros(l,n):
"""
If list l has less than n elements returns l with enough 0 elements
in front of the list to make it length n.
"""
if len(l) < n:
return(([0] * (n - len(l))) + l)
else:
return l
def get_fbn(n):
"""
Return the n! + 1 first Factorial Based Numbers starting with zero.
"""
max = math.factorial(n)
for i in range(max):
# from Wikipedia article
current = i
divisor = 1
new_fbn = int_to_fbn(i)
yield leading_zeros(new_fbn,n-1)
def print_write(f, line):
"""
prints to console and
output file f
"""
print(line)
f.write(str(line)+'\n')
def dot_format(l):
"""
Take a list l that is a factorial based number
and returns it in dot format.
i.e. [0, 2, 1] becomes 0.2.1
"""
# empty list
if len(l) < 1:
return ""
# start with just first element no dot
dot_string = str(l[0])
# add rest if any with dots
for e in l[1:]:
dot_string += "."+str(e)
return dot_string
def str_format(l):
"""
Take a list l and returns a string
of those elements converted to strings.
"""
if len(l) < 1:
return ""
new_string = ""
for e in l:
new_string += str(e)
return new_string
with open("output.html", "w", encoding="utf-8") as f:
f.write("<pre>\n")
# first print list
omega=[0,1,2,3]
four_list = get_fbn(4)
for l in four_list:
print_write(f,dot_format(l)+' -> '+str_format(apply_perm(omega[:],l)))
print_write(f," ")
# now generate this output:
#
# Permutations generated = 39916800
# compared to 11! which = 39916800
num_permutations = 0
for p in get_fbn(11):
num_permutations += 1
if num_permutations % 1000000 == 0:
print_write(f,"permutations so far = "+str(num_permutations))
print_write(f," ")
print_write(f,"Permutations generated = "+str(num_permutations))
print_write(f,"compared to 11! which = "+str(math.factorial(11)))
print_write(f," ")
"""
u"\u2660" - spade
u"\u2665" - heart
u"\u2666" - diamond
u"\u2663" - club
"""
shoe = []
for suit in [u"\u2660",u"\u2665",u"\u2666",u"\u2663"]:
for value in ['A','K','Q','J','10','9','8','7','6','5','4','3','2']:
shoe.append(value+suit)
print_write(f,str_format(shoe))
p1 = [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]
p2 = [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]
print_write(f," ")
print_write(f,dot_format(p1))
print_write(f," ")
print_write(f,str_format(apply_perm(shoe[:],p1)))
print_write(f," ")
print_write(f,dot_format(p2))
print_write(f," ")
print_write(f,str_format(apply_perm(shoe[:],p2)))
# generate random 51 digit factorial based number
import random
max = math.factorial(52)
random_int = random.randint(0, max-1)
myperm = leading_zeros(int_to_fbn(random_int),51)
print(len(myperm))
print_write(f," ")
print_write(f,dot_format(myperm))
print_write(f," ")
print_write(f,str_format(apply_perm(shoe[:],myperm)))
f.write("</pre>\n")
- Output:
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 permutations so far = 1000000 permutations so far = 2000000 permutations so far = 3000000 permutations so far = 4000000 permutations so far = 5000000 permutations so far = 6000000 permutations so far = 7000000 permutations so far = 8000000 permutations so far = 9000000 permutations so far = 10000000 permutations so far = 11000000 permutations so far = 12000000 permutations so far = 13000000 permutations so far = 14000000 permutations so far = 15000000 permutations so far = 16000000 permutations so far = 17000000 permutations so far = 18000000 permutations so far = 19000000 permutations so far = 20000000 permutations so far = 21000000 permutations so far = 22000000 permutations so far = 23000000 permutations so far = 24000000 permutations so far = 25000000 permutations so far = 26000000 permutations so far = 27000000 permutations so far = 28000000 permutations so far = 29000000 permutations so far = 30000000 permutations so far = 31000000 permutations so far = 32000000 permutations so far = 33000000 permutations so far = 34000000 permutations so far = 35000000 permutations so far = 36000000 permutations so far = 37000000 permutations so far = 38000000 permutations so far = 39000000 Permutations generated = 39916800 compared to 11! which = 39916800 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♠ 35.21.48.20.4.1.5.41.3.1.25.34.30.4.25.1.11.29.28.4.5.29.17.28.0.18.14.19.20.1.1.4.19.6.2.6.9.5.8.3.10.10.7.1.7.3.0.3.2.0.0 5♦6♥3♣7♥10♠K♠7♠6♣9♠Q♠8♦10♣A♣5♠6♦J♠9♥9♣J♣3♠A♥4♣J♦2♣A♠7♦K♦2♦Q♣6♠4♠J♥5♣5♥K♥3♥10♦4♥9♦10♥8♣7♣4♦2♠K♣2♥8♠Q♦A♦Q♥8♥3♦
Quackery
(I have set my own tasks to illustrate the use of factorial base numbers with permutations as I do not find the assigned tasks particularly illuminating IMHO.)
[ 1 swap times [ i 1+ * ] ] is ! ( n --> n )
[ dup 0 = iff [ drop 2 ] done
0
[ 1+ 2dup ! / 0 = until ]
nip ] is figits ( n --> n )
[ [] unrot 1 - times
[ i 1+ ! /mod
dip join ] drop ] is factoradic ( n n --> [ )
[ 0 swap
witheach [ i 1+ ! * + ] ] is unfactoradic ( [ --> n )
[ [] unrot witheach
[ pluck
rot swap nested join
swap ]
join ] is inversion ( [ [ --> [ )
[ over size
factoradic inversion ] is nperm ( [ n --> [ )
[ 0 unrot swap witheach
[ over find
dup dip [ pluck drop ]
rot i 1+ * + swap ]
drop ] is permnum ( [ [ --> n )
say 'The 1236880662123rd permutation of' cr
say '"uncopyrightable" is "'
$ 'uncopyrightable' 1236880662123 nperm echo$
say '".' cr cr
say 'The factorial base representation of' cr
say '1236880662123 is '
1236880662123 dup figits factoradic echo
say '.' cr cr
say '"lucentbiography" is permutation' cr
say '#' $ 'lucentbiography' $ 'uncopyrightable' permnum echo
say ' of "uncopyrightable".'Output:
The 1236880662123rd permutation of "uncopyrightable" is "echoingabruptly". The factorial number base representation of 1236880662123 is [ 14 2 8 2 5 1 4 5 5 3 0 0 1 1 ]. "lucentbiography" is permutation #1134238755307 of "uncopyrightable". The factorial base number [ 13 0 1 11 0 7 8 4 0 3 2 3 0 1 ] is 1134238755307 as a decimal.
Raku
(formerly Perl 6)
Using my interpretation of the task instructions as shown on the discussion page.
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;
- 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♦
Wren
import "random" for Random
import "./math" for Int
import "./fmt" for Fmt
var genFactBaseNums = Fn.new { |size, countOnly|
var results = []
var count = 0
var n = 0
while (true) {
var radix = 2
var res = null
if (!countOnly) res = List.filled(size, 0)
var k = n
while (k > 0) {
var div = (k/radix).floor
var rem = k % radix
if (!countOnly) {
if (radix <= size + 1) res[size-radix+1] = rem
}
k = div
radix = radix + 1
}
if (radix > size+2) break
count = count + 1
if (!countOnly) results.add(res)
n = n + 1
}
return [results, count]
}
var mapToPerms = Fn.new { |factNums|
var perms = []
var psize = factNums[0].count + 1
var start = List.filled(psize, 0)
for (i in 0...psize) start[i] = i
for (fn in factNums) {
var perm = start.toList
for (m in 0...fn.count) {
var g = fn[m]
if (g != 0) {
var first = m
var last = m + g
for (i in 1..g) {
var temp = perm[first]
for (j in first+1..last) perm[j-1] = perm[j]
perm[last] = temp
}
}
}
perms.add(perm)
}
return perms
}
var join = Fn.new { |ints, sep| ints.map { |i| i.toString }.join(sep) }
var undot = Fn.new { |s| s.split(".").map { |ss| Num.fromString(ss) }.toList }
var rand = Random.new()
// Recreate the table.
var factNums = genFactBaseNums.call(3, false)[0]
var perms = mapToPerms.call(factNums)
var i = 0
for (fn in factNums) {
Fmt.print("$s -> $s", join.call(fn, "."), join.call(perms[i], ""))
i = i + 1
}
// Check that the number of perms generated is equal to 11! (this takes a while).
var count = genFactBaseNums.call(10, true)[1]
Fmt.print("\nPermutations generated = $,d", count)
Fmt.print("compared to 11! which = $,d", Int.factorial(11))
System.print()
// Generate shuffles for the 2 given 51 digit factorial base numbers.
var fbn51s = [
"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"
]
factNums = [undot.call(fbn51s[0]), undot.call(fbn51s[1])]
perms = mapToPerms.call(factNums)
var shoe = "A♠K♠Q♠J♠T♠9♠8♠7♠6♠5♠4♠3♠2♠A♥K♥Q♥J♥T♥9♥8♥7♥6♥5♥4♥3♥2♥A♦K♦Q♦J♦T♦9♦8♦7♦6♦5♦4♦3♦2♦A♣K♣Q♣J♣T♣9♣8♣7♣6♣5♣4♣3♣2♣".toList
var cards = List.filled(52, null)
for (i in 0..51) {
cards[i] = shoe[2*i..2*i+1].join()
if (cards[i][0] == "T") cards[i] = "10" + cards[i][1..-1]
}
i = 0
for (fbn51 in fbn51s) {
System.print(fbn51)
for (d in perms[i]) System.write(cards[d])
System.print("\n")
i = i + 1
}
// Create a random 51 digit factorial base number and produce a shuffle from that.
var fbn51 = List.filled(51, 0)
for (i in 0..50) fbn51[i] = rand.int(52-i)
System.print(join.call(fbn51, "."))
perms = mapToPerms.call([fbn51])
for (d in perms[0]) System.write(cards[d])
System.print()
- Output:
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 Permutations generated = 39,916,800 compared to 11! which = 39,916,800 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♠ 35.12.47.3.41.40.22.9.38.8.26.15.29.23.23.0.17.19.32.5.31.10.8.26.1.18.15.6.23.21.9.13.13.1.7.11.1.1.2.5.8.6.4.1.2.3.3.2.1.2.0 5♦2♠4♣J♠9♣10♣3♥4♠8♣5♠9♦8♥3♦J♦10♦A♠4♥K♦3♣7♠2♣J♥K♥7♣Q♠6♦Q♦A♥5♣J♣7♥8♦7♦10♠9♥4♦9♠8♠3♠5♥A♣A♦6♥6♠10♥2♦K♣2♥Q♥6♣K♠Q♣
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
}- Part 1, Generate permutation table:
foreach a,b,c in (4,3,2){
println("%d.%d.%d --> %s".fmt(a,b,c, fpermute(T(0,1,2,3),T(a,b,c)).concat()));
}- Output:
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 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("")); }- Output:
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♠
- Part 4, Generate a random shuffle:
r:=[52..2,-1].pump(List,(0).random);
println(r.concat("."),"\n",fpermute(deck,r).concat(""));- Output:
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♠