How can I use the Fisher-Yates shuffle while ensuring my permutation is even?

Posted by Mithrax on Stack Overflow See other posts from Stack Overflow or by Mithrax
Published on 2010-04-16T14:31:03Z Indexed on 2010/04/16 14:33 UTC
Read the original article Hit count: 606

Filed under:

15-puzzle

|

permutation

|

shuffle

|

knuth-fisher-yates

I'm interested making an implementation of the 14-15 puzzle:

I'm creating an array with the values 0 - 15 in increasing order:

S = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 }

Now, what I want to do is shuffle them to create a new instance of the puzzle. However, I know that if I create a board with an "odd permutation" than it is unsolvable.

Wikipedia says I need to create the puzzle with an even permutation. I believe this means that I simply have to do ensure I do an even number of swaps?

How would I modify Fisher-Yates so I ensure I end up with an even permutation at the end? If I do a swap for every element in the array that would be 16 swaps which I believe would be an even permutation. However, do I need to be concerned about swapping with itself? Is there any other way to ensure I have a valid puzzle?

© Stack Overflow or respective owner

Related posts about 15-puzzle

Creating practically solvable 15 puzzle inputs

as seen on Game Development - Search for 'Game Development'
I am now developing a 15 puzzle game. I know the method to detect unsolvable puzzles. But unlike 8-puzzle, solution for 15-puzzle takes quite long time for some input states and can be solved within 5 seconds some other set of input states. Now the problem is that I cannot give the user(the player)… >>> More
15 Puzzle Shuffle Method Issues

as seen on Game Development - Search for 'Game Development'
I am making a 15 puzzle game in C# that allows the user to enter a custom row and column value up to a maximum of a 10 x 10 puzzle. Because of this I am having problems with the shuffle method. I want to make it so the puzzle is always solvable. By first creating a winning puzzle then shuffling the… >>> More
How do you solve the 15-puzzle with A-Star or Dijkstra's Algorithm?

as seen on Stack Overflow - Search for 'Stack Overflow'
I've read in one of my AI books that popular algorithms (A-Star, Dijkstra) for path-finding in simulation or games is also used to solve the well-known "15-puzzle". Can anyone give me some pointers on how I would reduce the 15-puzzle to a graph of nodes and edges so that I could apply one of these… >>> More
How can I use the Fisher-Yates shuffle while ensuring my permutation is even?

as seen on Stack Overflow - Search for 'Stack Overflow'
I'm interested making an implementation of the 14-15 puzzle: I'm creating an array with the values 0 - 15 in increasing order: S = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 } Now, what I want to do is shuffle them to create a new instance of the puzzle. However, I know that if I… >>> More
How can I ensure that when I shuffle my puzzle I still end up with an even permutation?

as seen on Stack Overflow - Search for 'Stack Overflow'
I'm interested making an implementation of the 14-15 puzzle: I'm creating an array with the values 0 - 15 in increasing order: S = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 } Now, what I want to do is shuffle them to create a new instance of the puzzle. However, I know that if I… >>> More

Related posts about permutation

Fast permutation -> number -> permutation mapping algorithms

as seen on Stack Overflow - Search for 'Stack Overflow'
I have n elements. For the sake of an example, let's say, 7 elements, 1234567. I know there are 7! = 5040 permutations possible of these 7 elements. I want a fast algorithm comprising two functions: f(number) maps a number between 0 and 5039 to a unique permutation, and f'(permutation) maps the… >>> More
Doing permutation of different arrays in perl

as seen on Stack Overflow - Search for 'Stack Overflow'
Hello! I want to do permutation in perl. For example I have three arrays. ["big", "tiny", "small"] and then I have ["red", "yellow", "green"] and also ["apple", "pear", "banana"]. How do I get: ["big", "red", "apple"] ["big", "red", "pear"] ..etc.. ["small", "green", "banana"] I understand this… >>> More
Prolog: permutations check and multiple answers

as seen on Stack Overflow - Search for 'Stack Overflow'
Continuing to learn prolog, I'm trying to write a permutation(L1, L2) predicate. It should return true, only if L1 can be made up of all elements in L2. My code so far is the following: permutation([], []). permutation([H|T], L2) :- remove(L2, H, R), permutation(T, R). Assuming that the predicate… >>> More
Generating permutation in Python with specific rule

as seen on Stack Overflow - Search for 'Stack Overflow'
Let say a=[A, B, C, D], each element has a weight w, and is set to 1 if selected, 0 if otherwise. I'd like to generate permutation in the below order 1,1,1,1 1,1,1,0 1,1,0,1 1,1,0,0 1,0,1,1 1,0,1,0 1,0,0,1 1,0,0,0 Let's w=[1,2,3,4] for item A,B,C,D ... and max_weight = 4. For each permutation… >>> More
How can I use the Fisher-Yates shuffle while ensuring my permutation is even?

as seen on Stack Overflow - Search for 'Stack Overflow'
I'm interested making an implementation of the 14-15 puzzle: I'm creating an array with the values 0 - 15 in increasing order: S = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 } Now, what I want to do is shuffle them to create a new instance of the puzzle. However, I know that if I… >>> More