n-ta permutacja bez powtórzeń.

Nie znacie może algorytmu (znacznie szybszego od n!), który znajdzie k-tą (zgodnie z sortowaniem leksykograficznym) permutację zbioru n-elementowego (1, 2, 3, ... , n - 1, n).
np.
n = 3
k = 6
wynik = 3 2 1;

n = 2
k = 1
wynik = 1 2;

Uwaga: To jest stary temat Ta dyskusja jest starsza niż 90 dni. Informacje w niej zawarte mogą już nie być aktualne

w c++ istnieje pewna funkcja szablonowa "next_permutation" z stl'a znajdująca się w nagłówku "algorithm". Proponowałbym przejrzeć ten plik (w nim znajduje się w rzeczywistości odwołanie do prawidłowego pliku) gdzie znajduje się implementacja tej funkcji. Myślę, że może być ona pomocna.

Musi istnieć coś szybszego. Dla k = 20! i n = 20, program działał by "troszkę" za długo.

Ok. Napisałem to sam. Gdyby komuś się miało przydac zamieszczam kod C++. Demon szybkości to to nie jest, ale działa troszkę szybciej od n! :

Kod php:

#include <iostream> 
#include <algorithm> 
#include <list> 
using namespace std; 
long long int silnia(int k) 
{ 
      long long int wynik = 1; 
      while (k > 1) 
      { 
              wynik *= k; 
              k--; 
      } 
      return wynik; 
} 
int main() 
{ 
              int n; 
              long long int k, s, pom; 
              cin >> n >> k; 
              list<int> lista; 
              list<int>::iterator it; 
              for(int j = 1; j < n+1; j++) lista.push_back(j); 
              k--; 
              while(!lista.empty()) 
              { 
                      s = silnia(n-1); 
                      pom = (k/s); 
                      it = lista.begin(); 
                      for (int i = 0; i<pom; i++) it++; 
                      cout << *it << " "; 
                      lista.erase(it); 
                      k %= s; 
                      n--; 
              } 
              cout << endl; 
return 0; 
}