查找給定字符串的下一個更大排列的算法

Question

我想要一個有效的算法來查找給定字符串的下一個更大排列。

Answer 1

維基百科有關辭典生成的不錯article。它還描述了生成下一個排列的算法。

引用：

以下算法給定的置換之後字典順序生成下一個排列。它改變了原來的給定排列。

1. 查找指數最高i這樣s[i] < s[i+1]。如果不存在這樣的索引，則排列是最後的排列。
2. 查找最高索引j > i，例如s[j] > s[i]。這樣的j必須存在，因爲i+1就是這樣一個索引。
3. 交換s[i]與s[j]。
4. 顛倒索引i之後的所有元素的順序直到最後一個元素。

Answer 2

家庭作業？無論如何，可以看看C++函數的std :: next_permutation，或這樣的：

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

Answer 3

我們可以找到使用以下步驟給定的字符串S中的一個最大的字典字符串。

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]) 

給定的字符串是S的下一個最大的字典字符串。也可以使用C++中的next_permutation函數調用。

Answer 4

我希望這段代碼可能會有幫助。

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

有用的一個很好的解決方案在這裏描述：https://www.nayuki.io/page/next-lexicographical-permutation-algorithm。而解決方案是，如果接下來的排列存在，返回它，否則返回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.