michal11 Temat założony przez niniejszego użytkownika |
Wyznaczanie k-tej permutacji zbioru n-elementowego. » 2015-03-06 17:44:55 Jak w temacie, mam wyznaczyć k-tą permutacje w porządku leksykograficznym. Niestety przeszukiwanie internetu zaowocowało tylko 1 postem sprzed 10 lat z którego nie za wiele wywnioskowałem. Czy ktoś mógłby mnie przynajmniej naprowadzić czego mam szukać albo najlepiej podać nazwę algorytmu ? |
|
pekfos |
» 2015-03-07 20:34:17 Spróbuj szukać w kierunku std::next_permutation(). Od biedy możesz też po prostu użyć tej funkcji. |
|
Monika90 |
» 2015-03-07 21:39:31 Mój nieprzemyślany algorytm #include <iostream>
#include <string>
unsigned long long factorial( unsigned long long n )
{
unsigned long long result = 1;
while( n > 1 )
result *= n--;
return result;
}
std::string nth_permutation( std::string str, unsigned long long n )
{
std::string result;
while( !str.empty() )
{
const auto f = factorial( str.size() - 1 );
const auto k = n / f;
n -= k * f;
result += str[ k ];
str.erase( k, 1 );
}
return result;
}
int main()
{
const std::string s = "abcdefgh";
std::cout << nth_permutation( s, 0 )
<< '\n' << nth_permutation( s, 11111 )
<< '\n' << nth_permutation( s, 40319 )
<< '\n';
}
Na pewno można lepiej, tak żeby nie liczyć za każdym razem tej silni. Permutacje numerowane są od zera. |
|
michal11 Temat założony przez niniejszego użytkownika |
» 2015-03-07 22:01:16 @pekfos
Nie chodzi mi o kolejna permutację, to już mam, tylko o wyliczenie k-tej.
@Monika90
Dziękuje za kod, jeszcze go nie analizowałem ale nie chodzi mi o gotowca tylko o jakis schemat, spis kroków, nazwę algorytmu, stronę na której to jest opisane w miare przystepny sposób. Ewentualnie czy mogła byś napisac na czym polega twój algorytm ? Co on robi ? |
|
Monika90 |
» 2015-03-07 22:22:26 Nie wiem jak Ci ten algorytm wyjaśnić, może jutro... :)
Mała poprawka w powyższym kodzie, zamiast int n, jest unsigned long long n, tak chyba jest lepiej. |
|
michal11 Temat założony przez niniejszego użytkownika |
» 2015-03-08 11:32:41 No ok to czekam do jutra, bo po pierwsze chciałbym to sam napisać, a po drugie muszę permutować tablicę intów(ew. vector) a nie string. |
|
Monika90 |
» 2015-03-08 14:41:42 no to niestety jeszcze będziesz musiał poczekać, bo mi komputer nie działa, tylko piszczy. |
|
Monika90 |
» 2015-03-08 18:41:53 Łatwo uogólnić na ciąg dowolnych wartości (byle nie dłuższy niż 20 elemntów) #include <iostream>
#include <cassert>
#include <algorithm>
unsigned long long factorial( unsigned long long n )
{
unsigned long long result = 1;
while( n > 1 )
result *= n--;
return result;
}
template < class RandomAccessIter >
void nth_permutation( RandomAccessIter beg, RandomAccessIter end, unsigned long long n )
{
assert( end - beg <= 20 );
auto f = factorial( end - beg );
assert( n < f );
while( beg != end )
{
f /= end - beg;
const auto i = n / f;
std::rotate( beg, beg + i, beg + i + 1 );
n -= i * f;
++beg;
}
}
int main()
{
std::vector < int > v = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 };
nth_permutation( v.begin(), v.end(), 1312455074088721123 );
for( auto & n: v )
std::cout << n << ' ';
}
ale trudniej wyjaśnić |
|
| « 1 » 2 |