Category talk:Wren-perm

From Rosetta Code

Source code

/* 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)
        }
    }
}