Category talk:Wren-perm: Difference between revisions
→Source code: Added 2 more methods to Perm class and fixed some minor issues.
(Added source code for new 'Wren-perm' module.) |
(→Source code: Added 2 more methods to Perm class and fixed some minor issues.) |
||
Line 6:
/*
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,
slower methods are included to emit them in lexicographic order of the array indices where needed.
So, if the array is sorted to begin with,
*/
class Perm {
Line 36 ⟶ 37:
}
/* Non-lexicographic methods */
// Returns a list of all the permutations of the array 'a'.▼
▲ // Returns a list of all the permutations of the array 'a' in no particular order.
static list(a) {
Check.list("array", a, 1)
Line 62 ⟶ 65:
}
// Returns a list of all distinct permutations of the array 'a' in no particular order.
// Use only if not all elements are distinct.
static listDistinct(a) {
Check.list("array", a, 1)
var perms = []
var n = a.count
Line 95 ⟶ 99:
}
// Generates all the permutations of the array 'a'
// and yields them one by one.
static generate(a) {
Check.list("array", a, 1)
Line 119 ⟶ 124:
}
// Generates all the distinct permutations of the array 'a'
// and yields them one by one.
// Use only if not all elements are distinct.
static generateDistinct(a) {
Check.list("array", a, 1)
var perms = []
var n = a.count
Line 150 ⟶ 157:
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)
}
}
}
| |||