考虑字符串上的以下函数:
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?
最佳答案
假设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);
}
关于字符串字典顺序排列和反转,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10993365/