Задача с интервью.

Есть MP3 плэйер в который закачано 1000 композиций, которые составляют плэй-лист.
Написать функцию которая эффективно перемешает эти композиции и передаст плэй лист (List<Song>) функции play().

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

Any other ideas?

Здравствуйте, Аноним, Вы писали:

А>Задача с интервью.

А>Есть MP3 плэйер в который закачано 1000 композиций, которые составляют плэй-лист.
А>Написать функцию которая эффективно перемешает эти композиции и передаст плэй лист (List<Song>) функции play().

public static void shuffleSongsAndPlayThem(List<Song> songs) {
  Collections.shuffle(songs);
  play(songs);
}

А вообще можно посмотреть, как это делается в функции Collections.shuffle()

P.S. Permutations — перестановки, и их effective генерация — другая задача.

VZ>P.S. Permutations — перестановки, и их effective генерация — другая задача.

спасибо, но здесь как раз интересна реализация алгоритма а также эффективное использование структур для его реализации.

похоже в джаве так

/**
     * Randomly permute the specified list using the specified source of
     * randomness.  All permutations occur with equal likelihood
     * assuming that the source of randomness is fair.<p>
     *
     * This implementation traverses the list backwards, from the last element
     * up to the second, repeatedly swapping a randomly selected element into
     * the "current position".  Elements are randomly selected from the
     * portion of the list that runs from the first element to the current
     * position, inclusive.<p>
     *
     * This method runs in linear time.  If the specified list does not
     * implement the {@link RandomAccess} interface and is large, this
     * implementation dumps the specified list into an array before shuffling
     * it, and dumps the shuffled array back into the list.  This avoids the
     * quadratic behavior that would result from shuffling a "sequential
     * access" list in place.
     *
     * @param  list the list to be shuffled.
     * @param  rnd the source of randomness to use to shuffle the list.
     * @throws UnsupportedOperationException if the specified list or its
     *         list-iterator does not support the <tt>set</tt> operation.
     */
    public static void shuffle(List<?> list, Random rnd) {
        int size = list.size();
        if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
            for (int i=size; i>1; i--)
                swap(list, i-1, rnd.nextInt(i));
        } else {
            Object arr[] = list.toArray();

            // Shuffle array
            for (int i=size; i>1; i--)
                swap(arr, i-1, rnd.nextInt(i));

            // Dump array back into list
            ListIterator it = list.listIterator();
            for (int i=0; i<arr.length; i++) {
                it.next();
                it.set(arr[i]);
            }
        }
    }

Здравствуйте, Аноним, Вы писали:

А>Времени у меня было мало, поэтому начал изобретать из того что приходило на ум.
А>Сказал, мол, давайте сгенирируем рандомное число для каждой композиции и потом отсортируем эти числа (которые ссылаются на композиции) и передадим плэйеру.

У тебя два списка, один старый с композициями, другой новый, перемешанный.
Выбираешь случайным образом композицию из старого списка, удаляешь её из списка и кладёшь в новый список. Повторяешь предыдущий шаг, пока старый список не опустеет.

Здравствуйте, Аноним, Вы писали:

А>Any other ideas?

Fisher–Yates shuffle

А>Any other ideas?

Старик Кнут, упоминая задачу перетасовывания колоды карт, предлагает простое решение:
пройти по массиву и поменять текущий элемент со случайным.

В книге можно ознакомиться с доказательством правомочости такого подхода.

А>Сказал, мол, давайте сгенирируем рандомное число для каждой композиции и потом отсортируем эти числа (которые ссылаются на композиции) и передадим плэйеру.

ну, другие способы уже высказали.

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

А>Сказал, мол, давайте сгенирируем рандомное число для каждой композиции и потом отсортируем эти числа (которые ссылаются на композиции) и передадим плэйеру.

кстати, это решение немного некорректное. Результирующая перестановка будет ЧУТЬ-ЧУТЬ отличаться от случайной.
Почему?
Потому что наши рандомные числа имеют КОНЕЧНОЕ число бит.
А значит всегда есть ненулевая вероятность того что некоторые рандомные числа совпадут.
А в этом случае, если используется стабильная сортировка, то порядок этих чисел будет такой же как в исходной последовательности.

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

Здравствуйте, K13, Вы писали:

А>>Any other ideas?

K13>Старик Кнут, упоминая задачу перетасовывания колоды карт, предлагает простое решение:
K13>пройти по массиву и поменять текущий элемент со случайным.

K13>В книге можно ознакомиться с доказательством правомочости такого подхода.

Кстати, в std::random_shuffle из gnu libstdc++ почти так и делается.
Только для вектора размерности N каждый i-элемент (0 < i < N) заменяется с одним из предыдущих k-элементов (0 <= k <= i)

M>Кстати, в std::random_shuffle из gnu libstdc++ почти так и делается.
M>Только для вектора размерности N каждый i-элемент (0 < i < N) заменяется с одним из предыдущих k-элементов (0 <= k <= i)

ты уверен?
Если i проходит в направлении возрастания от 0 до N, то получится нехороший шаффл. Не все перестановки равновероятны.

Здравствуйте, dilmah, Вы писали:


M>>Кстати, в std::random_shuffle из gnu libstdc++ почти так и делается.
M>>Только для вектора размерности N каждый i-элемент (0 < i < N) заменяется с одним из предыдущих k-элементов (0 <= k <= i)

D>ты уверен?
D>Если i проходит в направлении возрастания от 0 до N, то получится нехороший шаффл. Не все перестановки равновероятны.

Вот выдержка из <bits/stl_algo.h>:

  template<typename _RandomAccessIterator>
    inline void
    random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
    {
      // concept requirements
      //...

      if (__first != __last)
        for (_RandomAccessIterator __i = __first + 1; __i != __last; ++__i)
          std::iter_swap(__i, __first + (std::rand() % ((__i - __first) + 1)));
    }

Здравствуйте, dilmah, Вы писали:


M>>Кстати, в std::random_shuffle из gnu libstdc++ почти так и делается.
M>>Только для вектора размерности N каждый i-элемент (0 < i < N) заменяется с одним из предыдущих k-элементов (0 <= k <= i)

D>ты уверен?
D>Если i проходит в направлении возрастания от 0 до N, то получится нехороший шаффл. Не все перестановки равновероятны.

И да, обоснуй, почему перестановки не будут равновероятными.

M>И да, обоснуй, почему перестановки не будут равновероятными.

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

Так что конкретно тот код генерирует равновероятные перестановки, но только, считая что количество элементов в последовательности пренебрежимо меньше RAND_MAX -- иначе будет проявляться что rand()%N дает неравномерное распределение.

Здравствуйте, dilmah, Вы писали:
D>Так что конкретно тот код генерирует равновероятные перестановки, но только, считая что количество элементов в последовательности пренебрежимо меньше RAND_MAX -- иначе будет проявляться что rand()%N дает неравномерное распределение.

Для получения равномерного целочисленного распределения 0..(N-1) нужно использовать правильный способ.

Из документации по Java™ Platform, Standard Edition:

public int nextInt(int n)
Returns a pseudorandom, uniformly distributed int value between 0 (inclusive) and the specified value (exclusive), drawn from this random number generator's sequence. The general contract of nextInt is that one int value in the specified range is pseudorandomly generated and returned. All n possible int values are produced with (approximately) equal probability. The method nextInt(int n) is implemented by class Random as if by:

 public int nextInt(int n) {
   if (n <= 0)
     throw new IllegalArgumentException("n must be positive");

   if ((n & -n) == n)  // i.e., n is a power of 2
     return (int)((n * (long)next(31)) >> 31);

   int bits, val;
   do {
       bits = next(31);
       val = bits % n;
   } while (bits - val + (n-1) < 0);
   return val;
 }

The hedge "approximately" is used in the foregoing description only because the next method is only approximately an unbiased source of independently chosen bits. If it were a perfect source of randomly chosen bits, then the algorithm shown would choose int values from the stated range with perfect uniformity.
The algorithm is slightly tricky. It rejects values that would result in an uneven distribution (due to the fact that 2^31 is not divisible by n). The probability of a value being rejected depends on n. The worst case is n=2^30+1, for which the probability of a reject is 1/2, and the expected number of iterations before the loop terminates is 2.
The algorithm treats the case where n is a power of two specially: it returns the correct number of high-order bits from the underlying pseudo-random number generator. In the absence of special treatment, the correct number of low-order bits would be returned. Linear congruential pseudo-random number generators such as the one implemented by this class are known to have short periods in the sequence of values of their low-order bits. Thus, this special case greatly increases the length of the sequence of values returned by successive calls to this method if n is a small power of two.

boost::uniform_int использует аналогичный алгоритм.

Здравствуйте, dilmah, Вы писали:


M>>И да, обоснуй, почему перестановки не будут равновероятными.

D>конкретно тот код, который ты привел хороший -- потому что свопы делаются не только с предшествующими элементами, но и с самим собой

D>Так что конкретно тот код генерирует равновероятные перестановки, но только, считая что количество элементов в последовательности пренебрежимо меньше RAND_MAX -- иначе будет проявляться что rand()%N дает неравномерное распределение.

У std::random_shuffle есть перегрузка, позволяющая использовать свою функцию random и в ней нет позорного %N, но в доке к функции есть требование: Calling rand(N) for a positive integer N should return a randomly chosen integer from the range [0,N)