Алгоритм для нахождения следующей большей перестановки заданной строки

Question

Я хочу, чтобы эффективный алгоритм нашел следующую большую перестановку данной строки.

Answer 1

В Википедии есть хорошая статья о создании лексикографического заказа Также описан алгоритм для генерации следующей перестановки.

Цитирование:

Следующий алгоритм генерирует следующую перестановку лексикографически после данной перестановки. Изменяет данную перестановку на месте.

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

Отличное решение, которое работает, описано здесь: 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 3

Домашнее задание? В любом случае, можете посмотреть на функцию C ++ std :: next_permutation, или это:

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

Answer 4

Использование источника, цитируемого @ Fleischpfanzerl

Следующая лексикографическая перестановка

Мы выполняем следующие шаги, чтобы найти следующую лексикографическую перестановку:

nums = [0,1,2,5,3,3,0]
nums = [0]*5
curr = nums[-1]
pivot = -1
for items in nums[-2::-1]:
    if items >= curr:
        pivot -= 1
        curr = items
    else:
        break
if pivot == - len(nums):
    print('break')     # The input is already the last possible permutation

j = len(nums) - 1
while nums[j] <= nums[pivot - 1]:
    j -= 1
nums[j], nums[pivot - 1] = nums[pivot - 1], nums[j]
nums[pivot:] = nums[pivot:][::-1]

> [1, 3, 0, 2, 3, 5]

Итак, идея такова: Идея состоит в том, чтобы следовать шагам -

1. Найти индекс 'pivot' в конце массива, чтобы nums [i - 1]
2. Найдите индекс j, такой что nums [j]> nums [pivot - 1]
3. Поменяйте местами оба этих индекса
4. Обратный суффикс, начинающийся с точки разворота

Answer 5

void Solution::nextPermutation(vector<int> &a) {    
int i,j=-1,k,t=a.size();
for(i=0;i<t-1;i++)
{
    if(a[i]<a[i+1])
    j=i;
}
if(j==-1)
reverse(a.begin(),a.end());
else
{
for(i=j+1;i<t;i++)
    {
        if(a[j]<a[i])
        k=i;
    }
swap(a[j],a[k]);
reverse(a.begin()+j+1,a.end());
}

}

Answer 6

следующий срок (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.

Answer 7

Мы можем найти следующую наибольшую лексикографическую строку для данной строки 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. Можно также использовать next_permutation вызов функции в C ++.

Answer 8

Я наткнулся на отличный учебник. ссылка: https://www.youtube.com/watch?v=quAS1iydq7U

void Solution::nextPermutation(vector<int> &a) {


int k=0;
int n=a.size();
for(int i=0;i<n-1;i++)
{
    if(a[i]<a[i+1])
    {
        k=i;
    }
}

int ele=INT_MAX;
int pos=0;
for(int i=k+1;i<n;i++)
{
    if(a[i]>a[k] && a[i]<ele)
    {
        ele=a[i];pos=i;
    }

}

if(pos!=0)
{

swap(a[k],a[pos]);

reverse(a.begin()+k+1,a.end()); 

}    

}

Answer 9

Отличное решение, которое работает, описано здесь: https://www.nayuki.io/page/next-lexicographical-permutation-algorithm. и если вы ищете

исходный код:

/**
     * method to find the next lexicographical greater string
     * 
     * @param w
     * @return a new string
     */
    static String biggerIsGreater(String w) {
        char charArray[] = w.toCharArray();
        int n = charArray.length;
        int endIndex = 0;

        // step-1) Start from the right most character and find the first character
        // that is smaller than previous character.
        for (endIndex = n - 1; endIndex > 0; endIndex--) {
            if (charArray[endIndex] > charArray[endIndex - 1]) {
                break;
            }
        }

        // If no such char found, then all characters are in descending order
        // means there cannot be a greater string with same set of characters
        if (endIndex == 0) {
            return "no answer";
        } else {
            int firstSmallChar = charArray[endIndex - 1], nextSmallChar = endIndex;

            // step-2) Find the smallest character on right side of (endIndex - 1)'th
            // character that is greater than charArray[endIndex - 1]
            for (int startIndex = endIndex + 1; startIndex < n; startIndex++) {
                if (charArray[startIndex] > firstSmallChar && charArray[startIndex] < charArray[nextSmallChar]) {
                    nextSmallChar = startIndex;
                }
            }

            // step-3) Swap the above found next smallest character with charArray[endIndex - 1]
            swap(charArray, endIndex - 1, nextSmallChar);

            // step-4) Sort the charArray after (endIndex - 1)in ascending order
            Arrays.sort(charArray, endIndex , n);

        }
        return new String(charArray);
    }

    /**
     * method to swap ith character with jth character inside charArray
     * 
     * @param charArray
     * @param i
     * @param j
     */
    static void swap(char charArray[], int i, int j) {
        char temp = charArray[i];
        charArray[i] = charArray[j];
        charArray[j] = temp;
    }

Если вы ищете видео объяснение того же, вы можете посетить здесь .

Answer 10

Я надеюсь, что этот код может быть полезным.

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";
    }
}