字符串字典顺序排列和反转

Question

考虑字符串上的以下函数:

int F(string S)
{
    int N = S.size();

    int T = 0;

    for (int i = 0; i < N; i++)
        for (int j = i + 1; j < N; j++)
            if (S[i] > S[j])
                T++;

    return T;
}

长度为 N 且所有成对不同字符的字符串 S0 共有 N!独特的排列。

例如“bac”有以下6种排列:

bac
abc
cba
bca
acb
cab

考虑这 N!按字典顺序排列的字符串:

abc
acb
bac
bca
cab
cba

现在考虑将 F 应用于以下每个字符串:

F("abc") = 0
F("acb") = 1
F("bac") = 1
F("bca") = 2
F("cab") = 2
F("cba") = 3

给定这组排列的一些字符串 S1，我们想找到集合中的下一个字符串 S2，它与 S1 具有以下关系:

F(S2) == F(S1) + 1

例如，如果 S1 == "acb"(F = 1) 而不是 S2 == "bca"(F = 1 + 1 = 2)

一种方法是从 S1 过去的一个开始，遍历排列列表以寻找 F(S) = F(S1)+1。不幸的是，这是 O(N!)。

在S1上用什么O(N)函数可以直接计算出S2？

Answer 1

假设S1的长度为n，最大值为F(S1)是n(n-1)/2 , 如果 F(S1) = n(n-1)/2 , 意味着它是最后一个函数并且没有任何下一个函数，但是如果 F(S1) < n(n-1)/2 , 表示至少有一个字符 x大于 char y和 x在y旁边, 找到这样一个 x具有最低索引，并更改 x 和 y 位置。让我们通过例子来看:

S1 == "acb"(F = 1) , 1 < 3 所以有一个字符 x比另一个字符大 y其索引大于y ，这里是最小的索引 x是c , 并首先尝试将其替换为 a (小于 x 所以算法在这里结束)==> S2= "cab", F(S2) = 2.

现在用 S2，cab 测试它:x=b，y=a，==> S3 = "cba"。\

发现 x不难，迭代输入，并有一个变量名 min , 而当前访问的字符小于 min , 设置 min作为新访问的字符，访问下一个字符，第一次访问大于 min 的字符停止迭代，这是 x :

这是 c# 中的伪代码(但我没有注意边界，例如在 input.Substring 中):

string NextString(string input)
{
    var min = input[0];
    int i=1;
    while (i < input.Length && input[i] < min)
    {
       min = input[i];
       i++;
    }

    if (i == input.Length) return "There isn't next item";

    var x = input[i], y=input[i-1];
    return input.Substring(0,i-2) + x + y + input.Substring(i,input.Length - 1 - i);

}