Last active
September 23, 2022 08:07
-
-
Save Hermann-SW/f61aa890a12671fa19beae7ab1bb95be to your computer and use it in GitHub Desktop.
Generating permutations (in order), with or without abortion
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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)); }); | |
} |
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
$
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
nodejs perm.js N
does generate all permutaions of {1,2,...,N} in order.And calls a passed function for each, here "console.log()":
With abortion it outputs prefix of permutation up to N.
And does big step in iterating for loop to catch next: