"Richard A. DeVenezia" <ra******@ix.netcom.com> writes:
This function writes a function that enumerates permutations of n things by
iterations.
Yes, the dense interaction of abstract and specific is a difficult brew to
understand and maintain.
Yes, there are recursive techniques that can do the same thing (I haven't
done any benchmarking to see if lots of loops with lots of ifs is faster
than lots of loops of recursive function calls)
My guess is that the recursive version will be simpler and therefore
faster.
The way you generate ifs, the inner loop (which will run n times) will
start with n-1 if statements that will continue the loop in all but
one case. There will be approx. (1/2)*n^2 if statements, which will all
have been tested for each permutation you generate, as well as all the
tests that fail and continue a loop. I believe the time complexity
is quite bad for this approach.
Here is a recursive function for comparison :)
---
function perm(arr,acc) { // arr(ay): elements yet to permute
// acc(umulator): elements placed so far
if (!acc) {acc=[];}
if (arr.length == 0) {
return [acc.slice(0)]; // return copy of accumulator
}
var result = [];
var tmp = arr.pop(); // pick element to fill hole with
for(var i=0;i<arr.length;i++) {
acc.push(arr[i]); // push each other element on acc
arr[i] = tmp; // fill hole with elem from above
result = result.concat(perm(arr,acc)); // recurse
arr[i] = acc.pop(); // restore element
}
acc.push(tmp); // push picked element
result = result.concat(perm(arr,acc)); // recurse
arr.push(acc.pop()); // restore arr and acc
return result;
}
alert(perm([0,1,2,3]).join("\n"));
---
/L
--
Lasse Reichstein Nielsen -
lr*@hotpop.com
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'
