2

このような質問には、この場所が最適だと思います。

私は次の問題を抱えています（見た目よりも複雑だと思います）。

文字列の両端キュー (deque) データ構造を使用しています。deque < 文字列 > 抽出。

両端キューには N 個の異なる文字列のみが含まれ、各文字列はランダムな順序で M 回繰り返されるため、両端キューの長さは N*M になります。たとえば、M=4、N=2、string1="A"、string2= とします。 "B":

extractions[1] = "A"
extractions[2] = "A"
extractions[3] = "B"
extractions[4] = "B"
extractions[5] = "A"
extractions[6] = "B"
extractions[7] = "B"
extractions[8] = "A"

私は、2 つの連続した等しい要素が存在しない興味深い構成を見つけることができるアルゴリズムを探しています。この場合、「A」、「B」、「A」 「B」、「A」、「B」、「A」、「B」および「B」、「A」、「B」、「A」、「B」、「A」、「B」、」あ」。「興味深い」構成とは、ネストされたループの数 N によって単純に与えられない構成を意味します。

私が実装した非常にばかげた解決策はstd::random_shuffle、連続する等しい要素が見つからなくなるまでデッキをランダムにシャッフルすることですが、これはばかげていると同時に遅く、ボゴソートのようなものです...

文字列間の編集距離を明らかに最大化する方がよいはずです。何かヒント？

4

3 に答える 3

1

些細な構成から始めます。たとえば、N=4およびM=4の場合、

ABCDABCDABCDABCD

次に、標準のシャッフルアルゴリズムを実行しますが、2つの等しい要素を隣り合わせにしないという制約を確認します。

for i = 0 .. N*M - 2
  let j = random(N*M - 2 - i) + i + 1
    if ((i == 0 || array[i - 1] != array[j])
        && (array[i + 1] != array[j])
        && (array[i] != array[j - 1])
        && (j == N*M - 1 || array[i] != array[j + 1]))
      swap (array[i], array[j])

これにより、2つの連続する等しい要素がないという要件を満たすランダムな構成がすぐに得られます。

于 2011-12-02T12:59:20.433 に答える
0

私は再帰でそれを行います：

例はC＃にあります：ネストされたループよりも「話す」ことが多いと思います：

public List<String> GetPermutations(string s, IEnumerable<String> parts, string lastPart, int targetLength)
{
    List<String> possibilities = new List<string>();

    if (s.Length >= targetLength)
    {
        possibilities.Add(s);
        return possibilities;
    }

    foreach (String part in parts)
    {
        if (!part.Equals(lastPart))
        {
            possibilities.AddRange(
               GetPermutations(s + part, parts, part, targetLength));
        }
    }

    return possibilities;
}

利用方法：

List<String> parts = new List<String>() { "A", "B", "C"};
int numOccurences = 4;

List<String> results = 
    GetPermutations("", parts, "", numOccurences * parts.Count );

しかし、可能性のあるソリューションが 1 つだけ必要な場合 (もちろん、計算する方がはるかに高速です):

次のようなランダムで自明でないソリューションを作成します： CACBCBCABABACAB （A、B、Cの場合）

public String GetRandomValidPermutation(
     string s, 
     List<String> parts, 
     string lastPart, 
     int targetLength)
{
    if (s.Length >= targetLength)
    {
        return s;
    }

    String next = String.Empty; 
    while(
      (next = parts[new Random().Next(0, parts.Count)])
      .Equals(lastPart)
    ){}

    return GetRandomValidPermutation(s + next, parts, next, targetLength);
}

電話：

String validString = 
    GetRandomValidPermutation("", parts, "", numOccurences * parts.Count);
于 2011-12-02T12:00:44.657 に答える
0 
int total = m * n;

for (int i = 1; i < total - 1; i++)
  {
    int j = total - 1;
    while ((j > i) && (queue[i - 1] == queue[j]))
      j--;
    if (queue[i - 1] == queue[j])
      {
        String aux = queue[i - 1];
        queue[i - 1] = queue[j];
        queue[j] = aux;
      }
  }

このコードはテストされていませんが、アイデアは得られます。

于 2011-12-02T11:36:16.007 に答える