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

Question

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

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

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

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

Приемлемые результаты были бы:
      {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

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

Answer 2

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

Answer 3

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

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

Answer 4

Я думаю, что вы ищете алгоритм, который: * Может быть использован для отображения итерационного процесса для пользователя, который выглядит как перетасовка * Заканчивается с оригинальным набором разделяться на 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 

Это не дает эффективное статистически хороший тасовать, как Фишер-Йейтс, но действительно дает вам хороший внешний вид на экране.