алгоритмы перемешивания какого-либо набора (например колода карт)

[Mur4ik]

Собственно интересны разные варианты и их оптимальность.

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

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

Но скорее всего уже есть более оптимальные алгоритмы, может кто сталкивался?
Поделитесь линками или общим принципом, плиз.

[VVall]

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

[Яски]

{
var array:Array = ["девятка", "десятка", "валет", "дама", "король", "туз"];
array.sort(random)
}
function random (a:*, b:*):int {
   return (Math.random() - 0.5)*100;
}

Или еще лучше

{
var array:Array = ["девятка", "десятка", "валет", "дама", "король", "туз"];
var shuffed:Array = new Array();
var val:*;
while ((val = array.slice(int(Math.random()*(array.length - 1))), 1) != null) {
   shuffed.push(val);
}
}

[Mur4ik]

Всем спасибо

private function randomizeArray(array:Array):Array
{
	var randomizedArray:Array = new Array();
 
	while (array.length)
	{
		randomizedArray.push(array.splice(Math.floor(Math.random() * array.length), 1)[0]);
	}
 
	return randomizedArray;
}

[Smrad]

О(n^2)

[Mur4ik]

Сообщение от Smrad

О(n^2)

Это как понимать?

[dimarik]

типа "O-сложность алгоритмов"

[Яски]

Сообщение от Smrad

О(n^2)

неа O(n)

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

{
   var array:Array = [new Card("десять"), new Card("валет", 0.2), new Card("туз", 0.5)];
   for each (var card:Card in array) {
      // Может быть любая другая функция, 
      // все зависит от того, как сильно приоритет влияет на выбор.
      card.sortPriority = Math.random() + card.priority;
   }
   array.sortOn("sortPriority", Array.DESCENDING | Array.NUMERIC);
}
 
class Card {
   public var name:String;
   public var priority:Number;
   public var sortPriority:Number;
   public function Card(name:String, priority:Number = 0) {
      this.name = name;
      this.priority = priority;
   }
}

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

[Smrad]

Сообщение от Яски

неа O(n)

Только сам splice уже имеет O(n), потому все варианты со splice'ом квадратичные. Варианты с сортировкой должны быть побыстрее, но сама сортировка это O(n*log(n)). Что-то мне подсказывает что нормальный алгоритм должен иметь линейную сложность.

Добавлено через 15 минут
Сам алгоритм, в принципе, очевиден. Просто нужен random, выдающий _неповторяющиеся_ числа от 0, до arr.length.