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
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
m (→{{header|Wren}}: Minor tidy) |
||
| (4 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,820 ⟶ 1,922:
result += s * fact(i)
return result</syntaxhighlight>
=={{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">
[ 1 swap times [ i 1+ * ] ] is ! ( n --> n )
[ [] swap times [ i^ join ] ] is identity ( n --> [ )
[ dup identity unrot
[] unrot 1 - times
[ i 1+ ! /mod
dip join ] drop ] is factoradic ( n n --> [ )
[ [] unrot witheach
[ pluck
rot swap nested join
swap ]
join ] is inversion ( [ [ --> [ )
[ factoradic inversion ] is rank->perm ( n n --> [ )
[ [] over size identity
rot witheach
[ over find
dup dip
[ pluck drop ]
swap dip join ]
drop -1 split drop ] is perm->fdic ( [ --> [ )
[ 0 swap
witheach [ + i 1+ * ] ] is fdic->rank ( [ --> n )
[ perm->fdic fdic->rank ] is perm->rank ( [ --> n )
3 ! times
[ i^
dup echo say " -> "
3 rank->perm
dup echo say " -> "
perm->rank
echo cr ]
cr
4 times
[ 12 ! random
dup echo say " -> "
12 rank->perm
dup echo say " -> "
perm->rank
echo cr ]</syntaxhighlight>
{{out}}
<pre>0 -> [ 0 1 2 ] -> 0
1 -> [ 0 2 1 ] -> 1
2 -> [ 1 0 2 ] -> 2
3 -> [ 1 2 0 ] -> 3
4 -> [ 2 0 1 ] -> 4
5 -> [ 2 1 0 ] -> 5
195266704 -> [ 4 10 9 0 11 3 7 5 6 8 1 2 ] -> 195266704
240729875 -> [ 6 0 4 5 7 11 1 3 8 10 9 2 ] -> 240729875
109569601 -> [ 2 9 1 11 6 0 3 4 5 7 10 8 ] -> 109569601
275654445 -> [ 6 10 11 5 7 2 3 1 9 4 8 0 ] -> 275654445
</pre>
=={{header|Racket}}==
Line 2,346 ⟶ 2,516:
{{trans|Kotlin}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="
import "./fmt" for Fmt
var swap = Fn.new { |a, i, j|
Line 2,411 ⟶ 2,581:
{{out}}
Sample output:
<pre>
0 -> [1, 2, 0] -> 0
| |||