5

注文されたが一意ではないアイテムのリスト (プレイリスト) を削減するアルゴリズムを探しています。集合論を検索しましたが、適切なものはまだ見つかりませんでした

例

[a, b, b, c] -> [a, b, b, c] Cannot be reduced. 
[a, b, b, a, b, b] -> [a, b, b]. 
[b, b, b, b, b] -> [b]. 
[b, b, b, b, a] -> [b, b, b, b, a] Cannot be reduced.

既存のすべてのサブリストを取得し、各インスタンスをカウントすることを考えています。カウントにサブリストの長さを掛けた値が元のリストと等しいサブリストがある場合は、この基準に一致する最短のサブリストを取得します。

これは少し力ずくのように思えます。よりシンプルで高速なソリューションが利用できるはずです。

4

4 に答える 4

3

まず、すべてのサブリストをチェックする必要はありません。完全なリストの長さの要素である長さを持つものだけです。

生の速度よりもコーディングの単純さが主な関心事である場合は、正規表現エンジンに問題を解決させてください。

/^(.+?)\1+$/

これは、素数を見つけるための Abigail の素晴らしい Perl 正規表現の変形です。

于 2010-11-28T21:40:05.610 に答える
2

それぞれn <= N(Nはリストの長さ) について、nが の因数である場合N。nそうである場合は、最初の文字のサブリストを繰り返して元のリストが生成されるかどうかを確認します。一致する場合は、潜在的な答えが見つかりました (答えは最短です)。これO(N^2)により、最悪の場合でもブルートフォースと同じ程度の効率になります。

たとえば、長さ 2 のサブリストが最初の 4 文字を正常に生成するが完全なリストを生成しない場合、長さ 4 のサブリストは失敗することに注意して、いくつかのプルーニングを行うことができます。そのようなすべてのサブリストの長さのリストをチェックしないように保持することができ、これにより一部の計算が削減されます。

于 2010-11-28T21:36:11.413 に答える
0

これは、ほぼ線形時間で実行する必要があるいくつかの単純なコードです (最悪の場合、O(n lg lg n) と思いますが、より高度な数学に依存しています)。

f(x) {
  i = 1;
  while (i <= size(x) / 2) {
    if (size(x) % i != 0) { i++; continue;}
    b = true;
    for (j = 0; j + i < x.size(); j++) {
      if (x[i] != x[j]) {
        b = false;
        break;
      }
    }
    if (b) return i;
    i = max(i + 1, j / i * i / 2); // skip some values of i if j is large enough
  }
  return -1;
}

基本的に、上記は素朴なアルゴリズムを実行しますが、以前の「ニアミス」のために不可能であることが知られているいくつかの周期性をスキップします。たとえば、期間 5 を試して "aaaabaaaabaaaabaaaabab" が表示された場合、5 の繰り返しが 4 サイクルあり、その後失敗したため、6、7、...、10 を安全にスキップできます。

最終的には、線形量の作業に加えて、O(n lg lg n) によって制限される n の除数の合計である sigma(n) で線形の作業量を加えることになります。

*このスキップの正しさを証明することは非常に微妙であり、詳細に間違いを犯した可能性があることに注意してください-コメントを歓迎します.

于 2010-11-29T02:36:34.047 に答える
0

すべてのセット要素を素数でエンコードします。

元：

a -> 2
b -> 3
c -> 5

等

ここで、維持するためにさらに 2 つのリストが必要です。

最初のリストは素数用で、2 番目はその指数用です。

アイデアは次のとおりです。要素に出くわしたら、それが素数であり、連続して何回出現するかを記録します。

の場合[a, b, b, c]、次のようになります。

[2, 3, 3, 5]

次のように記録できます。

[2, 3^2, 5]

または、より正確には：

[2^1, 3^2, 5^1]

2 つのリストを維持します。

[2,3,5]  // primes in succession - list [p]
[1,2,1]  // exponents - list [e]

ここで、最初の要素 [p]^[e] が最後の要素と同じかどうかをチェックして、これら 2 つのリストを端から端まで反復します。そうである場合は、最後から次の 2 番目など... それらがすべて同じである場合は、リストを減らすことができます。

この例では、次のことを確認します2^1*5^1 == 3^2*3^2。そうではないので、減らすことはできません。

試してみましょう[a, b, b, a, b, b]：

これは次のようにエンコードされます。

[2^1, 3^2, 2^1, 3^2]

また、

[2, 3, 2, 3]  // primes
[1, 2, 1, 2]  // exponents

ここで、2^1 * 3^2 == 3^2 * 2^1(最初の素数、最初の指数に最後の素数を掛けたもの、最後の指数、そして 2 番目と最後から 2 番目のものを比較するかどうか) をチェックします。

これが成り立つので、還元可能です。

試してみましょう[b, b, b, b, b]：

これは次のようにエンコードできます。

[3^5]

また、

[3]  // primes
[5]  // exponents

これは特殊なケースです: 要素リストが 1 つある場合、元のリストは簡約可能です。

試してみましょう[b, b, b, b, a]：

これは次のようにエンコードできます。

[3^4, 2^1]

また、

[3, 2]  // primes
[4, 1]  // exponents

かどうかを確認3^4 == 2^1しますが、そうではないため、リストは縮小できません。

試してみましょう[a, b, a, b, a, b]：

これは次のようにエンコードできます。

[2^1, 3^1, 2^1, 3^1, 2^1, 3^1]

また、

[2, 3, 2, 3, 2, 3]
[1, 1, 1, 1, 1, 1]

上記の手順を試すとうまくいきます。2^1 * 3^1 == 3^1 * 2^1 == 2^1 * 3^1

したがって、アルゴリズムは次のようになります。

すべての数値を素数にエンコードします。

リストを反復処理し、2 つのリストを作成して、説明どおりに入力します

2 つのリスト と ができpたのでe、どちらも長さを持っnています。

var start = p[0]^e[0] * p[n-1]^e[n-1]
var reducible = true;

for (int i = 0; i < n/2, ++i) :
   if ( (p[i]^e[i] * p[n-i]^e[n-i]) != start ) :
       reducible = false;
       break;

注: このアルゴリズムを実際にコーディングして、さまざまな入力に対して試してみたわけではありません。それはただのアイデアです。また、リストが縮約可能である場合、その長さと の長さからn、元のリストを基本的な形に縮約する方法を理解するのはそれほど難しくありません。

2 番目の注意: 誰かが上記の間違いを見つけた場合は、訂正してください。遅くて私の集中力が最適ではないため、これが実際に機能しない可能性があります.

于 2010-11-28T22:42:56.260 に答える