It's a mess, needs optimized, I need to pseudo-overload it and tidy up my messes, but hey, I have a function that composes permutations!
<html>
<head>
<title>Permutation</title>
</head>
<body>
<script type="text/javascript">
/*
Signature:
Array [Array int || int] X int -->boolean
post:
true if the int is in the permutation
*/
function contains(arr, val){
var found = false, over = false, ret = false
var ix = 0;
while(!found && !over){
if(typeof arr[ix] == 'object'){ //a cycle
var subArr = contains(arr[ix], val);
ret = subArr;
found = subArr;
ix++;
}
else{
if(arr[ix] == val){
ret = true;
found = true;
}
else if(ix++ >= arr.length){
over = true;
}
}
}
return ret;
}
/*
Signature:
Array int X int --> int
Post:
the int after val
the first int in the array if val is the last member of the array
val if the array doesn't contain int
*/
function findNextInCycle(arr, val){
var len = arr.length;
for(var i = 0; i < len; i++){
if(arr[i] == val){ //we have the value
if(i == len - 1){ //end of the permutation return the first
return arr[0];
}
else{ //return the next value
return arr[i + 1];
}
}
}
return val; //val didn't exist in the permutation
}
/*
Signature:
Array [Array int || int] X int --> boolean
Pre:
Either an array of int representing a single cycle
or an array of array(int) with any fixed points excluded
ie [1,2,3] or [[1,3], [2,4]] but not [[1,2], 3, 4]
the last should be [1,2]
Post:
the int after val
the first int in the array if val is the last member of the array
val if the array doesn't contain int
*/
//uses findNextInCycle
function findNextInPerm(arr, val){
if(contains(arr, val)){
for(var i = 0; i < arr.length; i++){
if(typeof arr[i] == 'object'){ //an array hand it off to findNextInCycle
if(contains(arr[i], val)){
return findNextInCycle(arr[i], val);
} //otherwise we carry on through the cycles
}
else{ //hand the whole thing off to findNextInCycle
return findNextInCycle(arr, val);
}
}
}
else{
return val;
}
}
/*
Signature:
Array [Array int] --> Array int || Array [Array int]
Post:
If the argument contains only a single array it will return that
Otherwise it will return an array with all single length cycles removed
*/
function fixCycles(arr){
if(arr.length == 1){
return arr[0];
}
else{
var ret = [];
for (cycle in arr){
if(arr[cycle].length > 1){
ret.push(arr[cycle]);
}
}
return ret;
}
}
/*
Signature:
Array [Array int || int] X Array [Array int || int] --> Array Array int
Pre:
The arrays must be either of int representing single cycles
or arrays of array(int) with any fixed points excluded
ie for either array [1,2,3] or [[1,3], [2,4]] but not [[1,2], 3, 4]
the last should be [1,2]
Post:
a composition of permutations
Use the fixCycles function to change this into a single permutaion
Note:
We need len because we may not have all numbers may appear in the perms
*/
function composePerms(first, second, len){
var ret = [], cache = [];
for(var i = 1; i <= len; i++){
if(!contains(ret, i)){
var at = i;
while(!contains(cache, at)){
cache.push(at);
at = findNextInPerm(first, findNextInPerm(second, at));
}
ret.push(cache);
cache = []; //reset
}
}
return ret;
}
var x = fixCycles(composePerms([1,2,4,3,5], [1,2,3,5,4], 5));
for(i in x){
document.writeln(x[i]);
} //1 4 2 5 3
// -->
</script>
</body>
</html>
Now I need to write the unit tests, and a test suite.