Category talk:Wren-perm: Difference between revisions
Content added Content deleted
(Added source code for new 'Wren-perm' module.) |
(→Source code: Added 2 more methods to Perm class and fixed some minor issues.) |
||
Line 6: | Line 6: | ||
/* |
/* |
||
Perm is a class containing static methods to count or emit the permutations of a given array. |
Perm is a class containing static methods to count or emit the permutations of a given array. |
||
In the interests of speed, permutations are usually emitted in no particular order. However, |
|||
Permutations are emitted in lexographic order of the array indices. So, if the array is sorted |
|||
slower methods are included to emit them in lexicographic order of the array indices where needed. |
|||
to begin with, |
So, if the array is sorted to begin with, such permutations will be in sorted order too. |
||
*/ |
*/ |
||
class Perm { |
class Perm { |
||
Line 36: | Line 37: | ||
} |
} |
||
/* Non-lexicographic methods */ |
|||
⚫ | |||
⚫ | |||
static list(a) { |
static list(a) { |
||
Check.list("array", a, 1) |
Check.list("array", a, 1) |
||
Line 62: | Line 65: | ||
} |
} |
||
// Returns a list of all distinct permutations of the array 'a'. |
// Returns a list of all distinct permutations of the array 'a' in no particular order. |
||
// Use only if not all elements are distinct. |
// Use only if not all elements are distinct. |
||
static listDistinct(a) { |
static listDistinct(a) { |
||
Check.list("array", a, 1) |
|||
var perms = [] |
var perms = [] |
||
var n = a.count |
var n = a.count |
||
Line 95: | Line 99: | ||
} |
} |
||
// Generates all the permutations of the array 'a' |
// Generates all the permutations of the array 'a' in no particular order |
||
// and yields them one by one. |
|||
static generate(a) { |
static generate(a) { |
||
Check.list("array", a, 1) |
Check.list("array", a, 1) |
||
Line 119: | Line 124: | ||
} |
} |
||
// Generates all the distinct permutations of the array 'a' |
// Generates all the distinct permutations of the array 'a' in no particular order |
||
// and yields them one by one. |
|||
// Use only if not all elements are distinct. |
// Use only if not all elements are distinct. |
||
static generateDistinct(a) { |
static generateDistinct(a) { |
||
Check.list("array", a, 1) |
|||
var perms = [] |
var perms = [] |
||
var n = a.count |
var n = a.count |
||
Line 150: | Line 157: | ||
permute.call(0) |
permute.call(0) |
||
} |
|||
/* Lexicographic methods */ |
|||
// Returns a list of all the permutations of the array 'a' in lexicographic order by index. |
|||
static listLex(a) { |
|||
Check.list("array", a, 1, 18) |
|||
var n = a.count - 1 |
|||
var p = (0..n).toList |
|||
var perms = [p.toList] |
|||
for (c in 1...count(n+1)) { |
|||
var i = n - 1 |
|||
var j = n |
|||
while (p[i] > p[i+1]) i = i - 1 |
|||
while (p[j] < p[i]) j = j - 1 |
|||
p.swap(i, j) |
|||
j = n |
|||
i = i + 1 |
|||
while (i < j) { |
|||
p.swap(i, j) |
|||
i = i + 1 |
|||
j = j - 1 |
|||
} |
|||
perms.add(p.toList) |
|||
} |
|||
for (i in 0...perms.count) { |
|||
perms[i] = perms[i].map { |i| a[i] }.toList |
|||
} |
|||
return perms |
|||
} |
|||
// Generates all the permutations of the array 'a' in lexicographic order by index |
|||
// and yields them one by one. |
|||
static generateLex(a) { |
|||
Check.list("array", a, 1, 18) |
|||
var n = a.count - 1 |
|||
var p = (0..n).toList |
|||
Fiber.yield(a.toList) |
|||
for (c in 1...count(n+1)) { |
|||
var i = n - 1 |
|||
var j = n |
|||
while (p[i] > p[i+1]) i = i - 1 |
|||
while (p[j] < p[i]) j = j - 1 |
|||
p.swap(i, j) |
|||
j = n |
|||
i = i + 1 |
|||
while (i < j) { |
|||
p.swap(i, j) |
|||
i = i + 1 |
|||
j = j - 1 |
|||
} |
|||
Fiber.yield(p.map { |i| a[i] }.toList) |
|||
} |
|||
} |
} |
||
} |
} |