Skip to content

Instantly share code, notes, and snippets.

@Hermann-SW
Last active September 23, 2022 08:07
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Hermann-SW/f61aa890a12671fa19beae7ab1bb95be to your computer and use it in GitHub Desktop.
Save Hermann-SW/f61aa890a12671fa19beae7ab1bb95be to your computer and use it in GitHub Desktop.
Generating permutations (in order), with or without abortion
function nth(P) {
var n=P.length; var S = []; var fac=[1];
for(i=1; i<=n; ++i) { S.push(i); fac.push(i*fac[i-1]); }
var p=0;
for(i=0; i<P.length-1; ++i) {
var j = S.indexOf(P[i]);
p += j*fac[n-1-i];
S.splice(j, 1);
}
return p;
}
function seq(S, i, m) {
if (S.length===1) return S;
return S.splice(Math.floor(i/m), 1).concat(seq(S, i%m, m/S.length));
}
function perm_abort(n, f) {
var fac=[1]; for(i=1; i<=n; ++i) fac.push(i*fac[i-1]);
for(i=0, j=0; j<fac[n]; j = j - (j % fac[n-i]) + fac[n-i]) {
var S = []; for(i=1; i<=n; ++i) S.push(i);
var a = seq(S, j, fac[n-1]);
i = a.indexOf(n);
f(a.slice(0, i+1));
}
}
function perm(n, f) {
var fac=[1]; for(i=1; i<=n; ++i) fac.push(i*fac[i-1]);
for(i=0, j=0; j<fac[n]; j = j + 1) {
var S = []; for(i=1; i<=n; ++i) S.push(i);
f(seq(S, j, fac[n-1]));
}
}
var N = (process.argv.length > 2) ? parseInt(process.argv[2]) : 5;
if (process.argv.length > 3) {
perm_abort(N, function(a) { console.log(a); });
} else {
perm(N, function(a) { console.log(a, nth(a)); });
}
@Hermann-SW
Copy link
Author

Hermann-SW commented Sep 21, 2022

nodejs perm.js N does generate all permutaions of {1,2,...,N} in order.
And calls a passed function for each, here "console.log()":

$ nodejs perm.js 3
[ 1, 2, 3 ]
[ 1, 3, 2 ]
[ 2, 1, 3 ]
[ 2, 3, 1 ]
[ 3, 1, 2 ]
[ 3, 2, 1 ]
$

With abortion it outputs prefix of permutation up to N.
And does big step in iterating for loop to catch next:

$ nodejs perm.js 4 abort
[ 1, 2, 3, 4 ]
[ 1, 2, 4 ]
[ 1, 3, 2, 4 ]
[ 1, 3, 4 ]
[ 1, 4 ]
[ 2, 1, 3, 4 ]
[ 2, 1, 4 ]
[ 2, 3, 1, 4 ]
[ 2, 3, 4 ]
[ 2, 4 ]
[ 3, 1, 2, 4 ]
[ 3, 1, 4 ]
[ 3, 2, 1, 4 ]
[ 3, 2, 4 ]
[ 3, 4 ]
[ 4 ]
$

@Hermann-SW
Copy link
Author

Related integer sequence on oeis.org:
https://oeis.org/A000522

$ for((i=1; i<=9; ++i))
> do
> nodejs perm.js $i abort | grep "\[" | wc --lines
> done
1
2
5
16
65
326
1957
13700
109601
$ 

@Hermann-SW
Copy link
Author

Newly added function "nth(P)" determines index of permutation P (of numbers {1,...,n}) from 0..(n!-1).
Allows to create "next" and "previous" permutations for a given permutation P.
Demo in not "abort" case only:

$ nodejs perm.js 4
[ 1, 2, 3, 4 ] 0
[ 1, 2, 4, 3 ] 1
[ 1, 3, 2, 4 ] 2
[ 1, 3, 4, 2 ] 3
[ 1, 4, 2, 3 ] 4
[ 1, 4, 3, 2 ] 5
[ 2, 1, 3, 4 ] 6
[ 2, 1, 4, 3 ] 7
[ 2, 3, 1, 4 ] 8
[ 2, 3, 4, 1 ] 9
[ 2, 4, 1, 3 ] 10
[ 2, 4, 3, 1 ] 11
[ 3, 1, 2, 4 ] 12
[ 3, 1, 4, 2 ] 13
[ 3, 2, 1, 4 ] 14
[ 3, 2, 4, 1 ] 15
[ 3, 4, 1, 2 ] 16
[ 3, 4, 2, 1 ] 17
[ 4, 1, 2, 3 ] 18
[ 4, 1, 3, 2 ] 19
[ 4, 2, 1, 3 ] 20
[ 4, 2, 3, 1 ] 21
[ 4, 3, 1, 2 ] 22
[ 4, 3, 2, 1 ] 23
$

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment