Перемешать массив без создания каких-либо пробегов

Question

У меня есть массив из повторяющихся букв:

AABCCD

, и я хотел бы поставить их в псевдослучайной последовательности. Простое право, просто используйте Fisher-Yates => done. Однако на выходе есть ограничение - я не хочу никаких прогонов одной и той же буквы. Я хочу, чтобы по крайней мере два других персонажа появлялись до появления того же символа. Например:

ACCABD

не действует, потому что есть два Cs рядом друг с другом.

ABCACD

также не действует, потому что есть два Кассиопеян рядом друг с другом (CAC) только один другим символом (A) между ними, я требую, по крайней мере, два других символов.

Каждый действительный последовательность для этого простого примера:

ABCADC ABCDAC ACBACD ACBADC ACBDAC ACBDCA ACDABC ACDACB ACDBAC ACDBCA ADCABC ADCBAC BACDAC BCADCA CABCAD CABCDA CABDAC CABDCA CADBAC CADBCA CADCAB CADCBA CBACDA CBADCA CDABCA CDACBA DACBAC DCABCA

Я использовал метод грубой силы для этого небольшого массива, но моей реальной проблемой являются массивы с сотнями элементов. Я пробовал использовать Fisher-Yates с некоторым подавлением - делать нормальные Fisher-Yates, а затем, если вам не нравится персонаж, который появляется, попробуйте X еще раз для лучшего. Генерирует допустимые последовательности только в 87% времени и очень медленный. Удивление, если есть лучший подход. Очевидно, это невозможно для всех массивов. Массив только «AAB» не имеет действительного порядка, поэтому я бы отказался до наилучшего доступного порядка «ABA» для чего-то подобного.

Answer 1

Это модифицированный подход Fisher-Yates. Как я уже упоминал, очень сложно создать допустимую последовательность в 100% случаев, потому что вам нужно проверить, что вы не оказались в ловушке, оставив только AAA в конце вашей последовательности.

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

public static bool Shuffle(char[] array) 
{ 
    var random = new Random(); 
    var groups = array.ToDictionary(e => e, e => array.Count(v => v == e)); 
    char last = '\0'; 
    char lastButOne = '\0'; 
    for (int i = array.Length; i > 1; i--) 
    { 
     var candidates = groups.Keys.Where(c => groups[c] > 0) 
      .Except(new[] { last, lastButOne }).ToList(); 
     if (!candidates.Any()) 
      return false; 

     var @char = candidates[random.Next(candidates.Count)]; 
     var j = Array.IndexOf(array.Take(i).ToArray(), @char); 
     // Swap. 
     var tmp = array[j]; 
     array[j] = array[i - 1]; 
     array[i - 1] = tmp; 
     lastButOne = last; 
     last = @char; 
     groups[@char] = groups[@char] - 1; 
    } 
    return true; 
} 

Answer 2

Поддержание списка ссылок, который будет отслеживать букву и ее позицию в результате.

После получения случайного числа выберите соответствующий символ из ввода (то же, что и Fisher-Yates), но теперь найдите в списке, произошло ли это или нет.

Если нет, вставьте букву в результат, а также в список ссылок с ее положением в результате.

Если да, то проверьте его позицию в результате (который вы сохранили в списке ссылок, когда вы написали это письмо в результате).Теперь сравните это местоположение с текущим местоположением вставки, если mod (currentlocation-previouslocation) равен 3 или больше, вы можете вставить эту букву в результат иначе, если не выбрать случайное число снова.