Category talk:Wren-perm
Source code
<lang ecmascript>/* Module "perm.wren" */
import "./check" for Check
/*
Perm is a class containing static methods to count or emit the permutations of a given array. Permutations are emitted in lexographic order of the array indices. So, if the array is sorted to begin with, the permutations will be in sorted order too.
- /
class Perm {
// Returns the number of permutations of an array with 'n' different elements.
static count(n) {
Check.int("n", n, 1, 18)
if (n == 1) return 1
var fact = 1
for (i in 2..n) fact = fact * i
return fact
}
// Returns the number of permutations of an array with 'n' elements which are not all different.
// The argument 'f' is a list of the frequencies of the different elements in any order.
static countDistinct(n, f) {
Check.int("n", n, 1, 18)
Check.typedList("frequency array", f, "Int", false, 1)
var sum = f.reduce { |acc, i| acc + i }
if (n != sum) {
Fiber.abort("The elements of the array must sum to 'n'.")
}
var prod = 1
for (e in f) {
if (e < 1) Fiber.abort("The elements of the frequency array must be positive integers.")
if (e > 1) prod = prod * count(e)
}
return count(n)/prod
}
// Returns a list of all the permutations of the array 'a'.
static list(a) {
Check.list("array", a, 1)
var perms = []
var n = a.count
a = a.toList
var permute
permute = Fn.new { |start, end|
if (start == end) {
perms.add(a.toList)
} else {
var i = start
while (i <= end) {
a.swap(start, i)
permute.call(start+1, end)
a.swap(start, i)
i = i + 1
}
}
}
permute.call(0, n - 1)
return perms
}
// Returns a list of all distinct permutations of the array 'a'.
// Use only if not all elements are distinct.
static listDistinct(a) {
var perms = []
var n = a.count
a = a.toList
var shouldSwap = Fn.new { |start, curr|
var i = start
while (i < curr) {
if (a[i] == a[curr]) return false
i = i + 1
}
return true
}
var permute
permute = Fn.new { |index|
if (index >= n) perms.add(a.toList)
var i = index
while (i < n) {
if (shouldSwap.call(index, i)) {
a.swap(index, i)
permute.call(index+1)
a.swap(index, i)
}
i = i + 1
}
}
permute.call(0)
return perms
}
// Generates all the permutations of the array 'a' and yields them one by one.
static generate(a) {
Check.list("array", a, 1)
var n = a.count
a = a.toList
var permute
permute = Fn.new { |start, end|
if (start == end) {
Fiber.yield(a.toList)
} else {
var i = start
while (i <= end) {
a.swap(start, i)
permute.call(start+1, end)
a.swap(start, i)
i = i + 1
}
}
}
permute.call(0, n - 1) }
// 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) {
var perms = []
var n = a.count
a = a.toList
var shouldSwap = Fn.new { |start, curr|
var i = start
while (i < curr) {
if (a[i] == a[curr]) return false
i = i + 1
}
return true
}
var permute
permute = Fn.new { |index|
if (index >= n) Fiber.yield(a.toList)
var i = index
while (i < n) {
if (shouldSwap.call(index, i)) {
a.swap(index, i)
permute.call(index+1)
a.swap(index, i)
}
i = i + 1
}
}
permute.call(0) }
}
/*
Comb is a class containing static methods to count or emit the combinations of a given array. Combinations are emitted in lexographic order of the array indices. So, if the array is sorted to begin with, the combinations will be in sorted order too.
- /
class Comb {
// Returns the number of combinations of an array with 'n' different elements taken 'k' at a time.
static count(n, k) {
Check.int("n", n, 1)
Check.int("k", k, 1, n.min(18))
if (n == 1) return 1
var fact = 1
for (i in n-k+1..n) fact = fact * i
if (fact > Num.maxSafeInteger) Fiber.abort("Too large to be safely calculated.")
return fact / Perm.count(k)
}
// Returns a list of all the combinations of the array 'a' taken 'k' elements at a time.
static list(a, k) {
Check.list("array", a, 1)
var n = a.count
Check.int("k", k, 1, n.min(18))
var c = List.filled(k, null)
var combs = []
var combine
combine = Fn.new { |start, end, index|
if (index == k) {
combs.add(c.toList)
return
}
var i = start
while (i <= end && end - i + 1 >= k - index) {
c[index] = a[i]
combine.call(i+1, end, index+1)
i = i + 1
}
}
combine.call(0, n-1, 0)
return combs
}
// Returns a list of all distinct combinations of the array 'a' taken 'k' elements at a time.
// Use only if not all elements are distinct and 'a' is in sorted order to start with.
static listDistinct(a, k) {
Check.list("array", a, 1)
var n = a.count
Check.int("k", k, 1, n.min(18))
var c = List.filled(k, null)
var combs = []
var combine
combine = Fn.new { |start, end, index|
if (index == k) {
combs.add(c.toList)
return
}
var i = start
while (i <= end && end - i + 1 >= k - index) {
c[index] = a[i]
combine.call(i+1, end, index+1)
while (i + 1 < n && a[i] == a[i+1]) i = i + 1
i = i + 1
}
}
combine.call(0, n-1, 0)
return combs
}
// Generates all the combinations of the array 'a' taken 'k' elements at a time and yields them one by one.
static generate(a, k) {
Check.list("array", a, 1)
var n = a.count
Check.int("k", k, 1, n.min(18))
var c = List.filled(k, null)
var combine
combine = Fn.new { |start, end, index|
if (index == k) {
Fiber.yield(c.toList)
return
}
var i = start
while (i <= end && end - i + 1 >= k - index) {
c[index] = a[i]
combine.call(i+1, end, index+1)
i = i + 1
}
}
combine.call(0, n-1, 0)
}
// Generates all distinct combinations of the array 'a' taken 'k' elements at a time and yields them one by one.
// Use only if not all elements are distinct and 'a' is in sorted order to start with.
static generateDistinct(a, k) {
Check.list("array", a, 1)
var n = a.count
Check.int("k", k, 1, n.min(18))
var c = List.filled(k, null)
var combine
combine = Fn.new { |start, end, index|
if (index == k) {
Fiber.yield(c.toList)
return
}
var i = start
while (i <= end && end - i + 1 >= k - index) {
c[index] = a[i]
combine.call(i+1, end, index+1)
while (i + 1 < n && a[i] == a[i+1]) i = i + 1
i = i + 1
}
}
combine.call(0, n-1, 0)
}
}
/*
Powerset is a class containing static methods to count or emit the elements of the powerset of a given array. Elements are emitted in lexographic order of the array indices. So, if the array is sorted to begin with, the powerset will be in sorted order too.
- /
class Powerset {
// Returns the number of elements of the powerset of an array with 'n' elements.
static count(n) {
Check.nonNegInt("n", n)
if (n == 0) return 1
var a = (0...n).toList
var total = 1
for (i in 1..n) {
total = total + Comb.count(n, i)
}
if (total > Num.maxSafeInteger) Fiber.abort("Too large to be safely calculated.")
return total
}
// Returns a list of all elements of the powerset of the array 'a'.
static list(a) {
Check.list("array", a)
var ps = [[]]
if (a.count == 0) return ps
for (i in 1..a.count) ps.addAll(Comb.list(a, i))
return ps
}
// Generates all elements of the powerset of the array 'a' and yields them one by one.
static generate(a) {
Check.list("array", a)
Fiber.yield([])
if (a.count == 0) return
for (i in 1..a.count) {
for (e in Comb.list(a, i)) Fiber.yield(e)
}
}
}</lang>