Алгоритъм за разбъркване на масива

За пореден път срещнах проста, но интересна задача - да смесвам наличните стойности в даден масив.

Понякога тази задача се формулира и като запълване на масив с неповтарящи се стойности в произволен ред. Но не е разумно да се напише алгоритъм, който ще генерира произволно число и след това да се провери дали тази стойност ще се повтори с вече попълнени елементи. Би било много по-правилно просто да смесите дадения масив. Нещо повече, това ще позволи да не се усложнява процесът на избор на приемливи стойности, като се наблюдава уникалността на всяка стойност или като се вземе предвид появата на всяка стойност определен брой пъти.

В резултат на това задачата се свежда само до смесване на съществуващата последователност, независимо от първоначалния й състав и подреждане.

Най-простото решение би било да се извършат N операции за замяна на два елемента в цикъл, чиито индекси се избират на случаен принцип. Стойността на N определя качеството на такова смесване - колкото повече замествания, толкова по-добър е резултатът. Недостатъкът на този метод е, че някои елементи от масива (особено ако е голям) могат да останат на първоначалните си места. Същият недостатък ще бъде възможността за многократно преместване на един и същ елемент от масив. В резултат на това нерационално увеличаване на броя на замените все още не води до 100% висококачествено разместване на всички елементи.

Следният алгоритъм е по-добър както по отношение на преместването на всички елементи, така и по броя на операциите за смесване:

- изберете произволен елемент от масива;

- разменете го с последния елемент;

- отново изберете произволен елемент от масив, без да се засяга последния;

- промяна с предпоследния;

Фигура: Алгоритъм за разбъркване на масива

По този начин избираме случаен елемент от стесняващия се списък и го поставяме последен в този списък. За да преместите всички елементи, ще е необходим един ход по-малък от броя на елементите в масива.

конст
N = 9; // размер на масива
вар
mas: масив [1.N] на цяло число;
i, r, h: Цяло число;
започнете
Случайно;
за i: = N в центъра 2 започва
r: = Случайно (i) + 1; // изберете произволен елемент

ако r <> i, тогава започнете
// заместване на елементи
h: = mas [i];
mas [i]: = mas [r];
mas [r]: = h;
край;
край;
край;

В това решение има вероятност този, който се заменя, да отпадне като случаен елемент. За да се избегне безсмисленото движение на един елемент, има отметка, която ще изключи ненужната подмяна. В този случай обаче има възможност някои елементи от масива да останат на мястото си.

За да премахнете този недостатък, можете да вземете произволна стойност, без да засягате крайно заменения елемент. Тъй като е известно предварително, че елементът, който трябва да бъде заменен, не може да бъде избран, тук не е необходимо допълнително условие.

конст
N = 9; // размер на масива
вар
mas: масив [1.N] на цяло число;
i, r, h: Цяло число;
започнете
Случайно;
за i: = N в центъра 2 започва
r: = Случайно (i-1) + 1; // изберете произволен елемент

// заместване на елементи
h: = mas [i];
mas [i]: = mas [r];
mas [r]: = h;
край;
край;

Използването на такъв алгоритъм гарантира, че нито един елемент не остава на същото място.