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) よりも

これを行う 1 つの方法は、S1 の 1 つ前から開始し、F(S) = F(S1)+1 を探して順列のリストを反復処理することです。これは残念ながら O(N!) です。

S1 のどの O(N) 関数によって、S2 を直接計算できますか?

4

4 に答える 4

0

S1 の長さが n であると仮定すると、 is の最大値ifF(S1)は、それが最後の関数であり、次の関数がないことを意味しますが、 ifは、 char よりも大きく、の隣にあるchar が少なくとも 1 つあることを意味します。最低のインデックスで、x と y の場所を変更します。例で見てみましょう：n(n-1)/2F(S1) = n(n-1)/2F(S1) < n(n-1)/2xyxyx

S1 == "acb" (F = 1) , 1 < 3 したがってx、別の char よりも大きい 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

これは ではありませんO(n)が、少なくともそうですO(n²)(例 3 では、n は順列の要素の数です)。

最初に、文字列に文字を配置するときはいつでも、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")

また、最も内側のループを2 項索引ツリーO(n log n)などのデータ構造に置き換えることによって、実行することもできます。

于 2012-06-12T23:32:03.567 に答える
0

問題を解決するためのアルゴリズムの概要を次に示します。

n-th 順列 (与えられたn) とその逆を直接返す関数、つまり与えられた順列を返す関数があると仮定しますn。これらperm(n)をperm'(n)それぞれ と とする。

私が正しく理解した場合、関数 F を並べ替える 4 文字の文字列がある場合、次のようになります。

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 位に配置することで、すでに 1 つの錯乱があります。これは、元の 3 文字の文字列に当てはまる場合と同じパターンで、他の混乱に単純に追加されます。

この概要から、関数 F を書くのはそれほど難しくないはずです (しかし、今は時間がありません)。厳密に言えば、F の逆関数は多値であるため関数ではありませんが、 が与えられますn。stF(n)が見つかるケースはごくわずかです。これらのケースは次のとおりです。mF(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 に答える
-1

文字列内の隣接する 2 つの文字を入れ替えようとしましたか? 問題の解決に役立ちそうです。S[i] と S[j] (i < j および S[i] < S[j]) を交換すると、F(S) が 1 増加します。これは、インデックスの他のすべてのペアがこの順列の影響を受けないためです。

私が間違っていなければ、Fは順列の反転の数を計算します。

于 2012-06-12T17:04:56.780 に答える