Factorial base numbers indexing permutations of a collection: Difference between revisions
Factorial base numbers indexing permutations of a collection (view source)
Revision as of 20:45, 30 June 2024
, 4 days agoMinor code alteration.
m (→{{header|Wren}}: Minor tidy) |
m (Minor code alteration.) |
||
| (3 intermediate revisions by the same user not shown) | |||
Line 207:
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♦"</syntaxhighlight>
=={{header|C++}}==
<syntaxhighlight lang="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;
}
</syntaxhighlight>
{{ out }}
<pre>
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♥
</pre>
=={{header|F_Sharp|F#}}==
Line 841 ⟶ 1,034:
ThreadLocalRandom random = ThreadLocalRandom.current();
factoradic.clear();
for ( int i = 0; i <
factoradic.add(random.nextInt(cards.size() - i));
}
| |||