/* Module "perm.wren" */
import "./check" for Check
/*
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, such 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
}
/* Non-lexicographic methods */
// Returns a list of all the permutations of the array 'a' in no particular order.
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' 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
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' in no particular order
// 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' in no particular order
// 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
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)
}
/* 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)
}
}
}
/*
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)
}
}
}
