fourdjs/permute.js

116 lines
2.2 KiB
JavaScript
Raw Permalink Normal View History

2023-07-26 07:57:43 +00:00
// Utilities for generating sets of coordinates based on
// permutations, even permutations and changes of sign.
// Based on https://www.qfbox.info/epermute
function pandita(a) {
const n = a.length;
for( let k = n - 2; k >= 0; k-- ) {
if( a[k] < a[k + 1] ) {
for( let l = n - 1; l >= 0; l-- ) {
if( a[k] < a[l] ) {
const tmp = a[k];
a[k] = a[l];
a[l] = tmp;
const revtail = a.slice(k + 1);
revtail.reverse();
for( let i = 0; i < revtail.length; i++ ) {
a[k + 1 + i] = revtail[i];
}
return Math.floor(revtail.length / 2) + 1;
}
}
console.log("Shouldn't get here");
process.exit();
}
}
return false;
}
function permutations_old(a) {
a.sort();
const ps = [ [...a] ];
let running = true;
while( running ) {
const s = pandita(a);
if( s ) {
ps.push([...a]);
} else {
running = false;
}
}
return ps;
}
2023-07-26 07:57:43 +00:00
function permutations(a) {
a.sort();
const ps = [ [...a] ];
let running = true;
while( pandita(a) > 0 ) {
2023-07-26 07:57:43 +00:00
ps.push([...a]);
}
return ps;
}
2023-07-26 07:57:43 +00:00
function permutations_even(a) {
a.sort();
let parity = 'even';
const ps = [ [...a] ];
let running = true;
while( running ) {
const s = pandita(a);
if( s ) {
if( parity === 'even' ) {
if( s % 2 === 1 ) {
parity = 'odd';
}
} else {
if( s % 2 === 1 ) {
parity = 'even';
}
}
if( parity === 'even' ) {
ps.push([...a]);
}
} else {
running = false;
}
}
return ps;
}
// for a given permutation, say [ 1, 1, 0, 0 ], return all
// of the valid changes of sign, so:
// [ [1, 1, 0, 0 ], [ -1, 1, 0, 0 ], [ 1, -1, 0, 0 ], [-1, -1, 0, 0 ]]
// ie don't do it on the zeros
2023-07-27 09:23:26 +00:00
function expand_sign(a, label) {
const expanded = [];
const exv = a.map((v) => v ? [ -v, v ] : [ 0 ]);
for( const xv of exv[0] ) {
for( const yv of exv[1] ) {
for( const zv of exv[2] ) {
for( const wv of exv[3] ) {
2023-07-27 09:23:26 +00:00
expanded.push({label: label, x: xv, y:yv, z:zv, w:wv});
}
}
}
}
return expanded;
}
export function coordinates(a, label, even=false) {
const ps = even ? permutations_even(a) : permutations(a);
const coords = [];
for( const p of ps ) {
const expanded = expand_sign(p, label);
coords.push(...expanded);
}
return coords;
}
2023-07-26 07:57:43 +00:00