算法找到一个给定的字符串的下一个更大的置换

本文介绍了算法找到一个给定的字符串的下一个更大的置换的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我想要一个高效的算法来找到特定字符串的下一个更大的置换。

解决方案

维基百科有一个很好的文章对辞书订单生成。它也描述了一种算法，以产生下一个置换

报价：

下面的算法给定的置换之后字典顺序生成下一个排列。它改变就地给定的置换。

     

找到最高的指数我，使得 S [1] - ; S [I + 1] 。如果没有这样的存在索引，置换是最后的置换。

  

找到最高的指数 J＆GT;我，使得 S [J]＆GT; S [I] 。这样的Ĵ必须存在，因为 I + 1 就是这样一个指标。

  

交换 S [I] 与 S [J] 。

  

在指数反转的所有元素的所有顺序为第i

  

I want an efficient algorithm to find the next greater permutation of the given string.

解决方案

Wikipedia has a nice article on lexicographical order generation. It also describes an algorithm to generate the next permutation.

Quoting:

The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place.

Find the highest index i such that s[i] < s[i+1]. If no such index exists, the permutation is the last permutation.

Find the highest index j > i such that s[j] > s[i]. Such a j must exist, since i+1 is such an index.

Swap s[i] with s[j].

Reverse all the order of all of the elements after index i