Перетасовка строки так, чтобы две соседние буквы не совпадали

Ответ 1

Вы можете отсортировать буквы по частоте, разбить отсортированный список пополам и построить вывод, взяв буквы из двух половинок по очереди. Это займет один вид.

Пример:

• Начальная строка: ACABBACAB
• Сортировка: AAAABBBCC
• Разделить: AAAA + BBBCC
• Объединить: ABABABCAC

Если число букв с наибольшей частотой превышает половину длины строки, проблема не имеет решения.

Ответ 2

Почему бы не использовать две структуры данных: одну для сортировки (как кучу) и одну для поиска ключей, например, словарь?

Ответ 3

Принятый ответ может привести к правильному результату, но, скорее всего, это не "правильный" ответ на этот опрос, а также самый эффективный алгоритм.

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

Ниже приведен пример С#, похожий на сортировку вставки для простоты (хотя многие алгоритмы сортировки можно было бы точно настроить):

string NonAdjacencySort(string stringInput)
{
    var input = stringInput.ToCharArray();

    for(var i = 0; i < input.Length; i++)
    {
        var j = i;

        while(j > 0 && j < input.Length - 1 && 
              (input[j+1] == input[j] || input[j-1] == input[j]))
        {
            var tmp = input[j];
            input[j] = input[j-1];
            input[j-1] = tmp;           
            j--;
        }

        if(input[1] == input[0])
        {
            var tmp = input[0];
            input[0] = input[input.Length-1];
            input[input.Length-1] = tmp;
        }
    }

    return new string(input);
}

Основное изменение стандартной сортировки вставки заключается в том, что функция должна смотреть вперед и назад и, следовательно, должна обернуться к последнему индексу.

Конечная точка заключается в том, что этот тип алгоритма изящно выходит из строя, обеспечивая результат с наименьшими последовательными символами (сгруппированными спереди).

Ответ 4

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

Алгоритм довольно прост, на самом деле. Это основано на наблюдении, что если мы отсортируем строку, а затем разделим ее на две половинки равной длины плюс средний символ, если строка имеет нечетную длину, то соответствующие позиции в этих двух половинах должны отличаться друг от друга, если только нет решение. Это легко увидеть: если два символа одинаковы, то так же и все символы между ними, что составляет ⌈n/2⌉+1 символ. Но решение возможно только в том случае, если существует не более ⌈n/2⌉ экземпляров любого отдельного символа.

Поэтому мы можем действовать следующим образом:

1. Сортируй строку.
2. Если длина строки нечетная, выведите средний символ.
3. Разделите строку (минус ее средний символ, если длина нечетная) на две половинки равной длины и чередуйте две половины.
4. В каждой точке чередования, поскольку пара символов отличается друг от друга (см. Выше), по крайней мере один из них должен отличаться от последнего вывода символов. Итак, мы сначала выводим этот символ, а затем соответствующий из другой половины.

Пример кода ниже находится в C++, так как у меня нет среды С#, удобной для тестирования. Это также упростило два способа, оба из которых было бы достаточно легко исправить за счет затенения алгоритма:

• Если в какой-то момент перемежения алгоритм встречает пару идентичных символов, он должен остановиться и сообщить об ошибке. Но в приведенном ниже примере реализации, который имеет слишком простой интерфейс, нет способа сообщить о сбое. Если решения не существует, приведенная ниже функция возвращает неверное решение.

• ОП предполагает, что алгоритм должен работать с символами Юникода, но сложность правильной обработки многобайтовых кодировок, кажется, не добавляет ничего полезного для объяснения алгоритма. Поэтому я просто использовал однобайтовые символы. (В С# и некоторых реализациях C++ не существует типа символов, достаточно широкого, чтобы содержать кодовую точку Unicode, поэтому символы астральной плоскости должны быть представлены суррогатной парой.)

#include <algorithm>
#include <iostream>
#include <string>

// If possible, rearranges 'in' so that there are no two consecutive
// instances of the same character. 
std::string rearrange(std::string in) {
  // Sort the input. The function is call-by-value,
  // so the argument itself isn't changed.
  std::string out;
  size_t len = in.size();
  if (in.size()) {
    out.reserve(len);
    std::sort(in.begin(), in.end());
    size_t mid = len / 2;
    size_t tail = len - mid;
    char prev = in[mid]; 
    // For odd-length strings, start with the middle character.
    if (len & 1) out.push_back(prev);
    for (size_t head = 0; head < mid; ++head, ++tail) 
      // See explanatory text
      if (in[tail] != prev) {
        out.push_back(in[tail]);
        out.push_back(prev = in[head]);
      }
      else {
        out.push_back(in[head]);
        out.push_back(prev = in[tail]);
      }
    }
  }
  return out;
}

Ответ 5

Вот вероятностный подход. Алгоритм:

10) Выберите случайный символ из входной строки.
20) Попробуйте вставить выбранный символ в случайную позицию в выходной строке.
30) Если его нельзя вставить из-за близости с одним и тем же символом, перейдите к 10.
40) Удалите выбранный символ из строки ввода и перейдите к 10.
50) Продолжайте, пока во входной строке больше не останется символов или не будет слишком много неудачных попыток.

public static string ShuffleNoSameAdjacent(string input, Random random = null)
{
    if (input == null) return null;
    if (random == null) random = new Random();
    string output = "";
    int maxAttempts = input.Length * input.Length * 2;
    int attempts = 0;
    while (input.Length > 0)
    {
        while (attempts < maxAttempts)
        {
            int inputPos = random.Next(0, input.Length);
            var outputPos = random.Next(0, output.Length + 1);
            var c = input[inputPos];
            if (outputPos > 0 && output[outputPos - 1] == c)
            {
                attempts++; continue;
            }
            if (outputPos < output.Length && output[outputPos] == c)
            {
                attempts++; continue;
            }
            input = input.Remove(inputPos, 1);
            output = output.Insert(outputPos, c.ToString());
            break;
        }
        if (attempts >= maxAttempts) throw new InvalidOperationException(
            $"Shuffle failed to complete after {attempts} attempts.");
    }
    return output;
}

Не подходит для строк длиной более 1000 символов!

Обновление: А вот и более сложный детерминированный подход. Алгоритм:

1. Группируйте элементы и сортируйте группы по длине.
2. Создайте три пустые груды элементов.
3. Вставьте каждую группу в отдельную стопку, всегда вставляя наибольшую группу в наименьшую стопку, так чтобы стопки отличались по длине как можно меньше.
4. Убедитесь, что нет кучи с более чем половиной всех элементов, и в этом случае выполнить условие отсутствия одинаковых смежных элементов невозможно.
5. Перемешать груды.
6. Начните собирать элементы из куч, каждый раз выбирая новую кучу.
7. Когда сваи, которые могут быть выбраны более одного, выбирают случайным образом, взвешивая по размеру каждой кучи. Сваи, содержащие около половины оставшихся элементов, должны быть очень предпочтительными. Например, если оставшиеся элементы равны 100, а две подходящие сваи имеют 49 и 40 элементов соответственно, то первая куча должна быть в 10 раз более предпочтительной, чем вторая (потому что 50 - 49 = 1 и 50 - 40 = 10).

    public static IEnumerable<T> ShuffleNoSameAdjacent<T>(IEnumerable<T> source,
        Random random = null, IEqualityComparer<T> comparer = null)
    {
        if (source == null) yield break;
        if (random == null) random = new Random();
        if (comparer == null) comparer = EqualityComparer<T>.Default;
        var grouped = source
            .GroupBy(i => i, comparer)
            .OrderByDescending(g => g.Count());
        var piles = Enumerable.Range(0, 3).Select(i => new Pile<T>()).ToArray();
        foreach (var group in grouped)
        {
            GetSmallestPile().AddRange(group);
        }
        int totalCount = piles.Select(e => e.Count).Sum();
        if (piles.Any(pile => pile.Count > (totalCount + 1) / 2))
        {
            throw new InvalidOperationException("Shuffle is impossible.");
        }

        piles.ForEach(pile => Shuffle(pile));
        Pile<T> previouslySelectedPile = null;
        while (totalCount > 0)
        {
            var selectedPile = GetRandomPile_WeightedByLength();
            yield return selectedPile[selectedPile.Count - 1];
            selectedPile.RemoveAt(selectedPile.Count - 1);
            totalCount--;
            previouslySelectedPile = selectedPile;
        }

        List<T> GetSmallestPile()
        {
            List<T> smallestPile = null;
            int smallestCount = Int32.MaxValue;
            foreach (var pile in piles)
            {
                if (pile.Count < smallestCount)
                {
                    smallestPile = pile;
                    smallestCount = pile.Count;
                }
            }
            return smallestPile;
        }

        void Shuffle(List<T> pile)
        {
            for (int i = 0; i < pile.Count; i++)
            {
                int j = random.Next(i, pile.Count);
                if (i == j) continue;
                var temp = pile[i];
                pile[i] = pile[j];
                pile[j] = temp;
            }
        }

        Pile<T> GetRandomPile_WeightedByLength()
        {
            var eligiblePiles = piles
                .Where(pile => pile.Count > 0 && pile != previouslySelectedPile)
                .ToArray();
            Debug.Assert(eligiblePiles.Length > 0, "No eligible pile.");
            eligiblePiles.ForEach(pile =>
            {
                pile.Proximity = ((totalCount + 1) / 2) - pile.Count;
                pile.Score = 1;
            });
            Debug.Assert(eligiblePiles.All(pile => pile.Proximity >= 0),
                "A pile has negative proximity.");
            foreach (var pile in eligiblePiles)
            {
                foreach (var otherPile in eligiblePiles)
                {
                    if (otherPile == pile) continue;
                    pile.Score *= otherPile.Proximity;
                }
            }
            var sumScore = eligiblePiles.Select(p => p.Score).Sum();
            while (sumScore > Int32.MaxValue)
            {
                eligiblePiles.ForEach(pile => pile.Score /= 100);
                sumScore = eligiblePiles.Select(p => p.Score).Sum();
            }
            if (sumScore == 0)
            {
                return eligiblePiles[random.Next(0, eligiblePiles.Length)];
            }
            var randomScore = random.Next(0, (int)sumScore);
            int accumulatedScore = 0;
            foreach (var pile in eligiblePiles)
            {
                accumulatedScore += (int)pile.Score;
                if (randomScore < accumulatedScore) return pile;
            }
            Debug.Fail("Could not select a pile randomly by weight.");
            return null;
        }
    }

    private class Pile<T> : List<T>
    {
        public int Proximity { get; set; }
        public long Score { get; set; }
    }

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