ひねりを加えた、線形時間で順列を計算する方法

StackOverflow https://stackoverflow.com/questions/483890

  •  20-08-2019
  •  | 
  •  

質問

私は物事を配列決定する必要が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|  1  0  0  0  0
3|  1  0  0  0  0
4|  0  1  0  0  0

長さNのすべての文字列をカウントするための私のソリューションは、空の文字列で始まる最初の数字を入れ替えて、長さN-1のすべての文字列の再帰呼び出しを行いました。再帰呼び出しが追加された最後の数字をチェックして、その数字の隣にすることができ、すべての順列を試してみてください。 03、唯一の02、それは<4000をベースにベース5（一例）からスケールとしての性能はまだ貧弱である - があり、私が試してみて、00を入れ替えないように作られたいくつかの最適化、01、04は、例えば、毎回あります/ P>

それらのすべてを列挙しようとしている以外の順列をカウントするためのより良い方法上の任意の考え？

役に立ちましたか？

解決

あなただけの特定の長さの文字列の数をしたい場合は、

、あなただけの自分自身に数回、互換性マトリックスを掛け、それが値です合計可能性があります。

  

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 のシンボルその次のシンボルです。また、あなたは長さの文字列の数としてそれを見ることができたの記号で始める、2 のは、私はのJ の

をシンボルで終わります

行列の乗算は、累乗の後ので、この不変を維持する A の N の-1 記号で始まる文字列の数が含まれます。のI / EMを> <、長さを有する N 、及びシンボルで終わる J

ウィキペディアを参照してください：マトリックスパワーの速い計算のためのアルゴリズムのための二乗することにより、べき乗<。 / P>

（感謝stefan.ciobaca）

この特定の場合には、式に帰着する：

  

の可能なストリングの数 = 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

他のヒント

あなたはちょうどあなたが与えられた行列のルールを構築することができますどのように多く与えられた長さの文字列を知りたいですか？もしそうなら、このようなアプローチは機能しなければならないこと。

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))

あなたのアルゴリズムが最適であると思われます。

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

をコメントに返信：の

あなただけの、あなたは、動的プログラミングを使用することができ、それらをカウントしたい場合：

[m]は[L] [j]が

、長さLであり、jで終わるような順列の数であるカウント配列、である[N]をカウントしてみましょう

次に、I1、I2、...が先行することができる数字である場合、... [I] [L-1] [I1]カウント= + [L-1] [I2] +カウント[L]を数えますI（これは事前計算アレイに保存することができる）。

カウントのすべてのセルは、複雑さはO（KMN）であるので、Mは置換の長さであり、Nは数字の総数である。、（K互換性マトリックスに依存）K番号を加算することにより充填することができます

たぶん私はこのことを理解していないが、これは各桁のためにそれに従うことができ、有効桁数のリストを持っていることのリストのテーブルを持つことによって提供されることはない。

次に生成するためにあなたのルーチンが蓄積した結果、桁数、および現在の数字がかかります。ような何かます：

// 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);
    }
}

複雑さが発生する桁数の関数として増加するが、その機能が有効の総数に依存するいずれかの数字に続きます。次の数の合計が、のは言わせて、すべての桁で同じである場合、kは、すべての可能な順列を生成するための時間は、nは桁数であるO（K ^ n）があることを行っています。申し訳ありませんが、私は数学を変更することはできません。ベース10にn個の数字を生成するための時間は、10 ^ nである。

私はあなたが求めているものを正確にわからないんだけど、nが潜在的に存在しているので！ n桁の文字列の置換は、あなたは、nよりも速くそれらを一覧表示できるようにするつもりはありません！私はあなたがO（N ^ 2）のランタイムを持ってどのように考えるか正確にはわかりません。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top