Как я могу перемешать список без случайности и гарантировать, что часть элементов в конечном итоге появится на одной стороне?

Question

Учитывая список элементов, существует ли алгоритм перетасовки, который будет гарантировать, что в конечном итоге выбранная половина будет с одной стороны, а оставшаяся - с другой?

Пример: {4, 3, 10, 7, 2, 9, 6, 8, 1, 5}

Учитывая вышеизложенное, я хотел бы иметь алгоритм микширования, который в конечном итоге перемещает отмеченные влево, даже если сам алгоритмпонятия не имеет, что такое и не «помечено».

{4, 3, 10, 7, 2, 9, 6, 8, 1, 5}
XXXXX

Приемлемые результаты:
{4, 10, 9, 6, 1, 3, 7, 2, 8, 5}
{1, 9, 10, 4, 6, 2, 8, 5, 7, 3}
{1, 4, 9, 10, 6, 3, 7, 5, 8, 2} и т. Д.

Сложность: Алгоритм не должениспользуйте случайные числа, чтобы смешать содержимое, это должен быть итеративный процесс. Значит, Фишер-Йейтс вышел.

Answer 1

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

Answer 2

Будет ли std::next_permutation() тем, что вы хотите? (Поскольку он создает всех возможных перестановок , он, в конце концов, также поместит помеченный один раз влево)

Answer 3

Я думаю, что вы ищете алгоритм, который: * Может использоваться для отображения итеративного процесса для пользователя, который выглядит как перетасовка * Завершает исходный набор, разделенный на 2 (предварительно выбранные) группы, но случайным образом упорядоченный в каждой группе

Мне кажется, что вам может пригодиться что-то простое, подумайте о десяти числах и, используя алгоритм, помеченный / немаркированный для групп, этот алгоритм:

1. Randomly select two members of the set
2. if swapping these two members would result in a marked number 
     being moved into positions 1-5 then forget about this swap and start again
3. Swap these elements
4. Check if positions 1-5 have ONLY marked elements, 
     if so you are done, otherwise start again

Это не дает эффективного статистически хорошего перетасовки, как у Фишера-Йейтса, но дает вам хорошо выглядящее на экране смешение.

Answer 4

Что-то вроде next_permutation выполнит работу, и (в конце концов) так же будет что-то вроде сортировки bogo.Любая из них в конечном итоге приведет к каждой возможной перестановке, включая все перестановки, которые вы считаете приемлемыми (наряду с некоторым произвольным числом, которое вы не делаете).

Сортировка Bogo показывает, что ваше: «Алгоритм не должен использовать случайные числа для смешиваниясодержание, это должен быть итеративный процесс. Так что Фишер-Йейтс вышел ".ложная дихотомияСортировка Bogo перемешивает случайным образом и , это итеративно.