Permutations/Rank of a permutation: Difference between revisions
Content added Content deleted
m (→{{header|Quackery}}: addled commentary) |
(New post.) |
||
Line 246: | Line 246: | ||
22: [ 0, 1, 3, 2 ] = 22 |
22: [ 0, 1, 3, 2 ] = 22 |
||
23: [ 0, 1, 2, 3 ] = 23 |
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> |
</pre> |
||