Минимизируйте количество последовательных равных извлечений в деке карты <строка, строка>

Question

Надеюсь, это место лучше всего подходит для такого рода вопросов.

У меня следующая проблема (думаю, она сложнее, чем кажется).

Я используюДвухсторонняя очередь (deque) структура данных строк.deque extractions;

Deque содержит только N различных строк, каждая строка повторяется M раз в случайном порядке, так что длина deque равна 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"

Я нахожусь в поиске алгоритма, который позволяет мне найти интересную конфигурацию, в которой нет двух последовательных равныхэлементов, в этом случае должно быть только два решения: «А», «В», «А», «В», «А», «В», «А», «В» и «В»,«А», «В», «А», «В», «А», «В», «А».Для «интересной» конфигурации я имею в виду конфигурацию, не просто заданную числом вложенных циклов N.

Очень глупое решение, которое я реализовал, состоит в том, чтобы случайным образом перетасовать колоду с std::random_shuffle до тех пор, пока не произойдет последовательное равноеэлементы найдены, но это и глупо, и медленно, это больше похоже на bogosort ...

Очевидно, что максимальное увеличение расстояния редактирования между строками должно быть лучше.Какой-то намек?

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

Это должно очень быстро оставить вас со случайной конфигурацией, которая удовлетворяет вашему требованию отсутствия двух последовательных равных элементов.

Answer 2

Я бы сделал это с рекурсией:

пример в 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 (для 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);

Answer 3

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

Этот код не тестировался, но вы поняли.