2

我希望这个地方最适合这类问题。

我有以下问题（我认为比看起来更复杂）。

我正在使用字符串的双端队列（deque）数据结构。deque <字符串> 提取；

deque 只包含 N 个不同的字符串，每个字符串以随机顺序重复 M 次，因此 deque 的长度为 N*M，例如假设 M=4, N=2, string1="A", string2= “乙”：

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

我正在寻找一种算法，它可以让我找到一个有趣的配置，其中没有两个连续的相等元素，在这种情况下应该只有两个解决方案，“A”，“B”，“A”， "B","A","B","A","B" 和 "B","A","B","A","B","A","B","一种”。对于“有趣”的配置，我的意思不是简单地由 N 个嵌套循环给出的配置。

我实施的一个非常愚蠢的解决方案是随机洗牌，std::random_shuffle直到没有找到连续相等的元素，但这既愚蠢又缓慢，这更像是一个 bogosort ......

显然最大化字符串之间的编辑距离应该更好。一些提示？

4

3 回答 3

1

从一个简单的配置开始，例如对于 N=4 和 M=4，从

ABCDABCDABCDABCD

然后运行一个标准的洗牌算法，但要遵守不要让两个相等的元素彼此相邻的约束，即

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

这应该会很快为您提供一个随机配置，以满足您不具有两个连续相等元素的要求。

于 2011-12-02T12:59:20.433 回答
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 回答
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 );

但是，如果您只想要一个可能的解决方案（当然计算起来要快得多）：

它将为您创建一个随机的、非平凡的解决方案，例如：CACBCBCABABACAB (for 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 回答