Algorytm znajdowania następnej większej permutacji danego ciągu znaków

Question

Potrzebuję skutecznego algorytmu do znalezienia następnej większej permutacji danego ciągu.

Answer 1

Wikipedia ma ładne article generowanie kolejności leksykograficznych. Opisano również algorytm generowania następnej permutacji.

Cytowanie:

następujący algorytm generuje następne permutacji leksykograficznie po danym permutacji. Zmienia daną permutację w miejscu.

1. Znajdź najwyższy wskaźnik i takie, że s[i] < s[i+1]. Jeśli taki indeks nie istnieje, permutacja jest ostatnią permutacją.
2. Znajdź najwyższy indeks j > i taki, że s[j] > s[i]. Takich musi być j, ponieważ taki indeks jest i+1.
3. Zamień s[i] z s[j].
4. Odwróć kolejność wszystkich elementów po indeksie i aż do ostatniego elementu.

Answer 2

Praca domowa? W każdym razie, można spojrzeć na C++ funkcja std :: next_permutation czy to:

http://blog.bjrn.se/2008/04/lexicographic-permutations-using.html

Answer 3

Możemy znaleźć następną największą leksykograficzny ciąg dla danego łańcucha S stosując następujący krok.

1. Iterate over every character, we will get the last value i (starting from the first character) that satisfies the given condition S[i] < S[i + 1] 
2. Now, we will get the last value j such that S[i] < S[j] 
3. We now interchange S[i] and S[j]. And for every character from i+1 till the end, we sort the characters. i.e., sort(S[i+1]..S[len(S) - 1]) 

Podany ciąg jest następna największa leksykograficzny ciąg S. Można również użyć wywołania funkcji next_permutation w C++.

Answer 4

Mam nadzieję, że ten kod może być pomocny.

int main() { 

    char str[100]; 
    cin>>str; 
    int len=strlen(len); 
    int f=next_permutation(str,str+len);  
    if(f>0) { 
     print the string 
    } else { 
     cout<<"no answer"; 
    } 
} 

Answer 5

Doskonałe rozwiązanie, które działa, jest opisane tutaj: https://www.nayuki.io/page/next-lexicographical-permutation-algorithm. I rozwiązanie, które, w razie następnego permutacji istnieje, zwraca go, powraca inaczej false:

function nextPermutation(array) { 
    var i = array.length - 1; 
    while (i > 0 && array[i - 1] >= array[i]) { 
     i--; 
    } 

    if (i <= 0) { 
     return false; 
    } 

    var j = array.length - 1; 

    while (array[j] <= array[i - 1]) { 
     j--; 
    } 

    var temp = array[i - 1]; 
    array[i - 1] = array[j]; 
    array[j] = temp; 

    j = array.length - 1; 

    while (i < j) { 
     temp = array[i]; 
     array[i] = array[j]; 
     array[j] = temp; 
     i++; 
     j--; 
    } 

    return array; 
} 

Answer 6

nextperm (A, n)

1. find an index j such that a[j….n - 1] forms a monotonically decreasing sequence. 
2. If j == 0 next perm not possible 
3. Else 
    1. Reverse the array a[j…n - 1] 
    2. Binary search for index of a[j - 1] in a[j….n - 1] 
    3. Let i be the returned index 
    4. Increment i until a[j - 1] < a[i] 
    5. Swap a[j - 1] and a[i] 


O(n) for each permutation.