sicmutils.util.permute — sicmutils 0.21.1

Utilities for generating permutations of sequences.

cartesian-product clj/s

(cartesian-product colls)

Accepts a sequence of collections colls and returns a lazy sequence of the cartesian product of all collections.

The cartesian product of N collections is a sequences of sequences, each N long, of every possible way of choosing N items where the first comes from the first entry in colls, the second from the second entry and so on.

NOTE: This implementation comes from Alan Malloy at this StackOverflow post. Thanks, Alan!

combinations clj/s

(combinations xs p)

Returns a lazy sequence of every possible set of p elements chosen from xs.

list-interchanges clj/s

(list-interchanges permuted-list original-list)

Given a permuted-list and the original-list, returns the number of interchanges required to generate the permuted list from the original list.

multichoose clj/s

(multichoose n k)

Returns the number of possible ways of choosing a multiset with cardinality k from a set of n items, where each item is allowed to be chosen multiple times.

number-of-combinations clj/s

(number-of-combinations n k)

Returns 'n choose k', the number of possible ways of choosing k distinct elements from a collection of n total items.

number-of-permutations clj/s

(number-of-permutations n)

Returns the number of possible ways of permuting a collection of n distinct elements.

permutation-interchanges clj/s

(permutation-interchanges permuted-list)

permutation-parity clj/s

(permutation-parity permuted-list)

(permutation-parity permuted-list original-list)

If a single permuted-list is supplied, returns the parity of the number of interchanges required to sort the permutation.

NOTE that the requirement that elements be sortable currently constrains permuted-list's elements to be numbers that respond to >=.

For two arguments, given a permuted-list and the original-list, returns the parity (1 for even, -1 for odd) of the number of the number of interchanges required to generate the permuted list from the original list.

In the two-argument case, if the two lists aren't permutations of each other, returns 0.

permutation-sequence clj/s

(permutation-sequence as)

Produces an iterable sequence developing the permutations of the input sequence of objects (which are considered distinct) in church-bell-changes order - that is, each permutation differs from the previous by a transposition of adjacent elements (Algorithm P from §7.2.1.2 of Knuth).

This is an unusual way to go about this in a functional language, but it's fun.

This approach has the side-effect of arranging for the parity of the generated permutations to alternate; the first permutation yielded is the identity permutation (which of course is even).

Inside, there is a great deal of mutable state, but this cannot be observed by the user.

permutations clj/s

(permutations xs)

Returns a lazy sequence of every possible arrangement of the elements of xs.

permute clj/s

(permute permutation xs)

Given a permutation (represented as a list of numbers), and a sequence xs to be permuted, construct the list so permuted.

sort-and-permute clj/s

(sort-and-permute ulist <? cont)

cont = (fn [ulist slist perm iperm] ...)

Given a short list and a comparison function, to sort the list by the comparison, returning the original list, the sorted list, the permutation procedure and the inverse permutation procedure developed by the sort.

subpermute clj/s

(subpermute m xs)

Given a sequence xs and a map m of replacement indices, returns a new version of xs with the element at the position marked by each key in m replaced by the element at each value in the original xs.