Johnson-Trotter Algorithm in VC++.NET

The Johnson-Trotter algorithm is an algorithm for figuring out permutations given a value set. A permutation is a way of altering the values in a set to create a different unique sequence from the original. If we have the set 1, 2, 3, 4, 5… one permutation would be 2, 1, 4, 5, 3 and another would be 3, 4, 2, 1, 5. Using a quirky little algorithm, we can transpose (aka swap) values in the set to obtain all the permutations of that given set. You could use such an algorithm for finding a word that might be scrambled or obtaining a unique sequence given the set contains enough values. We will run through this little exercise of finding permutations of a 4 element set using VC++.NET right here on the Programming Underground!

There are many algorithms out there for finding permutations. This is only one of many, and like all algorithms, it certainly has its limitations. But even though the understanding of the algorithm is not exactly hard, it does contain a few rules we must follow. Each value in our set of numbers is given a direction of mobility. This means that as we swap the value also has a direction in which it swaps.

1) It can either swap with the neighbor on the immediate left or right (determined by its mobility). Now if a value is to the far left and has mobility of left, it is considered immobile. Same with if it is to the far right and has mobility right. To start, all values have left mobility.

2) The swap will only take place if the neighbor next to it (in the direction of its mobility) is less than the value being swapped. Otherwise it is considered locked as well. eg. If 5 and 4 are side by side and both moving left, no swap is made to the left because 5 is bigger than 4. 4 is currently locked in place. But if it was 1 and 4, then 4 will swap.

3) One swap takes place on each pass. All values in the set which are of a higher value than the swapped value will have their direction of mobility switched to the other direction.

What our algorithm does is looks for the highest mobile value in the set, then swaps it in the direction of its mobility. If the highest value is considered locked, it will then look for the second, third, fourth highest mobile number and so on until there are no more mobile numbers.

So what we need to do this is a way to 1) Find the highest currently mobile number or return a sentinel value if no more are mobile 2) A routine to swap the values in the set and 3) A main loop which will print each permutation and continue until all permutations are exhausted.

Lets go through each piece of code and show how we will fit them into a standard VC++.NET forms application. The first part will be our function for finding a mobile integer in the set and return its index in the set or -1 if it doesn’t find a mobile value.

// This method looks for mobile values in our array
// based on the highest value and the direction of movement.
int findMovableInteger(array<int>^ ar, array<int>^ direction)
{
		int curMaxIndex = -1;
		int curMaxValue = Int32::MinValue;

		// Loop through all arrays looking for the highest value which
		// has mobility. (See rules for mobility in Johnson-Trotter algorithm)
		for (int i = 0; i < ar->Length; i++)
		{
			// If it is at the start with left mobility, skip
			// If at the far right with right mobility, skip
			// Others are possible candidates, so find the highest of those.
			if ((i == 0) && (direction[i] == 0)) { continue; }
			else if ((i == ar->Length - 1) && (direction[i] == 1)) { continue; }
			else
			{
				// Left mobile values, are they greater than their neighbors?
				// Are they also greater than our current max value?
				if (direction[i] == 0)
				{
					if ((ar[i - 1] < ar[i]) && (curMaxValue <= ar[i]))
					{
						curMaxIndex = i;
						curMaxValue = ar[i];
					}
				}
				else
				{
					// Greater than right neighbor and greater than current max value?
					if ((ar[i + 1] < ar[i]) && (curMaxValue <= ar[i]))
					{
						curMaxIndex = i;
						curMaxValue = ar[i];
					}
				}
			}
			
		}

		// Return index of current highest mobile value
		// or -1 to say there are no more mobile values.
		return curMaxIndex;
}

We kick off this routine by passing it two managed integer arrays. One which consists of the values and another which is a parallel array that keeps track of the numbers mobility. The mobility array has values which are 0 (for moving left) and 1 (for moving right). So this array will first start off all zeros.

Next we create an index of -1 and a really low integer value. Just like you would loop through an array looking for a high value, we do the same thing but with a twist. We compare each number’s position in the set, and its direction of mobility, to first see if it is “locked”. For instance, the first test makes sure that the value is not the first value in the set and has a mobility of left. It also checks to see if the value is to the far right and mobility right. Either of these two cases mean the value is locked, so we move on to the next value.

We also check if a value is moving left/right and its neighbor in that direction is less than the current value. If that is the case, then we have found a mobile value and thus record its index and store its value as the “current highest mobile value”. We loop through the whole set re-recording each high value (which is mobile) until we have the highest mobile value.

Lastly we return its index in the array or the original -1 if none of the values turned out to be mobile.

Next we need a simple swap routine for swapping our mobile value once it has been located…

// Swap function to transpose elements. We are using % because
// these need to be tracked even if they are moved by the garbage collector
// (It is managed version of references)
void swap(int% num1, int% num2) {
		int temp = num1;
		num1 = num2;
		num2 = temp;
}

This should appear pretty straight forward except for the use of the percentage signs. This is because the calling function (shown below) is passing values from a managed array. This means that the array is under the control of the garbage collector which may move the array’s memory values from their original location. These “tracker” variables are just like references in old C++, but are bound to the values in the array even if they are moved.

Now the main routine is used to do a few things. Setup our array of values (these could be collected from the user), sort the array into order, setup our mobility array for those values (initializing all left to start), keep looping through the set until it runs out of mobile integers, kicks off any swapping as needed and lastly calls print for each permutation as it is generated.

// Main algorithm which takes an array of integers
void johnsonTrotter(array<int>^ values)
{
		// First sort
		Array::Sort(values);
	   
		// We then create an array which will keep track
		// of the mobility of keys (called "direction")
		// Initialize them to the left (0)
		array<int>^ direction = gcnew array<int>(values->Length);
		for (int i = 0; i < values->Length; i++) { direction[i] = 0; }


		// Find our first mobile integer
		int mobileInt = findMovableInteger(values, direction);

		// Print our values to start
		print(values);

		// Now keep looping until we no longer have mobile integers
		while (mobileInt != -1)
		{
			// If mobile value has left mobility, do swap left
			// Both values and their mobility flag
			if (direction[mobileInt] == 0)
			{
				swap(values[mobileInt - 1], values[mobileInt]);
				swap(direction[mobileInt - 1], direction[mobileInt]);
				mobileInt--;
			}
			else
			{
				// If mobile value has right mobility, do swap right
				// And mobility flag
				swap(values[mobileInt + 1], values[mobileInt]);
				swap(direction[mobileInt + 1], direction[mobileInt]);
				mobileInt++;
			}

			// Now loop through all values and for any larger than our
			// mobile value, flip their mobility direction.
			for (int i = 0; i < values->Length; i++)
			{
				if (values[i] > values[mobileInt])
				{
					direction[i] = (direction[i] == 0) ? 1 : 0;
				}
			}

			// Print out new order
			print(values);

			// Find next mobile integer
			mobileInt = findMovableInteger(values, direction);
		}
}

We accept an array which we first sort into order. Next we create our array (same size) to keep track of the mobility of each value. We initialize this array to the left (value 0) for all elements. We find our first mobile value. After that we go into a loop where we find a mobile number, swap it and then look for all values in the set which have a value bigger than the swapped value. We then change their direction of mobility.

So for a set of 1, 2, 3, 4 we will gravitate the 4 to the beginning where it becomes locked, then we switch the 3 (it is the next highest mobile value) which in turn will cause that 4 (4 being larger than 3) to change direction and gravitate back to the end. So looking at all our mutations you will notice the 4 do a zigzag motion back and forth through the set….

 1  2  3  4
 1  2  4  3
 1  4  2  3
 4  1  2  3
 4  1  3  2
 1  4  3  2
 1  3  4  2
 1  3  2  4
 3  1  2  4
 3  1  4  2
 3  4  1  2
 4  3  1  2
 4  3  2  1
 3  4  2  1
 3  2  4  1
 3  2  1  4
 2  3  1  4
 2  3  4  1
 2  4  3  1
 4  2  3  1
 4  2  1  3
 2  4  1  3
 2  1  4  3
 2  1  3  4

One way we can check if we have all the permutations is take the factorial of the number of values in the set. So for instance, 4 numbers in the set will be 4! = 24 individual permutations. We have 24 result lines in the example above so we know that we have all the possible permutations.

Our results above are printed using a print function which dumps each permutation set into a listbox. You can dump this to screen in a console application or a file etc. The print function is simple and can even look like this…

// Simple method to print our permutations to a listbox.
void print(array<int>^ values)
{
		String^ val = "";
		for (int i = 0; i < values->Length; i++)
		{
				val = val + " " + values[i];
		}

		listBox1->Items->Add(val);
}

So that is all there is to it. I know it can be a bit confusing at first, especially if you are unfamiliar with VC++.NET coding, but I tried to keep it as simple as possible. A great place to look at the mechanics is on the Wikipedia Johnson-Trotter Algorithm page.

Keep these limitations in mind when using this…

1) The values must be in order before using the algorithm
2) No repeat values. To the algorithm one 3 looks like another 3. They are not considered individual elements. This could be overcome by making each value an object and check one object against another. Possible enhancement!
3) Since the number of permutations grow by factorials, you might want to stay under 10 elements or else you are going to be sitting there for awhile as it scrolls through all the permutations. 10! = 3,628,800 permutations.

I hope you enjoyed our little trip down the rabbit hole of another whacked out entry of the Programming Underground. Thanks for reading! 🙂