Belirli bir dizgenin bir sonraki daha büyük permütasyonunu bulmak için algoritma

Question

Verilen dizenin bir sonraki daha büyük permütasyonunu bulmak için verimli bir algoritma istiyorum.

Answer 1

Wikipedia, lexicographical order generation üzerinde article numaralı telefona sahiptir. Ayrıca, bir sonraki permütasyonu oluşturmak için bir algoritma açıklar.

teklif:

Aşağıdaki algoritma sözlük sırasında belirli bir permütasyon sonraki permütasyon oluşturur. Verilen permütasyonu yerinde değiştirir.

1. en yüksek endeksi i öyle ki s[i] < s[i+1] bulun. Eğer böyle bir indeks yoksa, permütasyon son permümandır.
2. s[j] > s[i] gibi en yüksek j > i dizinini bulun. gibi bir i+1 böyle bir dizin olduğundan, böyle bir varlık bulunmalıdır.
3. ile s[i] değiştir.
4. Son öğeye kadar i dizininden sonra tüm öğelerin sırasını tersine çevirin.

Answer 2

Ödev? Neyse, C++ işlev std :: next_permutation veya bu bakabilirsiniz: Aşağıdaki adımı kullanarak belirli bir dize S için bir sonraki büyük lexicographic dize bulabilirsiniz

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

Answer 3

.

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

verilen dize S sonraki büyük lexicographic dizedir. Bir de C++ 'da next_permutation işlev çağrısını kullanabilir.

Answer 4

Umarım bu kod yararlı olabilir.

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

burada açıklanan çalışan bir harika bir çözüm: https://www.nayuki.io/page/next-lexicographical-permutation-algorithm.

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.