## Friday, May 31, 2013

### Ordering list elements with component intervals

Every list induces an equivalence relation of its indexes called the kernel of the list. Every finite totally ordered set has a component interval which includes the parts of a partition of the indexes of a list. Here is an example in which we compute the component intervals:
(= (component-intervals [3 0 1 0 1 2 3 4])
[[1 3] [2 4] [5 5] [0 6] [7 7]]

Since the set of intervals of a partially ordered set is itself partially ordered we know that we can partially order those five intervals to get the following ordering relation:
(= (order-from-list [3 0 1 0 1 2 3 4 ])
[[1 0 1 0 1]
[0 1 1 0 1]
[0 0 1 0 1]
[0 0 0 1 1]
[0 0 0 0 1]]

The order type of the above partial ordering relation is the rooted tree {{{} 2} 1, {} 1}. Producing all the different configurations of a list that satisfy an unbounded partial order is a far more complex task that once achieved can be used to compute all the different permutations of a list by their ordering.