Kod źle obliczał parzystość permutacji. Mam nadzieję, że teraz będzie dobrze:
var i,j,odd=0,blank=15,tab=[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15];
shuffle(tab);
//Check permutation parity
for(i=0; i<15; i++)
{
for(j=i+1; j<16; j++)
{
if(tab[i] > tab[j]) odd = 1-odd;
}
if(tab[i] === 15)
{
blank = i
}
}
//Blank color
var white = parseInt(blank*1.25) % 2;
//Check if game is solvable
if(white ^ odd)
{
var tmp = tab[0];
tab[0] = tab[1];
tab[1] = tmp;
}
Na czacie matematycznym dostałem taki przykład:
parity_preserving_shuffle(array) {
# Use a Knuth shuffle to give equal chances to each permutation.
odd = false
for (i=array.length - 1; i >= 0; i--) {
j = rand(i)
if (i != j) {
odd = !odd
temp = array[i]
array[i] = array[j]
array[j] = temp
}
}
# This shouldn't have a bias in which even permutations it creates.
if (odd) {
random_swap(array)
}
}
random_swap(array) {
# There are array.length*(array.length - 1)/2 different swaps.
# We want to give one equal chance to each of them.
array_length = array.length
swap_index = rand(array_length*(array_length - 1)/2)
x = floor((sqrt(8*swap_index + 1) + 1)/2)
y = array_length - x
i = y - 1
j = y + swap_index - x*(x - 1)/2
temp = array[i]
array[i] = array[j]
array[j] = temp
}
Wykorzystuje tasowanie Fisher–Yates. Jest bardziej optymalne, bo mamy tylko 1 pętlę. Czy zawsze po 1 zamianie permutacja jest nieparzysta, po 2 parzysta, po 3 nieparzysta itd? W przypadku mojego kodu parzystość permutacji można policzyć ze wzoru. Zawsze wychodzi nieparzysta. Funkcja shuffle() podana w pierwszym poście. Kod wynikowy:
var i,blank=15,tab=[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15];
shuffle(tab);
//Find blank - niestety spacja < 15
for(i=0; i<15; i++)
{
if(tab[i] === 15)
{
blank = i;
break
}
}
//Blank color
var white = parseInt(blank*1.25) % 2;
//Check if game is solvable
if(!white)
{
var tmp = tab[0];
tab[0] = tab[1];
tab[1] = tmp;
}
//Rearrange board
for(i=0, tab[blank]=''; i<16; i++)
{
rows[parseInt(i/4)].cells[i%4].innerHTML = tab[i].toString(16).toUpperCase();
}