2

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

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 吗？

4

4 回答 4

0

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

S1 == "acb" (F = 1) , 1 < 3 所以有一个 charx比另一个 char 大y并且它的索引大于y，这里最小的索引x是c，并且首先尝试将其替换为a（即小于x所以算法在这里完成）==> S2= "cab", F(S2) = 2。

现在让我们用 S2 进行测试，cab: x=b, y=a, ==> S3 = "cba".\

查找x不难，迭代输入，并有一个变量名 it 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);

}
于 2012-06-12T09:58:42.953 回答
0

这是解决您的问题的算法的大纲。

我假设您有一个函数可以直接返回第n-th 排列（给定n）及其逆排列，即返回n给定排列的函数。让它们分别为perm(n)和perm'(n)。

如果我猜对了，当你有一个 4 个字母的字符串来置换函数 F 时，如下所示：

F("abcd")   = 0
F("abdc")   = 1
F(perm(3))  = 1
F(...)      = 2
F(...)      = 2
F(...)      = 3
F(perm(7))  = 1
F(...)      = 2
F(...)      = 2
F(...)      = 3
F(...)      = 3
F(...)      = 4
F(perm(13)) = 2
F(...)      = 3
F(...)      = 3
F(...)      = 4
F(...)      = 4
F(...)      = 5
F(perm(19)) = 3
F(...)      = 4
F(...)      = 4
F(...)      = 5
F(...)      = 5
F(perm(24)) = 6

换句话说，当您从 3 个字母变为 4 个字母时，您将获得 F 值表的 4 个副本，分别将 (0,1,2,3) 添加到 (1st,2nd,3rd,4th) 副本。例如，在第 2 种情况下，您已经将第 2 个字母放在第 1 位，从而导致一种错乱；这只是以与原始 3 字母字符串相同的模式添加到其他混乱中。

从这个大纲来看，编写函数 F 应该不会太难（但我现在没有时间）。严格来说，F 的逆不是一个函数，因为它是多值的，但是给定n, 和F(n)只有少数情况下可以找到mst F(m)==F(n)+1。这些情况是：

  • n == N!其中N是字符串中字母的个数，没有下一个排列；
  • F(n+1) < F(n), 寻求的解决方案是perm(n+(N-1)!), ;
  • F(n+1) == F(n), 解决方案是perm(n+2);
  • F(n+1) > F(n)，解决方案是perm(n+1)。

我怀疑其中一些可能只适用于 4 个字母的字符串，其中一些术语必须针对 K 字母排列进行调整。

于 2012-06-12T10:29:17.197 回答
0

这不是O(n)，但至少是O(n²)（其中 n 是排列中的元素数，在您的示例 3 中）。

首先，请注意，每当您在字符串中放置一个字符时，您已经知道 F 增加了多少意味着 - 它比尚未添加到字符串中的字符小很多。

这为我们提供了另一种计算 F(n) 的算法：

used = set()

def get_inversions(S1):
    inv = 0
    for index, ch in enumerate(S1):
        character = ord(ch)-ord('a')
        cnt = sum(1 for x in range(character) if x not in used)
        inv += cnt
        used.add(character)
    return inv

这并不比原始版本好多少，但在反转 F 时很有用。您想知道第一个按字典顺序较小的字符串 - 因此，复制原始字符串并仅在强制时更改它是有意义的。当需要进行此类更改时，我们还应该尽可能少地更改字符串。

为此，让我们使用具有n字母的字符串的 F 的最大值是的信息n(n-1)/2。如果我们不更改原始字符串，每当所需反转的数量大于此数量时，这意味着我们必须在该点交换一个字母。Python中的代码：

used = set()

def get_inversions(S1):
    inv = 0
    for index, ch in enumerate(S1):
        character = ord(ch)-ord('a')
        cnt = sum(1 for x in range(character) if x not in used)
        inv += cnt
        used.add(character)
    return inv

def f_recursive(n, S1, inv, ign):
    if n == 0: return ""

    delta = inv - (n-1)*(n-2)/2

    if ign:
        cnt = 0
        ch = 0
    else:
        ch = ord(S1[len(S1)-n])-ord('a')
        cnt = sum(1 for x in range(ch) if x not in used)

    for letter in range(ch, len(S1)):
        if letter not in used:
            if cnt < delta:
                cnt += 1
                continue

            used.add(letter)
            if letter != ch: ign = True

            return chr(letter+ord('a'))+f_recursive(n-1, S1, inv-cnt, ign)

def F_inv(S1):
    used.clear()
    inv = get_inversions(S1)

    used.clear()
    return f_recursive(len(S1), S1, inv+1, False)


print F_inv("acb")

也可以O(n log n)通过用诸如二叉索引树之类的数据结构替换最内层循环来使其运行。

于 2012-06-12T23:32:03.567 回答
-1

您是否尝试交换字符串中的两个相邻字符？似乎它可以帮助解决问题。如果交换 S[i] 和 S[j]，其中 i < j 且 S[i] < S[j]，则 F(S) 增加 1，因为所有其他索引对都不受此排列的影响。

如果我没记错的话，F 会计算排列的反转次数。

于 2012-06-12T17:04:56.780 回答