[inhibitormonoaminooksydazy]

Mam tablicę [1,2,3,4] i chcę ją posortować przypadkowo, ale mam warunek, że żadna wartość nie może być na tej samej pozycji co wcześniej. Czyli w normalnym losowniu kolejności może wyjść taki wynik: [2,4,3,1] czyli liczba 3 jest w tym samym miejscu. Muszę tego uniknąć. Wie ktoś jak to zrobić szybko i skutecznie?

Bo ja zrobiłem funckję do tego, ale czasami się wywala - to zależy od losowania. Czasem wyjdzie tak, że ostatnia cyfra z tablicy zostanie na samym końcu i wtedy tablica copyArr zostaje pusta i przypisywana jest wartość 'undefined'. Łatwo moge to obejść, ale ta funkcja i tak jest dość skomplikowana i się zastanawiam czy ktoś ma jakąś lepszą i bardziej zgrabną wersję.

public function uniqSort(ar:Array):Array {
var input:Array = ar;
var output:Array = new Array;
var random:int;

for (var i:int = 0; i < input.length; i++) {

var copyArr:Array = ObjectUtil.copy(input) as Array; //robi kopię obiektu
copyArr.splice(i,1); //usuwa 1 wartość na pozycji i

for each (var j:int in output) {
var idx:int = copyArr.indexOf(j);
if (idx > -1) {
copyArr.splice(idx,1); //usuwa 1 wartość na pozycji idx
}
}
random = Math.random() * copyArr.length;

if (copyArr[random] == undefined) trace ('error') //tu się wywala raz na jakiś czas; zwraca undefined, bo tablica copyArr jest pusta

output.push(copyArr[random]);
}
return output;
}
#programowanie

[sokytsinolop]

@inhibitormonoaminooksydazy: jakie debilne zadanie, skoro są jakieś zasady dodatkowe to pozycja już nie może być losowa xD

[inhibitormonoaminooksydazy]

@sokytsinolop: ok, to w takim razie potrzebuję pozycji pseudolosowej :)

[kawazaki]

@sokytsinolop: @inhibitormonoaminooksydazy: pozycja jednej konkretnej cyfry raczej nie będzie randomem z pozostałych miejsc, bo w ogóle nie uwzględnia pozostałych cyfr i powstaje ten problem z ostatnią cyfrą,

Ale już permutacja wszystkich liczb może być losowo wybrana ze zbioru, który powstanie po uwzględnieniu ograniczeń. Jednak nie mam pomysłu, żeby to działało dla długiej listy innego niż wygenerowanie wszystkich dozwolonych permutacji i losowo wybranie jednej z nich.

[sokytsinolop]

@inhibitormonoaminooksydazy: ja bym to zrobił tak żebym posortował randomem normalnie, i później sprawdził czy są elementy które występują na tym samym miejscu, jeśli tak to zamień go z innym (ale takim żeby zamieniony również nie trafił na złe miejsce) ale to beznadziejne rozwiązanie bo niewiadoma złożoność

[inhibitormonoaminooksydazy]

(ale takim żeby zamieniony również nie trafił na złe miejsce)

@sokytsinolop: tylko po zwykłym randomie może wyjść kilka wartości na tych samych miejscach co wcześniej, w skrajnym przypadku mogą być wszystkie:) Wtedy na każdą cyfrę i tak muszę stworzyć osobny warunek czyli to co zrobiłem w mojej funkcji mniej więcej.

[inhibitormonoaminooksydazy]

@kawazaki: hmm, nie wiem za bardzo jak wdrożyć permutację, ale to będą krótkie listy, maksymalnie 10 pozycji.

[sokytsinolop]

@inhibitormonoaminooksydazy: jak 10 pozycji to możesz nawet zrobić math random while nie jest dobrze :D

[inhibitormonoaminooksydazy]

@sokytsinolop: właśnie chciałem uniknąć takiego sprawdzania metodą prób i błędów, ale chyba faktycznie tak będize prościej niż to co do tej pory mam.

[sokytsinolop]

@inhibitormonoaminooksydazy: prościej, ale to już jest totalnie nieoptymalne rozwiązanie i jeśli to jest na studia (na jakieś metody numeryczne) to dostaniesz po głowie ;)

[inhibitormonoaminooksydazy]

@sokytsinolop: nie na studia, do pracy, czyli mogę zastosować :P

[sokytsinolop]

@inhibitormonoaminooksydazy: tylko miej na uwadze, że nawet po milionie prób możesz dostać błędny wynik

[sokahr]

@inhibitormonoaminooksydazy: to nie pomoże? ( ͡° ͜ʖ ͡°)

[inhibitormonoaminooksydazy]

@sokytsinolop: właśnie dlatego chciałem uniknąć while.
Ostatecznie dodam warunek w mojej fukncji, że jak skopiowana tablica zostaje pusta to znaczy, że na bank została tylko ostatnia wartość i zamienię ją z inną pozycją w tablicy i tyle.

[inhibitormonoaminooksydazy]

@sokahr: dzięki, troche to skomplikowane, ale mam gdzie się zaczepić przynajmniej, nowe słówko na dziś 'derangement' :)

[Hauleth]

@inhibitormonoaminooksydazy: Fisher-Yates shuffle algorithm

[inhibitormonoaminooksydazy]

@Hauleth: Próbowałem wykorzystać odmianę Fishera-Yatesa, metodę Durstenfelda. Ale w obu tych metodach możliwe jest wystąpienie wartości w tych samych miejscach co poprzednio. Czyli nie o to mi chodzi.

[Hauleth]

@inhibitormonoaminooksydazy: wystarczy "źle" zaimplementować Fishera-Yatesa (https://en.wikipedia.org/wiki/Fisher–Yatesshuffle#Implementationerrors)

[inhibitormonoaminooksydazy]

@Hauleth: czytam i jedyne co widzę to ten fragment:
Sattolo's algorithm, which produces only permutations consisting of a single cycle involving all elements: in particular, with this modification, no element of the array can ever end up in its original position.
Ale zastosowałem algorytm Sattolo i nie daje tego efektu który potrzebuje,bo liczby wciąż są w tych samych miejscach.