Sunday, July 10, 2011

Generating Permutation with Javascript

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.

  1. Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
  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.
  3. Swap a[k] with a[l].
  4. 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, also serve as a user guide :)



/////////////////////////////////////////////
// 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.

4 comments:

Max Roald Eckardt said...
This comment has been removed by the author.
Max Roald Eckardt said...

hey this looks useful! I have a few short lists to premutate so performance may not be an issue.
can I use it under the MIT license?

sandhosh said...

Really Good blog post.provided a helpful programs for generating permutation with javascript. keep updating...
Digital marketing company in Chennai

Philips Huges said...

Its a wonderful post and very helpful, thanks for all this information. You are including better information regarding this topic in an effective way.Thank you so much

Installment loans in alabama
Payday loans in alabama
Title loans in alabama
Cash Advances in alabama