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

Question

У меня 11 букв: BDAARARBKAA Мне нужно отсортировать их таким образом, чтобы каждая следующая буква отличалась от предыдущей, например: BDARARABAKA Я пытался сделать так:

bool sort = true;
while (sort)
{
    sort= false;
    for (int i = 1; i <= n-1; i++)
    {
        if (letter[i] == letter[i + 1])
        {
            swap(letter[i], letter[i + 2]);
            sort = true;
        }
    }
}

Но программа не работает. Я не знаю что делать Кто-нибудь может помочь? Я все еще новичок, поэтому я не знаю никаких продвинутых алгоритмов

Answer 1

Вот один из возможных алгоритмов:

Ввод: BDAARARBKAA

Сначала сгруппируйте буквы и отсортируйте по количеству:

A 5
B 2
R 2
D 1
K 1

Убедитесь, что самый высокий количество не больше int((N+1)/2)

Заполните слоты, начиная с самой большой группы, и оставьте пустое место между равными буквами, как это:

A.A.A.A.AB.

Затем заполните остальные букв:

A.A.A.A.AB.
 B R R D  K

Результат:

ABARARADABK

Answer 2

Я знаю, что это будет непрактично для длинных струн, но в любом случае я покажу подход грубой силы.

Просто go через все перестановки в строке и, если рядом нет равных элементов, покажите это как один из возможных результатов.

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

Я подумаю больше о проблеме и, возможно, подберу лучший алгоритм. , .

Пожалуйста, смотрите:

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

#define InputFromUser 0

int main() {
#if InputFromUser
    // Ask the user to enter a string (a line of char)
    std::cout << "Please enter a string:\n";

    // Get a line from the user
    if (std::string line{}; std::getline(std::cin, line) && !line.empty()) {
#else
    // A test input string
    std::string line{ "BDAARARBKAA" };
#endif
    // Sort all letters in string
//  std::sort(line.begin(), line.end());
    // Go through all permutations
    do {
        // Check, if we have 2 consecutive equal characters
        if (std::adjacent_find(line.begin(), line.end()) == line.end()) {
            // If not, then show a result
            std::cout << line << "\n";
            // Stop searching. If you remove this statement, then you will get all solutions 
            // But all solutions might be astronomically long
            break;
        }
    } while (std::next_permutation(line.begin(), line.end()));

#if InputFromUser
    }
#endif
return 0;
}