Shuffle array, чтобы никакие элементы не отображались в одинаковом положении в одинаковом массиве [duplicate]

Существует не тот, который действительно полезен. Я обсуждаю некоторые проблемы в моем ответе . Есть ли библиотека php для проверки адресов электронной почты? , она также обсуждается в Regexp-распознавании адреса электронной почты?

Короче говоря, не ожидайте, что одно полезное регулярное выражение будет работать правильно. И лучшее регулярное выражение будет проверять синтаксис, а не действительность электронной почты (jhohn@example.com верен, но он, вероятно, будет отказываться ...).

13
задан cychoi 30 May 2014 в 05:25
поделиться

3 ответа

Как отметил @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<Integer,BigInteger> numberOfDerangementsMap 
        = new HashMap<Integer,BigInteger>();
      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<n; i++) numberOfDerangements(i);
          greatestNCached = n-1;
          // recursion for derangements: D(n) = (n-1)*(D(n-1) + D(n-2))
          BigInteger Dn_1 = numberOfDerangements(n-1);
          BigInteger Dn_2 = numberOfDerangements(n-2);
          BigInteger Dn = (Dn_1.add(Dn_2)).multiply(BigInteger.valueOf(n-1));
          numberOfDerangementsMap.put(n,Dn);
          greatestNCached = n;
          return Dn;
        } else {
          throw new IllegalArgumentException("argument must be >= 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<n; i++) {
          result[i] = i;
          mark[i] = false;
        }
        int unmarked = n;

        for (int i=n-1; 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<String,Integer> countMap = new TreeMap<String,Integer>();
        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<d.length; i++) {
        s += d[i] + sep;
          }

          if (countMap.containsKey(s)) {
        countMap.put(s,countMap.get(s)+1);
          } else {
        countMap.put(s,1);
          }
        }

        for (String key : countMap.keySet()) {
          System.out.println(key + "\t\t" + countMap.get(key));
        }

        System.out.println();

        // large random derangement
        int size1 = 1000;
        System.out.println("Random derangement of " + size1 + " elements:");
        int[] d1 = randomDerangement(size1);
        for (int i=0; i<d1.length; i++) {
          System.out.print(d1[i] + " ");
        }

        System.out.println();
        System.out.println();

        System.out.println("We start to run into memory issues around u=40000:");
        {
          // increase this number from 40000 to around 50000 to trigger
          // out of memory-type exceptions
          int u = 40003;
          BigDecimal d = (new BigDecimal(numberOfDerangements(u-2))).
        multiply(new BigDecimal(u-1)).
        divide(new BigDecimal(numberOfDerangements(u)),MathContext.DECIMAL64);
          System.out.println((u-1) + " * D(" + (u-2) + ") / D(" + u + ") = " + d);
        }

      }

    }

4
ответ дан Edward Doolittle 25 August 2018 в 16:35
поделиться

Вы ищете derangement ваших записей.

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

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

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

Асимптотически вероятность получения нарушения близка к 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, но только если он не создает фиксированную точку. Это немного длиннее для выполнения (из-за части отказа) и требует, чтобы вы могли проверить, находится ли запись в ее первоначальном месте или нет, но она имеет то преимущество, что она может производить все возможные нарушения (равномерно для этого материя).

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

Изменить:

Мой алгоритм на самом деле плохо: у вас все еще есть шанс закончить с последней точкой неперепутанной, а распределение не является случайным вообще, см. предельные распределения моделирования: marginal distributions [/g4]

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

Second Edit:

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

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

9
ответ дан FelixCQ 25 August 2018 в 16:35
поделиться

В C ++:

template <class T> void shuffle(std::vector<T>&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]);
    }
}
0
ответ дан uncletall 25 August 2018 в 16:35
поделиться
Другие вопросы по тегам:

Похожие вопросы: