I got hit by an interesting problem of “Zebra Puzzle” the other day. It is a well known logic puzzle believed to be first invented by Albert Einstein.
The question here is, how do we use our favorite programming language to solve this problem?
The first obstacle I found is that we need to generate all permutation of given list. Say if we have [1,2,3], we have a total of 3! = 6 which are [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1]. I couldn’t find simple Javascript code for this so I ended up writing one. Reinventing the wheel is fun, isn’t it? :))
Wikipedia suggests the following algorithm for generating all permutation systematically.
The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place.
- Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
- Find the largest index l such that a[k] < a[l]. Since k + 1 is such an index, l is well defined and satisfies k < l.
- Swap a[k] with a[l].
- Reverse the sequence from a[k + 1] up to and including the final element a[n].
Here is my PermutationGenerator module implemented in Javascript.
/////////////////////////////////////////////
// Permutation Generator
// - generate all permutation of given string
// array
// - Natthawut Kulnirundorn <m3rlinez at email by google>
// http://www.solidskill.net 10 July 2011
/////////////////////////////////////////////
var PermutationGenerator = (function () {
var self = {};
// Get start sequence of given array
self.getStartSequence = function (list) {
return list.slice(0).sort();
};
// Get next sequence from given array
// Ref: http://en.wikipedia.org/wiki/Permutation#Systematic_generation_of_all_permutations
self.getNextSequence = function (list) {
// Make clone
var a = list.slice(0);
//The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place.
// 1. Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
var k = -1;
for (var i = 0; i < a.length - 1; ++i) {
if (a[i] < a[i + 1]) { k = i; }
}
if (k == -1) return null; // means this is the last one
// 2. Find the largest index l such that a[k] < a[l]. Since k + 1 is such an index, l is well defined and satisfies k < l.
var l = -1;
for (var i = 0; i < a.length; ++i) {
if (a[k] < a[i]) { l = i };
}
if (l == -1) return null; // impossible
// 3. Swap a[k] with a[l].
var tmp = a[k]; a[k] = a[l]; a[l] = tmp;
// 4. Reverse the sequence from a[k + 1] up to and including the final element a[n].
var next = a.slice(0, k + 1).concat(a.slice(k + 1).reverse());
return next;
};
return self;
} ());
/////////////////////////////////////////////
// Test Cases
/////////////////////////////////////////////
var PermutationGeneratorTest = (function () {
var self = {};
function getStartSequence_Test1() {
var a = ['red', 'white', 'green', 'yellow', 'blue'];
var res = PermutationGenerator.getStartSequence(a);
log('input = ' + a);
log('output = ' + res);
}
function generateSequence(list) {
var current = PermutationGenerator.getStartSequence(list);
var count = 1;
log('start = ' + current);
while (true) {
current = PermutationGenerator.getNextSequence(current);
if (current == null) { break; }
log('next' + (++count) + ' = ' + current);
}
}
function getNextSequence_TestNormal() {
generateSequence(['English', 'Spanish', 'Japanese']);
}
function getNextSequence_TestEmpty() {
generateSequence([]);
}
function getNextSequence_TestRepeat() {
generateSequence(['gant', 'gant', 'korkore', 'jan']);
}
self.runTests = function () {
log("=== getStartSequence 1 ===");
getStartSequence_Test1();
log("=== getNextSequence Normal ===");
getNextSequence_TestNormal();
log("=== getNextSequence Empty ===");
getNextSequence_TestEmpty();
log("=== getNextSequence Repeat ===");
getNextSequence_TestRepeat();
};
return self;
} ());
I have put the working example on http://www.solidskill.net/ZebraPuzzle.htm. There are other parts of code that search through the solution space, setup the constraints for Zebra puzzle. But they are not discussed here.
There are some things to note about this implementation though. First, it is not very efficient. You can see in the getNextSequence(..) loop that there are loops used to search for k and l that satisfy the conditions.
Second, there could be problem with list of integers. The Array.sort() in Javascript sort using string interpretation by default. So [4, –1, 100, 500].sort() would return [-1, 100, 4, 500] instead of expected [-1, 4, 100, 500]. One must give Array.sort() function the comparer in order to properly sort list of integer. I design this module to work with list of strings initially.
Hope this helps those who are looking for permutation generation code.
