12

当面の問題は次のとおりです。

文字列を指定します。辞書式にソートされたすべての順列の中でのランクを教えてください。

質問は数学的に試みることができますが、それを計算するための他のアルゴリズム方法があるかどうか疑問に思っていましたか?

また、すべての文字列順列をランクごとに保存する必要がある場合、それらを効率的に生成するにはどうすればよいでしょうか (そして複雑さはどうなるでしょうか)。順列を格納するのに適したデータ構造は何で、検索にも効率的ですか?

編集

順列生成部分に関する詳細な回答をありがとう、誰かが良いデータ構造を提案できますか? トライの木しか思い浮かびませんでした。

4

3 に答える 3

6

順列のリストで長さnの文字列のランクを見つけるためのO（n |Σ|）アルゴリズムがあります。ここで、Σはアルファベットです。

アルゴリズム

sの下にランク付けされているすべての順列は、 pcxの形式で一意に記述できます。どこ：

  • pはsの適切なプレフィックスです
  • cは、sのpの直後に表示される文字の下にランク付けされた文字です。また、cはpに含まれないsの部分に出現する文字でもあります。
  • xは、 sで発生する残りの文字の順列です。つまり、pまたはcには含まれません。

sの残りの部分に現れる文字の頻度と、 xが表す順列の数を維持しながら、長さの昇順でsの各接頭辞を反復処理することにより、これらの各クラスに含まれる順列を数えることができます。詳細は読者にお任せします。

これは、関連する算術演算に一定の時間がかかることを前提としています。それはしません。関係する番号はnlog|Σ|を持つことができるので 数字。この考慮事項により、アルゴリズムはO（n 2 log|Σ|log（nlog |Σ|））で実行されます。O（dlogd）の2つのd桁の数値を加算、減算、乗算、除算できるため。

C++の実装

typedef long long int lli;

lli rank(string s){
    int n = s.length();

    vector<lli> factorial(n+1,1);
    for(int i = 1; i <= n; i++)
        factorial[i] = i * factorial[i-1];
    
    vector<int> freq(26);
    lli den = 1;
    lli ret = 0;
    for(int i = n-1; i >= 0; i--){
        int si = s[i]-'a';
        freq[si]++;
        den *= freq[si];
        for(int c = 0; c < si; c++) 
            if(freq[c] > 0) 
                ret += factorial[n-i-1] / (den / freq[c]);
    }
    return ret + 1;
}
于 2012-07-14T15:07:17.000 に答える
4

これは、 quickselect アルゴリズムに似ています。ソートされていない整数の配列で、特定の配列要素のインデックスを見つけます。パーティション要素は、指定された文字列になります。

編集：

実際には、QuickSort で行われるパーティション方法に似ています。指定された文字列はパーティション要素です。すべての順列が生成されると、長さ k の文字列のランクを見つける複雑さは O(nk) になります。再帰を使用して文字列順列を生成し、それらをリンク リストに格納できます。この連結リストを partition メソッドに渡すことができます。

すべての文字列順列を生成する Java コードは次のとおりです。

 private static int generateStringPermutations(String name,int currIndex) {

        int sum = 0;

        for(int j=name.length()-1;j>=0;j--) {
            for(int i=j-1;((i<j) && (i>currIndex));i--) {

                String swappedString = swapCharsInString(name,i,j);
                list.add(swappedString);
                //System.out.println(swappedString);
                sum++;
                sum = sum + generateStringPermutations(swappedString,i);
            }
        }
        return sum;


    }

編集：

すべての順列を生成するにはコストがかかります。文字列に個別の文字が含まれている場合、すべての順列を生成しなくてもランクを決定できます。ここにリンクがあります。

これは、繰り返し文字がある場合に拡張できます。

x * (n-1) の代わりに! これは、リンクのように言及されている個別のケースのためのものです。

繰り返し文字の場合は次のようになります。

2回繰り返される文字が1つある場合、

x* (n-1)!/2!

例を見てみましょう。文字列 abca の組み合わせは次のとおりです。

aabc,aacb,abac,abca,acab,acba,baac,baca, bcaa ,caab, caba , cbaa (ソート順)

組み合わせの合計 = 4!/2! = 12

「bcaa」のランクを見つけたい場合、「a」で始まるすべての文字列が 3 より前にあることがわかります。= 6。

「a」が開始文字であるため、残りの文字は a、b、c で​​あり、繰り返しがないため 3! であることに注意してください。また、「ba」で始まる文字列は 2 より前になることもわかっています。= 2 なのでランクは 9です。

もう一つの例。'caba'のランクを見つけたい場合:

a で始まるすべての文字列は = 6 より前です。b で始まるすべての文字列は = 3!/2! より前です。= 3 (一度 b を選択すると、a、a、c が残り、繰り返しがあるため、3!/2! になります。caa で始まるすべての文字列は、1 になる前になります。

したがって、最終的なランクは 11です。

于 2012-07-14T10:04:07.897 に答える
1

GeeksforGeeksから:

文字列を指定して、辞書式に並べ替えられたすべての順列の中からそのランクを見つけます。たとえば、「abc」のランクは 1、「acb」のランクは 2、「cba」のランクは 6 です。

簡単にするために、文字列に重複する文字が含まれていないと仮定します。

簡単な解決策の 1 つは、ランクを 1 として初期化し、すべての順列を辞書順に生成することです。順列を生成した後、生成された順列が指定された文字列と同じかどうかを確認し、同じ場合はランクを返し、そうでない場合はランクを 1 増やします。このソリューションの時間の複雑さは、最悪の場合指数関数的になります。以下は効率的な解決策です。

与えられた文字列を「STRING」とします。入力文字列では、'S' が最初の文字です。全部で 6 文字あり、そのうち 4 文字は「S」より小さい文字です。したがって、4 * 5 が存在する可能性があります。次のように、最初の文字が 'S' より小さい小さな文字列

RXXXXIXXXXXNXXXXXXGXX XXX

それでは、S' を修正して、'S' で始まる小さな文字列を見つけてみましょう。

T に対して同じプロセスを繰り返します。ランクは 4*5 です。+ 4*4! +…</p>

ここで T を修正し、R について同じプロセスを繰り返します。ランクは 4*5 です! + 4*4! + 3*3! +…</p>

ここで R を修正し、I について同じプロセスを繰り返します。ランクは 4*5 です! + 4*4! + 3*3! + 1*2! +…</p>

ここで I を修正し、N について同じプロセスを繰り返します。ランクは 4*5 です! + 4*4! + 3*3! + 1*2! + 1*1! +…</p>

ここで N を修正し、G について同じプロセスを繰り返します。ランクは 4*5 です! + 4*4 + 3*3! + 1*2! + 1*1! + 0*0!

ランク = 4*5! + 4*4! + 3*3! + 1*2! + 1*1! + 0*0! = 597

ランクの値は 1 から始まるため、最終的なランク = 1 + 597 = 598

于 2013-02-14T21:37:10.647 に答える