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

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

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

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

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

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