Thuật toán để tìm hoán vị lớn hơn tiếp theo của một chuỗi đã cho

Question

Tôi muốn một thuật toán hiệu quả để tìm hoán vị lớn hơn tiếp theo của chuỗi đã cho.

Answer 1

Wikipedia có kiểu dáng đẹp article khi tạo thứ tự từ điển. Nó cũng mô tả một thuật toán để tạo ra hoán vị tiếp theo.

Trích dẫn:

Thuật toán sau tạo ra hoán vị tiếp theo theo từ điển sau một hoán vị nhất định. Nó thay đổi hoán vị đã cho tại chỗ.

1. Tìm chỉ số cao nhất i mà s[i] < s[i+1]. Nếu không có chỉ mục như vậy tồn tại, hoán vị là hoán vị cuối cùng.
2. Tìm chỉ mục cao nhất j > i sao cho s[j] > s[i]. Vì vậy, j phải tồn tại, vì i+1 là một chỉ mục như vậy.
3. Hoán đổi s[i] với s[j].
4. Đảo ngược thứ tự của tất cả các phần tử sau chỉ mục i cho đến phần tử cuối cùng.

Answer 2

Bài tập về nhà? Dù sao, có thể nhìn vào hàm C++ std :: next_permutation, hay này:

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

Answer 3

Chúng ta có thể tìm ra chuỗi tự từ điển lớn nhất tiếp theo cho một chuỗi S được sử dụng các bước sau đây.

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

Chuỗi đã cho là chuỗi từ điển lớn nhất tiếp theo là S. Người ta cũng có thể sử dụng gọi hàm next_permutation trong C++.

Answer 4

Tôi hy vọng mã này có thể hữu ích.

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

Giải pháp tuyệt vời hoạt động được mô tả ở đây: https://www.nayuki.io/page/next-lexicographical-permutation-algorithm. Và giải pháp đó, nếu hoán vị kế tiếp tồn tại, trả về nó, nếu không thì trả 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.