перемешать двумерный массив

[Alexandr Izvekov]

Как можно перемешать двумерный массив? может кто сталкивался..

--
Alexandr Izvekov
Head of company
Piezo:lab
mobile: +38 050 187 0803
e-mail: spay...@piezodesign.com

[Павел Молянов]

// как вариант, через свою функцию sort, прописать какое-ть рандомайзное сравнение элементов
var array_tmp = [[0,1], [2,3], [3,4]]
function mix(a, b):Number
{
return Math.random()
}
array_tmp.sort(mix)

[Alexandr Izvekov]

sort поменяет местами только первый массив. а мне надо получить что
то похожее на [[0,1], [2,3], [3,4]] => [[4,2], [5,3], [1,0]]

> --~--~---------~--~----~------------~-------~--~----~

[Alexandr Izvekov]

>> // как вариант, через свою функцию sort, прописать какое-ть рандомайзное сравнение элементов
>> var array_tmp = [[0,1], [2,3], [3,4]]
>> function mix(a, b):Number
>> {
>> return Math.random()
>> }
>> array_tmp.sort(mix)

>> --~--~---------~--~----~------------~-------~--~----~

> sort поменяет местами только первый массив. а мне надо получить что
> то похожее на [[0,1], [2,3], [3,4]] => [[4,2], [5,3], [1,0]]

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

[Dima Skripnik]

Как по мне - то тебе не нужен ни 2 мерный массив ни перемешивание.
(по ходу и 2й массив как таковой может и не нужен на самом деле)

2-мерный массив: достаем (даже больше - вынимаем) из массива четный элемент и нечетный.
Перемешивание: вынимаем (как из колоды карт :))) случайный элемент.

Т.е. получится что-то в этом роде:
var a = [];
a[0] = [1,2];
a[1] = [3,4];
a[2] = [5,6];

function getItem(a) {
return a[getRand(0, a.length-1)][getRand(0, 1)];
}
function getRand(min, max) {
return Math.floor(Math.random() * (max - min + 1)) + min;
}

trace(getItem(a));
trace(getItem(a));
trace(getItem(a));
trace(getItem(a));

[Ivan Dembicki]

Hello Alexandr,

- тут требуется уточнение:
вложенные массивы должны остаться той же длины?

AI> Можно конечно склеить в одномерный перемешать и разбить обратно, но
AI> что то меня такой способ смущает.. может кто знает решение красивее?

--
Ivan Dembicki
____________________________________________________________________________
i...@design.ru | | http://www.design.ru

[iFrame]

> - тут требуется уточнение:
> вложенные массивы должны остаться той же длины?

var arr = [
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9],
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9],
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9],
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9],
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
];
Array.prototype.randomize = function(len:Number){
if(len<=0) len = 1;
var ret:Array = this.concat.apply([], this);
ret.sort(function(){return Math.round(Math.random()) ? true : false;});
this.length = 0;
while(ret.length){this.push(ret.splice(0, len));}
}
arr.randomize(10);
for(var i=0; i<arr.length; i++) trace(arr[i]);

--
/*
Oleg Galaburda
mailto:bur...@gmail.com
ICQ:289297363

ActionScript 3 - стихотворения, поэмы - эмоции в Брайле. (с) a_[w]
*/

[Alexandr Izvekov]

Ну так єто же и есть склеивание в одномарній массив. я об этом писал
выше. но уже мне кажется что это оптимальный вариант)

[Nox Noctis]

> Array.prototype.randomize = function(len:Number){
> if(len<=0) len = 1;
> var ret:Array = this.concat.apply([], this);
> ret.sort(function(){return Math.round(Math.random()) ? true : false;});
> this.length = 0;
> while(ret.length){this.push(ret.splice(0, len));}
> }
> arr.randomize(10);
> for(var i=0; i<arr.length; i++) trace(arr[i]);

Это перемешивание строк матрицы, а не перемешивание всех элементов.

Если по-честному перемешать матрицу (считая, что все строки одинаковой
длины), можно сделать так:

var shuffle2d:Function = function (list:Array)
{
var height:Number = list.length;
var width:Number = list[0].length;
var total:Number = height*width;
//
var index:Number;
var x1:Number, y1:Number, x2:Number, y2:Number;
var item:Object;
//
for (var i:Number = 0; i<total; i++) {
index = random(total);
y1 = int(index/width);
x1 = index%width;
y2 = int(i/width);
x2 = i%width;
//
item = list[y1][x1];
list[y1][x1] = list[y2][x2];
list[y2][x2] = item;
}
return list;
};
//
var list:Array = [[0, 1, 2, 3],
[4, 5, 6, 7],
[8, 9, 10, 11],
[12, 13, 14, 15],
[16, 17, 18, 19]];
trace(shuffle2d(list).join("\n"));
//

Можно, наверное, написать остроумнее и короче, но работать будет
медленнее. :)

--
Michael Antipin
______________________________________________________________________
n...@design.ru | http://www.artlebedev.ru | http://www.noregret.org

[Nox Noctis]

Хотя нет, насчет перемешивания строк я погорячился, извините. :)

> arr.randomize(10);
> for(var i=0; i<arr.length; i++) trace(arr[i]);

--

[Nox Noctis]

> ret.sort(function(){return Math.round(Math.random()) ? true : false;});

Очень медленно.

Примеры:

//
// неоригинальное перемешивание одномерного массива
//
var shuffle:Function = function (list:Array)
{
var item:Object;
var index:Number;
for (var i:Number = 0; i<list.length; i++) {
index = random(list.length);
item = list[index];
list[index] = list[i];
list[i] = item;
}
return list;
};
var list = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33,
34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49];
//
var s:Number = getTimer();
for (var i:Number = 0; i<100; i++) {
shuffle(list);
}
trace("time: "+(getTimer()-s)); // на моем компе выдает 12-18 мсек

//
// перемешивание повеселее
//
var shuffle:Function = function (list:Array)
{
var rnd:Function = function ()
{
return -1+random(3);
};
list.sort(rnd);
return list;
};
var list = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33,
34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49];
//
var s:Number = getTimer();
for (var i:Number = 0; i<100; i++) {
shuffle(list);
}
trace("time: "+(getTimer()-s)); // на моем компе выдает 660-690 мсек

то есть, вариант в sort() медленнее примерно в 40 раз даже на
коротеньком массиве (всего 50 элементов).

[andykud...@gmail.com]

Если перемешивать посредством перестановки по индексам с
использованием дополнительных массивов по row &
col будет быстрее

[iFrame]

Да, ваш вариант(вставил в свой прмер):

Array.prototype.randomize = function(len:Number){
if(len<=0) len = 1;
var ret:Array = this.concat.apply([], this);

var item:Object;
var index:Number;

for (var i:Number = 0; i<ret.length; i++) {
index = random(ret.length);
item = ret[index];
ret[index] = ret[i];
ret[i] = item;

}
this.length = 0;
while(ret.length){this.push(ret.splice(0, len));}
}

обрабатывает в ~13 раз быстрее -- 136 к 10. :)

> Очень медленно.

[Nox Noctis]

> Если перемешивать посредством перестановки по индексам с
> использованием дополнительных массивов по row &
> col будет быстрее

Может быть и так. Можно пример? :)

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

[Alexander Sergeyev]

Предложу свое решение.

1. переводишь массив в одномерный, запоминая, сколько было в каждом
"втором измерении" элементов.
2. Некоторое количество раз (потом скажу сколько) производишь обмен
двух случайных элементов местами. случайность выбирается равномерно,
метод random().
3. сливаешь по порядочку все это дело в двумерный массив.

Была такая классная статья, "How Many Times Should You Shuffle a Deck
of Cards", в которой математик исследовал вопрос - а каким способом и
сколько раз надо перемешивать карты, чтобы получить хорошо
разбросанное распределение? Такого способа перемешивания там не было,
там сложнее, но могу прислать если интересно статью.

Для такого способа, полагаю, достаточно сделать столько же обменов,
сколько всего элементов в массиве.