How to actually calculate if parity is even or odd?

Question

I am working on an implementation of the 15-pieces-sliding puzzle, and I am stuck at the point were I must make sure I only shuffle into "solvable permutations" - in my case with the empty tile in the down right corner: even permutations.

I have read many similar threads such as How can I ensure that when I shuffle my puzzle I still end up with an even permutation? and understand that I need to "count the parity of the number of inversions in the permutation".

I am writing in Javascript, and using Fischer-Yates-algorithm to randomize my numbers:

var allNrs = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14];
for (var i = allNrs.length - 1; i > 0; i--) {
   var j = Math.floor(Math.random() * (i + 1));
   var temp1 = allNrs[i];
   var temp2 = allNrs[j];
   allNrs[i] = temp2;
   allNrs[j] = temp1;
}

How do I actually caculate this permutation or parity value that I have read about in so many posts?

This is probably more a math (algebra / group theory) question than a programming question. — djechlin, May 25 '13 at 00:34
Since it's more about the algorithm than its specific implementation in JavaScript, the question might be better suited to http://programmers.stackexchange.com/ — Marcelo De Polli, May 25 '13 at 00:50

Ilya Kogan · Accepted Answer · 2013-05-25T00:36:11.483

2

Just count the number of swaps you're making. If the number of swaps is even then the permutation has an even parity.

For example, these are the even permutations for 3 numbers. Note that you need 0 or 2 swaps to get to them from [1,2,3]:

1,2,3
2,3,1
3,1,2

edited May 25 '13 at 00:36

answered May 25 '13 at 00:30

Ilya Kogan

21,995
15
85
141

Well, my code makes 14 swaps every time. Which then would mean even parity? But I can manage to reach the Sam Loyd scenario (with only 14 and 15 swapped) from some of the shuffles, which means it is unsolvable. What am I missing here? – fyrm May 25 '13 at 00:51
1

Are you sure some of your scenarios don't swap a number with itself? Maybe you should multiply the random by `i` instead of `i+1`. – Ilya Kogan May 25 '13 at 01:59
That seems to make sense. Will test later today. – fyrm May 25 '13 at 06:53

score 0 · Answer 2 · answered May 25 '13 at 00:35

Each swap of two numbers you do flips the parity. If you have an even number of them, you are good. If you have an odd number, you are not.

This is essentially what parity means and it is a (simple) theorem of group theory that any two ways to get to the same shuffle have the same parity.

How to actually calculate if parity is even or odd?

2 Answers2