Форум Flasher.ru - Как "перемешать" элементы в массиве?

Форум Flasher.ru (http://www.flasher.ru/forum/index.php)

- ActionScript 3.0 (http://www.flasher.ru/forum/forumdisplay.php?f=83)

- - Как "перемешать" элементы в массиве? (http://www.flasher.ru/forum/showthread.php?t=187036)

mihael_p

12.11.2012 12:26

Как "перемешать" элементы в массиве?

Есть определенный массив:

Код AS3:

private var someDigits:Array = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15];

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

КорДум

12.11.2012 12:28

Как-то ваял.

Код AS3:

package ru.kordum.utils {

 

        /**

         * @author KorDum

         */

 

        public class ArrayShuffler {

                private static var _array:Array;

 

                //---------------------------------------------------------------------------

                //

                // CONSTRUCTOR

                //

                //---------------------------------------------------------------------------

 

                public function ArrayShuffler() {

 

                }

 

 

                //---------------------------------------------------------------------------

                //

                // PRIVATE STATIC METHODS

                //

                //---------------------------------------------------------------------------

 

                private static function startRandomize():void {

                        var length:uint = _array.length;

 

                        while (length--) {

                                var n:int = Math.random() * (length + 1);

                                swap(length, n);

                        }

                }

 

 

                private static function swap(x:uint, y:uint):void{

                        var temp:* = _array[x];

                        _array[x] = _array[y];

                        _array[y] = temp;

                }

 

 

                //---------------------------------------------------------------------------

                //

                // PUBLIC STATIC METHODS

                //

                //---------------------------------------------------------------------------

 

                public static function randomize(array:Array, count:uint = 1):Array {

                        if (!array) return null;

 

                        _array = array.slice();

 

                        for (var i:uint = 0; i < count; i++) {

                                startRandomize();

                        }

 

                        return _array;

                }

        }

}

udaaff

12.11.2012 13:01

Код AS3:

public static function shuffle(array:Array):void

{

        var t:*;

        var r:int;

        var i:int = array.length;

        while (i) 

        {

                r = Math.floor(Math.random() * i--);

                t = array[i];

                array[i] = array[r];

                array[r] = t;

        }

}

КорДум

12.11.2012 13:31

У меня то же самое, но с приведением рандома с нормальных законом распределения к более-менее равномерному (у Чуви взял). Последствия очевидны.

mihael_p

12.11.2012 13:49

КорДум спасибо огромное, то что нужно:)

udaaff

12.11.2012 13:51

Цитата:

но с приведением рандома с нормальных законом распределения к более-менее равномерному

В моём примере какое-то другое распределение?

КорДум

12.11.2012 13:56

По идее, нормальное ) Math.random() в as3 живет по этому закону. Чуви проводил эксперименты, рисовал графики. Потом дошел до метода какого-то там, наваял код, приводящий нормальное к равномерному, а я нагло стырил.

Добавлено через 8 минут
А хотя по коду то же самое вообще у нас. Разве что у меня несколько раз можно "шуффлировать".

strangedk

12.11.2012 16:25

Код AS3:

var _source:Array = [1,2,3,4,5,6,7,8,9,0];

var _result:Array = [];

 

while (_source.length > 0) {

    _result.push(_source.splice(Math.round(Math.random() * (_source.length - 1)), 1)[0]);

}

Astraport

12.11.2012 16:52

Пользуясь случаем.
Вот например я таким способом перемешиваю итемы которые должны появиться в игре. Итемов поровну - хороших (здоровье, броня) и плохих (мины, враги). И герой может выпить эликсир и его удача вырастает на 10%, на 20% или даже на 50%. Соответственно, нужно чтобы в этом массиве вероятность появления положительных итемов также вырастала (в зависимости от выпитого эликсира удачи).

Вот как такое лучше сделать?

alexcon314

12.11.2012 17:20

Astraport, не ясно, как это может соотноситься с перемешиванием.
"вероятность появления" тех или иных элементов в массиве и перемешивание (т.е. изменение порядка следования) элементов никак не соотносятся.
скорее тут надо рассмотреть формирование самого массива изначально.

Astraport

12.11.2012 17:32

Цитата:

Astraport, не ясно, как это может соотноситься с перемешиванием.

Дело в том, что у меня, допустим, всего 50 итемов, но на каждом уровне должно появиться только 20 случайных (разное количество, зависит от уровня). Я тоже также примерно как советуют выше их перемешиваю и вывожу 20 первых в массиве. Ну вот и нужно увеличить вероятность появления в этой двадцатке "хороших" итемов после порции эликсира.

КорДум

12.11.2012 17:40

Решение в лоб: какова вероятность появления, столько копий (ссылок) значений/объектов в массиве. Если вероятности кругловыглядящие - 10%, 20% и так далее, то можно не 20 элементов втыкать в массив, а взять кратное 10, то есть 2. Затем перемешать это все и взять рандомный элемент.

amesqit

12.11.2012 18:12

а может 50 итемов отсортировать по степени "хорошести", выбирать необходимые N итемов с помощью нормального (Гаусовского) распределения случайных величин, со сдвигом мат ожидания, чем больше хороших вкусняшек съел игрок, тем мат ожидание ближе к хорошим индексам и наоборот, нужно только коэффициент рассеивания подобрать

Astraport

12.11.2012 19:54

КорДум, ну вот пока я думаю решать таким же способом: рандомно ищу в массиве хорошие итемы (если 10% эликсир - то 3 штуки, если 20% - то 6 штук и т. д.), добавляю их в исходный массив и потом уже перемешиваю и выбираю 20.

amesqit, это круто, но сложно:)

amesqit

12.11.2012 19:59

зато весело :) где-то видел реализацию нормального распределения на as3, а остальное реализовать вообще дело не хитрое :)

i.o.	12.11.2012 20:41

Код AS3:

var arr:Array = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ];

arr.sort(function(...args):int{ return (0x1 - (int(Math.random() < 0.5) << 0x1)); });

 

trace(arr);

Код:

3,0,6,8,1,5,4,7,9,2

Ну, полагаю труЪ

elder_Nosferatu

12.11.2012 20:49

2Astraport

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

- просуммировать все числа (шансы на выпадание);
- выбросить рандомное число от нуля, до посчитаной суммы;
- пробегаясь от начала массива, суммировать все числа и сравнивать с полученым рандомны. Как толко текущая сумма будет равна выброшеному числу возвратить текущий индекс, если больше - предидущий индекс.

По этому индексу я и получаю свой долгожданный элемент из набора.

По идее, этот вариант имитирует запихание в один массив нескольких одинаковых эелементов. Но заменяет этот процесс указанием количества этих элементов.

Пример:

Код AS3:

var items:Array = [item0, item1, item2, item3, item4];

var chances:Array = [10, 10, 10, 3, 1];

 

function getRandItem(items:Array, chances:Array):* {

        var sum:int = 0;

        var i:uint = 0;

        var len:uint = chances.length;

        var rnd:uint = 0;

 

        while (i < len) {

                sum += chances[i++];

        }

 

        rnd = uint(Math.random() * sum);

        sum = 0;

        i = 0;

        while (sum < rnd && i < len) {

                sum += chances[i++];

        }

 

        i = (sum == rnd) ? (i - 1) : (i - 2);

        return items[i];

}

 

trace("random item:", getRamdItem(items, chances));

expl	12.11.2012 21:21

Цитата:

Сообщение от strangedk (Сообщение 1104038)

Код AS3:

var _source:Array = [1,2,3,4,5,6,7,8,9,0];

var _result:Array = [];

 

while (_source.length > 0) {

    _result.push(_source.splice(Math.round(Math.random() * (_source.length - 1)), 1)[0]);

}

Не знаю, более ли этот вариант правильное распределение даёт, чем предыдущие, но сплайсить массив n раз дорого - сложность почти n * n + затраты на выделение памяти и сборку мусора.
Math.round(Math.random() * (_source.length - 1)) вроде бы эквивалентно int(Math.random() * _source.length), не?
Как написать то же самое (1 в 1), но без сплайса и без создания другого массива (линейная сложность :) ):

Код AS3:

public static function shuffle(array:Array):void {

        var length:int = array.length;

        while (length > 0) {

                var index:int = int(Math.random() * length);

                var value:int = array[index];

 

                // Элемент выбран, появилась дырка - заделываем элементом с условного конца

                // и у нас снова ровный массив из оставшихся элементов

                array[index] = array[length - 1];

 

                // Кидаем выбранный элемент в текущий условный конец массива - там выборки уже не будет

                // Т.е. слева у нас старый массив - справа строим новый

                array[length - 1] = value;

 

                // Левый (исходный) массив поубавился

                length--;

        }

}

Котяра

12.11.2012 22:07

http://soft.compulenta.ru/510956

Алгоритм Фишера-Йейтса

реализации (говорим спасибо ChuwY)
https://bitbucket.org/pavel_rybkin/y...zer?at=default

i.o.	12.11.2012 22:09

Ну и еще вариант

Код AS3:

var arr:Array = [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ];

 

function shuffle( a:Array ) : void

{

        var rnd:Array = [];

        var l:int = a.length;

        var i:int = -1;

        while (++i < l)

                rnd[i] = Math.random();

 

        var indicies:Array = rnd.sort(Array.NUMERIC | Array.RETURNINDEXEDARRAY);

 

        i = -1;

        while (++i < l)

        {

                var k:int = indicies[i];

                rnd[i] = a[k];

        }

 

        a.length = 0;

        a.push.apply(null, rnd);

}

alexcon314

12.11.2012 22:18

Вариант.
1. На каждую выпитую рюмку элексира увеличиваем количество "положительных" элементов в исходном массиве. Т.е увеличиваем "плотность" удачи. Соизмеримо, само-собой, исходя из разумных допущений и логики игры.
2. Перемешиваем массив одним из предложенных способов, например, как в посте udaaff'a.
3. Т.к. имеем дисбаланс плюсов и минусов в исходном массиве, на отдельном его участке [0,20] при равномерном распределении этот дисбалланс статистически должен присутствовать так же.

Nikem79

25.11.2012 13:03

Цитата:

Сообщение от strangedk (Сообщение 1104038)

Код AS3:

var _source:Array = [1,2,3,4,5,6,7,8,9,0];

var _result:Array = [];

 

while (_source.length > 0) {

    _result.push(_source.splice(Math.round(Math.random() * (_source.length - 1)), 1)[0]);

}

У меня код работает в таком виде:

Код AS3:

var _source:Array = [1,2,3,4,5,6,7,8,9,0,11,12,13,14,15];

var _result:Array = [];

 

while (_source.length > 0) {

    _result.push(_source.splice(Math.round(Math.random() * (_source.length - 1)), 1)[0]);

        trace(_result[_source]);

}

 

trace("Дальше");

 

for(var six:int=0;six<15;six++){

        trace(_result[six]);

}

Подскажите пожалуйста, а как сделать количество перемешиваемых чисел переменной?
Чтобы в строчку его можно было поместить

N=50;
вместо var _source:Array = [1,2,3,4,5,6,7,8,9,0];
это: var _source:Array = [N];

и чтобы в итоге перемешивались не 10 данных, а сколько понадобится?..

spirit2

25.11.2012 15:49

Код AS3:

var n:int = 50;

var source:Array = [];

for(var i:int=0;i<_n;i++){

        source.push(i+1);

}

Часовой пояс GMT +4, время: 15:19.

Copyright © 1999-2008 Flasher.ru. All rights reserved.
Работает на vBulletin®. Copyright ©2000 - 2026, Jelsoft Enterprises Ltd. Перевод: zCarot
Администрация сайта не несёт ответственности за любую предоставленную посетителями информацию. Подробнее см. Правила.