7

Java で物事を順序付けする必要があるリソース スケジューリングの問題がありますが、隣り合うリソースには制限があります。良い例えは、特定の数字のみが隣り合うことができる「数字」の文字列です。私の解決策は再帰的で、小さな文字列に対しては問題なく動作しますが、実行時間は O(X^N) です。ここで、X は可能な桁数 (ベース) であり、N は文字列の長さです。すぐに手に負えなくなります。

以下の互換性マトリックスを使用して、使用できる文字列の例をいくつか示します
。 長さ 1: 0、1、2、3、4
長さ 2:
02、03、14、20、30、41 長さ 3: 020、030 141、202、203、302、303、414

     0 1 2 3 4
   ----------------------
0| 0 0 1 1 0
1| 0 0 0 0 1
2| 10000
3| 10000
4| 0 1 0 0 0

長さ N のすべての文字列をカウントするための私の解決策は、空の文字列で開始し、最初の桁を並べ替え、長さ N-1 のすべての文字列に対して再帰呼び出しを行うことでした。再帰呼び出しは、追加された最後の数字をチェックし、その数字の隣にある可能性のあるすべての順列を試します。毎回 00、01、04 を並べ替えようとしないように、いくつかの最適化が行われています。

それらをすべて列挙しようとする以外に、順列を数えるより良い方法について何か考えはありますか?

4

5 に答える 5

19

特定の長さの文字列の数だけが必要な場合は、互換性マトリックスをそれ自体で数回掛けて、その値を合計することができます。

n =文字列の長さ
A =可能な文字列の互換性マトリックス
数= A の合計n -1

いくつかの例:

n = 1
| 1 0 0 0 0 |
| 0 1 0 0 0 |
| 0 0 1 0 0 |
| 0 0 0 1 0 |
| 0 0 0 0 1 |
sum: 5

n = 3
| 2 0 0 0 0 |
| 0 1 0 0 0 |
| 0 0 1 1 0 |
| 0 0 1 1 0 |
| 0 0 0 0 1 |
sum: 8

n = 8
| 0 0 8 8 0 |
| 0 0 0 0 1 |
| 8 0 0 0 0 |
| 8 0 0 0 0 |
| 0 1 0 0 0 |
sum: 34

元の行列 (行i、列j ) は、記号iで始まり、次の記号が記号jである文字列の数と考えることができます。または、記号iで始まり記号jで終わる、長さ2の文字列の数として表示することもできます。

行列の乗算ではこの不変式が保持されるため、べき乗の後、A n -1には、記号iで始まり、長さがnで、記号jで終わる文字列の数が含まれます。

ウィキペディア:行列のべき乗を高速に計算するためのアルゴリズムについては、 2 乗によるべき乗を参照してください。

(ステファン・シオバカに感謝)

この特定のケースは、式に還元されます。

可能な文字列の数= f ( n ) = 4 + Σ k =1.. n 2 ⌊ k -1 ⁄ 2 ⌋ = f ( n -1) + 2 ⌊ n -1 ⁄ 2 ⌋

n       f(n)
----    ----
   1       5
   2       6
   3       8
   4      10
   5      14
   6      18
   7      26
   8      34
   9      50
  10      66
于 2009-01-27T16:35:42.560 に答える
3

与えられた行列のルールを使用して、与えられた長さの文字列をいくつ作成できるか知りたいだけですか? もしそうなら、このようなアプローチがうまくいくはずです：

n = 5
maxlen = 100

combine = [
      [0, 0, 1, 1, 0],
      [0, 0, 0, 0, 1],
      [1, 0, 0, 0, 0],
      [1, 0, 0, 0, 0],
      [0, 1, 0, 0, 0]
   ]

# counts of strings starting with 0,1,...,4, initially for strings of length one:
counts = [1, 1, 1, 1, 1]

for size in range(2, maxlen+1):
   # calculate counts for size from count for (size-1)
   newcount = []
   for next in range(n):
      total = 0
      for head in range(n):
         if combine[next][head]:
            # |next| can be before |head|, so add the counts for |head|
            total += counts[head]
      # append, so that newcount[next] == total
      newcount.append(total)
   counts = newcount
   print "length %i: %i items" % (size, sum(counts))
于 2009-01-27T16:05:48.783 に答える
2

あなたのアルゴリズムは最適なようです。

これらの順列をどのように使用していますか? それらを 1 つのリストに蓄積していますか、それとも 1 つずつ使用していますか? このような順列は膨大な数あるため、メモリの使用量が多いため (すべてを収集している場合)、パフォーマンスが低下するか、時間がかかりすぎます。些細な時間で何十億ものループを実行することはできません。

コメントへの返信:

それらを数えたいだけなら、動的計画法を使用できます。

count[n][m] を配列とします。ここで、count[l][j] は長さ l で j で終わる順列の数です。

次に、count[l][i] = count[l-1][i1]+count[l-1][i2]+...、ここで、i1、i2、... は i に先行する数字です (これは事前に計算された配列に保存できます)。

count のすべてのセルは、K 個の数 (K は互換性のある行列によって異なります) を合計することで満たすことができるため、複雑さは O(KMN) であり、M は順列の長さ、N は総桁数です。

于 2009-01-27T16:06:05.100 に答える
1

あなたが何を求めているのか正確にはわかりませんが、潜在的に n! n 桁の文字列の順列の場合、n! よりも速くリストすることはできません。O(n^2) のランタイムをどのように考えているのか正確にはわかりません。

于 2009-01-27T16:18:05.623 に答える
1

多分私はこれを理解していませんが、これは、各数字に続く有効な数字のリストを持つリストのテーブルを持つことによって提供されません。

次に、生成するルーチンは、累積結果、桁数、および現在の桁を取得します。何かのようなもの：

// not really Java - and you probably don't want chars, but you'll fix it
void GenerateDigits(char[] result, int currIndex, char currDigit)
{
    if (currIndex == kMaxIndex) {
        NotifyComplete(result);
        return;
    }
    char[] validFollows = GetValidFollows(currDigit); // table lookup
    foreach (char c in validFollows) {
        result[currIndex] = c;
        GenerateDigits(result, currIndex+1, c);
    }
}

複雑さは、生成する桁数の関数として増加しますが、その関数は、任意の 1 つの桁の有効なフォローの総数に依存します。フォローの総数がすべての桁で同じである場合、たとえば k とすると、すべての可能な順列を生成する時間は O(k^n) になります。ここで、n は桁数です。申し訳ありませんが、数学を変更することはできません。基数 10 で n 桁を生成する時間は 10^n です。

于 2009-01-27T15:53:37.013 に答える