hyperfiddle.incseq
Permutations
A permutation describes a rearrangement of elements in a vector. It is
represented as a map associating each index to its image, where absence of entry implicitly defines a fixed point.
Permutations form a group with compose.
- closure : if
pandqare permutations then(compose p q)is a permutation - associativity :
(= (compose p (compose q r)) (compose (compose p q) r) (compose p q r)) - identity :
(= p (compose p {}) (compose {} p)) - invertibility :
(= {} (compose p (inverse p)) (compose (inverse p) p))
Sequence diffs
A sequence diff describes how to update a finite sequence of states. Each transformation performs 5 successive actions :
- grow the vector by allocating new slots at the end
- rearrange vector elements
- shrink the vector by discarding slots at the end
- change the state of some vector elements to a new value
- mark the state of some vector elements as frozen
It is represented as a map with 6 entries :
:grow: non-negative integer, the number of slots to append:degree: non-negative integer, the vector size after growing and before shrinking:shrink: non-negative integer, the number of slots to remove:change: a map from non-negative integers to arbitrary values, associating each position to its new state:freeze: a set of non-negative integers, the positions of frozen states:permutation: the permutation describing how to rearrange vector elements
Diffs form a semigroup with combine.
- closure : if
dandeare diffs then(combine d e)is a diff - associativity :
(= (combine d (combine e f)) (combine (combine d e) f) (combine d e f))
Incremental sequences
An incremental sequence describes a finite sequence of states varying over time. It is represented as a flow producing
successive sequence diffs. Incremental sequences are applicative functors with latest-product and monads with
latest-concat.
## Permutations
A [permutation](https://en.wikipedia.org/wiki/Permutation) describes a rearrangement of elements in a vector. It is
represented as a map associating each index to its image, where absence of entry implicitly defines a fixed point.
Permutations form a group with `compose`.
* closure : if `p` and `q` are permutations then `(compose p q)` is a permutation
* associativity : `(= (compose p (compose q r)) (compose (compose p q) r) (compose p q r))`
* identity : `(= p (compose p {}) (compose {} p))`
* invertibility : `(= {} (compose p (inverse p)) (compose (inverse p) p))`
## Sequence diffs
A sequence diff describes how to update a finite sequence of states. Each transformation performs 5 successive actions :
1. grow the vector by allocating new slots at the end
2. rearrange vector elements
3. shrink the vector by discarding slots at the end
4. change the state of some vector elements to a new value
5. mark the state of some vector elements as frozen
It is represented as a map with 6 entries :
* `:grow` : non-negative integer, the number of slots to append
* `:degree` : non-negative integer, the vector size after growing and before shrinking
* `:shrink` : non-negative integer, the number of slots to remove
* `:change` : a map from non-negative integers to arbitrary values, associating each position to its new state
* `:freeze` : a set of non-negative integers, the positions of frozen states
* `:permutation` : the permutation describing how to rearrange vector elements
Diffs form a semigroup with `combine`.
* closure : if `d` and `e` are diffs then `(combine d e)` is a diff
* associativity : `(= (combine d (combine e f)) (combine (combine d e) f) (combine d e f))`
## Incremental sequences
An incremental sequence describes a finite sequence of states varying over time. It is represented as a flow producing
successive sequence diffs. Incremental sequences are applicative functors with `latest-product` and monads with
`latest-concat`.arrangeclj
Arranges elements of v according to permutation p.
Arranges elements of `v` according to permutation `p`.
combineclj
Returns the diff applying given diffs successively.
Returns the diff applying given diffs successively.
composeclj
Returns the composition of given permutations.
Returns the composition of given permutations.
countclj
(count incseq)Returns the size of incseq as a continuous flow.
Returns the size of `incseq` as a continuous flow.
cycleclj
Returns the cyclic permutation denoted by given sequence of indices.
Returns the cyclic permutation denoted by given sequence of indices.
decomposeclj
(decompose p)Decompose permutation p as a product of disjoint cycles, represented as a set of vectors. 1-cycles matching fixed
points are omitted, the size of each cycle is therefore at least 2.
Decompose permutation `p` as a product of disjoint cycles, represented as a set of vectors. 1-cycles matching fixed points are omitted, the size of each cycle is therefore at least 2.
diff-byclj
Returns a flow producing the successive diffs of given continuous flow of collections, stabilized by given key function.
Returns a flow producing the successive diffs of given continuous flow of collections, stabilized by given key function.
empty-diffclj
Return the empty diff for n-item collection.
Return the empty diff for `n`-item collection.
fixedclj
Returns the incremental sequence defined by the fixed collection of given continuous flows. A collection is fixed iff its size is invariant and its items are immobile.
Returns the incremental sequence defined by the fixed collection of given continuous flows. A collection is fixed iff its size is invariant and its items are immobile.
inverseclj
Returns the inverse of permutation p.
Returns the inverse of permutation `p`.
involution?clj
Returns true if permutation p is an
involution, i.e. its order is 2.
Returns `true` if permutation `p` is an [involution](https://en.wikipedia.org/wiki/Involution_(mathematics)#Group_theory), i.e. its order is 2.
latest-concatclj
(latest-concat incseq-of-incseqs)Returns the incremental sequence defined by the concatenation of incremental sequences defined by given incremental sequence.
Returns the incremental sequence defined by the concatenation of incremental sequences defined by given incremental sequence.
latest-productclj
(latest-product f & incseqs)Returns the incremental sequence defined by applying the cartesian product of items in given incremental sequences, combined with given function.
Returns the incremental sequence defined by applying the cartesian product of items in given incremental sequences, combined with given function.
orderclj
Returns the order of permutation p, i.e. the smallest positive
integer n such that (= {} (apply compose (repeat n p))).
Returns the [order](https://en.wikipedia.org/wiki/Order_(group_theory)) of permutation `p`, i.e. the smallest positive
integer `n` such that `(= {} (apply compose (repeat n p)))`.patch-vecclj
Returns the application of diff d to vector v.
Returns the application of diff `d` to vector `v`.
recomposeclj
Reconstructs the permutation defined by given set of disjoint cycles.
Reconstructs the permutation defined by given set of disjoint cycles.
rotationclj
Returns the permutation moving an item from index i to index j and shifting items in-between.
(= (rotation i j) (inverse (rotation j i)))
Returns the permutation moving an item from index `i` to index `j` and shifting items in-between. ```clojure (= (rotation i j) (inverse (rotation j i))) ```
spineclj
(spine)(spine sentinel)(spine sentinel compare)Returns a new port maintaining a sorted map, initially empty. The successive values in each map entry can be observed using the port as an incremental sequence.
The map is mutated by calling the port with 3 arguments : a key, a reducing function and an arbitrary value. The state
associated with the key will be updated with the result of calling the reducing function with the current state and the
argument. Absence of entry is indicated by optional sentinel value, nil by default. Keys must be comparable with
optional compare function, clojure.core/compare by default.
Returns a new port maintaining a sorted map, initially empty. The successive values in each map entry can be observed using the port as an incremental sequence. The map is mutated by calling the port with 3 arguments : a key, a reducing function and an arbitrary value. The state associated with the key will be updated with the result of calling the reducing function with the current state and the argument. Absence of entry is indicated by optional `sentinel` value, `nil` by default. Keys must be comparable with optional `compare` function, `clojure.core/compare` by default.
split-swapclj
Returns the permutation swapping two contiguous blocks of respective sizes l and r at index i.
(= (split-swap i l r) (inverse (split-swap i r l)))
Returns the permutation swapping two contiguous blocks of respective sizes `l` and `r` at index `i`. ```clojure (= (split-swap i l r) (inverse (split-swap i r l))) ```
transposition?clj
Returns true if permutation p is a
transposition, i.e. it is a 2-cycle.
Returns `true` if permutation `p` is a [transposition](https://en.wikipedia.org/wiki/Cyclic_permutation#Transpositions), i.e. it is a 2-cycle.
cljdoc is a website building & hosting documentation for Clojure/Script libraries
× close