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, the permutations will be in sorted order too.
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 */
⚫
// 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) {
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' and yields them one by one.
// 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' and yields them one by one.
// 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)
}
}
}
}
}
Retrieved from "https://rosettacode.org/wiki/Category_talk:Wren-perm"