Permutations/Rank of a permutation: Difference between revisions
Permutations/Rank of a permutation (view source)
Revision as of 12:48, 24 January 2024
, 4 months ago→{{header|Wren}}: Minor tidy
(→{{header|Quackery}}: refactored) |
m (→{{header|Wren}}: Minor tidy) |
||
| (2 intermediate revisions by 2 users not shown) | |||
Line 246:
22: [ 0, 1, 3, 2 ] = 22
23: [ 0, 1, 2, 3 ] = 23
</pre>
=={{header|C++}}==
<syntaxhighlight lang="c++">
#include <cstdint>
#include <iostream>
#include <random>
#include <vector>
void print_vector(const std::vector<int32_t>& list) {
std::cout << "[";
for ( uint64_t i = 0; i < list.size() - 1; ++i ) {
std::cout << list[i] << ", ";
}
std::cout << list.back() << "]";
}
uint64_t factorial(const int32_t& n) {
uint64_t factorial = 1;
for ( int32_t i = 2; i <= n; ++i ) {
factorial *= i;
}
return factorial;
}
uint64_t rank1(const int32_t& n, std::vector<int32_t>& vec, std::vector<int32_t>& inverse) {
if ( n < 2 ) {
return 0;
}
const int32_t last = vec[n - 1];
std::swap(vec[n - 1], vec[inverse[n - 1]]);
std::swap(inverse[last], inverse[n - 1]);
return last + n * rank1(n - 1, vec, inverse);
}
void unrank1(const int64_t& rank, const int32_t& n, std::vector<int32_t>& vec) {
if ( n < 1 ) {
return;
}
const int64_t quotient = rank / n;
const int64_t remainder = rank % n;
std::swap(vec[remainder], vec[n - 1]);
unrank1(quotient, n - 1, vec);
}
int64_t rank(const int32_t& n, std::vector<int32_t>& vec) {
std::vector<int32_t> copy_vec(n, 0);
std::vector<int32_t> inverse(n, 0);
for ( int32_t i = 0; i < n; ++i ) {
copy_vec[i] = vec[i];
inverse[vec[i]] = i;
}
return rank1(n, copy_vec, inverse);
}
void permutation(const int64_t& rank, const int32_t& n, std::vector<int32_t>& vec) {
std::iota(vec.begin(), vec.end(), 0);
unrank1(rank, n, vec);
}
int main() {
int32_t test_size = 3;
std::vector<int32_t> test_vector(test_size, 0);
for ( uint64_t count = 0; count < factorial(test_size); ++count ) {
permutation(count, test_size, test_vector);
std::cout << count << " -> ";
print_vector(test_vector);
std::cout << " -> " << rank(3, test_vector) << std::endl;
}
std::cout << std::endl;
test_size = 12; // test_size can be increased up to a maximum of 20
test_vector.resize(test_size);
std::random_device random;
std::mt19937 generator(random());
std::uniform_real_distribution<double> distribution(0.0F, 1.0F);
for ( int32_t count = 0; count < 4; ++count ) {
const uint64_t rand = distribution(generator) * factorial(test_size);
permutation(rand, test_size, test_vector);
std::cout << rand << " -> ";
print_vector(test_vector);
std::cout << " -> " << rank(test_size, test_vector) << std::endl;
}
}
</syntaxhighlight>
{{ out }}
<pre>
0 -> [1, 2, 0] -> 0
1 -> [2, 0, 1] -> 1
2 -> [1, 0, 2] -> 2
3 -> [2, 1, 0] -> 3
4 -> [0, 2, 1] -> 4
5 -> [0, 1, 2] -> 5
247958875 -> [9, 1, 10, 5, 2, 0, 4, 11, 8, 6, 3, 7] -> 247958875
115652888 -> [10, 9, 4, 1, 3, 6, 5, 7, 0, 11, 2, 8] -> 115652888
353180282 -> [7, 5, 4, 1, 3, 10, 6, 0, 9, 8, 11, 2] -> 353180282
275422075 -> [2, 4, 10, 1, 3, 5, 8, 11, 6, 0, 9, 7] -> 275422075
</pre>
Line 1,823 ⟶ 1,925:
=={{header|Quackery}}==
Stretch goal: The words defined here would handle the limitations of the Stack Exchange question with ease, as Quackery numbers are BigInts. The only inconvenience would be generating random numbers in the range 0 to 144! - 1(*), as the built-in PRNG is limited to 64 bits.
(*) This would generate an arbitrary permutation of the numbers 0 to 143, <code>144 identity shuffle</code>. You ''could'' use that permutation to generate a number in the range 0 to 144! - 1 with <code>perm->rank</code> but it has a whiff of circular reasoning. <shrug>
<syntaxhighlight lang="Quackery">
Line 2,412 ⟶ 2,516:
{{trans|Kotlin}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="
import "./fmt" for Fmt
var swap = Fn.new { |a, i, j|
Line 2,477 ⟶ 2,581:
{{out}}
Sample output:
<pre>
0 -> [1, 2, 0] -> 0
| |||