Перемешать список, гарантируя, что элемент не останется в одном положении

Я хочу перетасовать список уникальных предметов, но не делаю полностью случайное перемешение. Я должен быть уверен, что ни один элемент в перетасованном списке не будет находиться в том же месте, что и в исходном списке. Таким образом, если исходный список (A, B, C, D, E), этот результат будет ОК: (C, D, B, E, A), но это не будет: (C, E, A, D, B), поскольку «D» по-прежнему остается четвертым. Список будет содержать не более семи позиций. Крайняя эффективность – это не соображение. Я думаю, что эта модификация Fisher / Yates делает трюк, но я не могу доказать это математически:

function shuffle(data) { for (var i = 0; i < data.length - 1; i++) { var j = i + 1 + Math.floor(Math.random() * (data.length - i - 1)); var temp = data[j]; data[j] = data[i]; data[i] = temp; } } 

    3 Solutions collect form web for “Перемешать список, гарантируя, что элемент не останется в одном положении”

    Вы ищете нарушение своих записей.

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

    Одним из возможных решений, предложенным в комментариях, было бы использование алгоритма отклонения:

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

    Асимптотически вероятность получения нарушения близка к 1/e = 0,3679 (как видно из статьи в Википедии). Это означает, что для того, чтобы получить нарушение, вам нужно будет создать среднее значение e = 2.718 перестановок, что довольно дорого.

    Лучший способ сделать это – отказаться от каждого шага алгоритма. В псевдокоде что-то вроде этого (если исходный массив содержит i в позиции i , т. a[i]==i ):

     for (i = 1 to n-1) { do { j = rand(i, n) // random integer from i to n inclusive } while a[j] != i // rejection part swap a[i] a[j] } 

    Основное отличие от вашего алгоритма состоит в том, что мы позволяем j быть равным i , но только если он не создает фиксированную точку. Это немного длиннее для выполнения (из-за части отказа) и требует, чтобы вы могли проверить, находится ли запись в ее первоначальном месте или нет, но она имеет то преимущество, что она может производить все возможные нарушения (равномерно для этого дело).

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

    Редактировать:

    Мой алгоритм на самом деле плох: у вас все еще есть шанс закончить с последней точкой unshuffled, и распределение не является случайным вообще, см. Предельные распределения моделирования: предельные распределения

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

    Второе редактирование:

    На самом деле ваш алгоритм известен как алгоритм Саттоло и , как известно, производит все циклы с равной вероятностью. Таким образом, любой алгоритм, не являющийся циклом, а произведением нескольких непересекающихся циклов, не может быть получен с помощью алгоритма. Например, с четырьмя элементами перестановка, которая обменивается 1 и 2 и 3 и 4, является расстройством, но не циклом.

    Если вы не возражаете получить только циклы, то алгоритм Саттоло – это путь, который на самом деле намного быстрее, чем любой унифицированный алгоритм нарушения, поскольку отклонений не требуется.

    Как отметил @FelixCQ, перетасовки, которые вы ищете, называются нарушениями . Построение равномерно распределенных беспорядков не является тривиальной проблемой, но некоторые результаты известны в литературе. Наиболее очевидным способом построения беспорядков является метод отклонения: вы генерируете равномерно распределенные случайные распределения с использованием алгоритма, такого как Fisher-Yates, а затем отклоняете перестановки с фиксированными точками. Среднее время выполнения этой процедуры: e * n + o (n), где e – константа Эйлера 2.71828 … Это, вероятно, будет работать в вашем случае.

    Другим важным подходом для создания нарушений является использование рекурсивного алгоритма. Однако, в отличие от Fisher-Yates, у нас есть две ветви алгоритма: последний элемент в списке может быть заменен другим элементом (т. Е. Частью двух циклов ) или может быть частью более крупного цикла. Поэтому на каждом шаге рекурсивный алгоритм должен ветвиться, чтобы генерировать все возможные нарушения. Кроме того, решение о том, следует ли брать одну ветвь или другую, должно быть сделано с правильными вероятностями.

    Пусть D (n) – число нарушений n элементов. На каждом этапе количество ветвей, занимающих последний элемент до двух циклов, равно (n-1) D (n-2), а число ветвей, занимающих последний элемент до более крупных циклов, равно (n-1) D (n -1). Это дает нам рекурсивный способ вычисления числа нарушений, а именно D (n) = (n-1) (D (n-2) + D (n-1)) и дает вероятность ветвления на два -цикл на любой стадии, а именно (n-1) D (n-2) / D (n-1).

    Теперь мы можем построить беспорядки, решив, к какому типу цикла принадлежит последний элемент, заменяя последний элемент на одну из n-1 других позиций и повторяя. Однако может быть сложно отслеживать все ветвления, поэтому в 2008 году некоторые исследователи разработали оптимизированный алгоритм с использованием этих идей. Вы можете посмотреть пошаговое руководство по адресу http://www.cs.upc.edu/~conrado/research/talks/analco08.pdf . Время работы алгоритма пропорционально 2n + O (log ^ 2 n), что на 36% превышает скорость по методу отклонения.

    Я реализовал их алгоритм в Java. Использование longs работает для n до 22 или около того. Использование BigIntegers расширяет алгоритм до n = 170 или около того. Использование BigIntegers и BigDecimals расширяет алгоритм до n = 40000 или около того (ограничение зависит от использования памяти в остальной части программы).

     package io.github.edoolittle.combinatorics; import java.math.BigInteger; import java.math.BigDecimal; import java.math.MathContext; import java.util.Random; import java.util.HashMap; import java.util.TreeMap; public final class Derangements { // cache calculated values to speed up recursive algorithm private static HashMap numberOfDerangementsMap = new HashMap(); private static int greatestNCached = -1; // load numberOfDerangementsMap with initial values D(0)=1 and D(1)=0 static { numberOfDerangementsMap.put(0,BigInteger.valueOf(1)); numberOfDerangementsMap.put(1,BigInteger.valueOf(0)); greatestNCached = 1; } private static Random rand = new Random(); // private default constructor so class isn't accidentally instantiated private Derangements() { } public static BigInteger numberOfDerangements(int n) throws IllegalArgumentException { if (numberOfDerangementsMap.containsKey(n)) { return numberOfDerangementsMap.get(n); } else if (n>=2) { // pre-load the cache to avoid stack overflow (occurs near n=5000) for (int i=greatestNCached+1; i= 0 but was " + n); } } public static int[] randomDerangement(int n) throws IllegalArgumentException { if (n<2) throw new IllegalArgumentException("argument must be >= 2 but was " + n); int[] result = new int[n]; boolean[] mark = new boolean[n]; for (int i=0; i=0; i--) { if (unmarked<2) break; // can't move anything else if (mark[i]) continue; // can't move item at i if marked // use the rejection method to generate random unmarked index j < i; // this could be replaced by more straightforward technique int j; while (mark[j=rand.nextInt(i)]); // swap two elements of the array int temp = result[i]; result[i] = result[j]; result[j] = temp; // mark position j as end of cycle with probability (u-1)D(u-2)/D(u) double probability = (new BigDecimal(numberOfDerangements(unmarked-2))). multiply(new BigDecimal(unmarked-1)). divide(new BigDecimal(numberOfDerangements(unmarked)), MathContext.DECIMAL64).doubleValue(); if (rand.nextDouble() < probability) { mark[j] = true; unmarked--; } // position i now becomes out of play so we could mark it //mark[i] = true; // but we don't need to because loop won't touch it from now on // however we do have to decrement unmarked unmarked--; } return result; } // unit tests public static void main(String[] args) { // test derangement numbers D(i) for (int i=0; i<100; i++) { System.out.println("D(" + i + ") = " + numberOfDerangements(i)); } System.out.println(); // test quantity (u-1)D_(u-2)/D_u for overflow, inaccuracy for (int u=2; u<100; u++) { double d = numberOfDerangements(u-2).doubleValue() * (u-1) / numberOfDerangements(u).doubleValue(); System.out.println((u-1) + " * D(" + (u-2) + ") / D(" + u + ") = " + d); } System.out.println(); // test derangements for correctness, uniform distribution int size = 5; long reps = 10000000; TreeMap countMap = new TreeMap(); System.out.println("Derangement\tCount"); System.out.println("-----------\t-----"); for (long rep = 0; rep < reps; rep++) { int[] d = randomDerangement(size); String s = ""; String sep = ""; if (size > 10) sep = " "; for (int i=0; i
    

    В C ++:

     template  void shuffle(std::vector&arr) { int size = arr.size(); for (auto i = 1; i < size; i++) { int n = rand() % (size - i) + i; std::swap(arr[i-1], arr[n]); } } 
    Interesting Posts

    Visual Studio 2010: возможно ли заставить редактор использовать ANSI, а не UTF-8?

    Как прослушать изменения в коллекции MongoDB?

    Как добавить элемент в контекстное меню папки?

    Могут ли использоваться шаблоны lambda?

    Также Accent Mark находится на клавиатуре

    printf добавляет дополнительный `FFFFFF` к шестнадцатеричной печати из массива char

    Linux: Запомнить путь к USB-устройству

    Простой инструмент для захвата изображений для Mac OS X, который использует FireWire

    В чем разница между методами next () и nextLine () из classа Scanner?

    (413) Запросить сущность слишком большой | UploadReadAheadSize

    Панель действий Android SearchView как автозаполнение?

    Журнал всех приложений, которые запускаются или запускаются вручную на ПК с временем начала и окончания

    AutoHotKey – как снова сфокусироваться на окне после выполнения некоторых действий

    Используя команду history с помощью ssh и получать выходные данные с отметками времени

    Как отобразить содержимое строки html в элементе управления webbrowser?

    Давайте будем гением компьютера.