Enumerating k-segmentations of a sequence

[Arnaud Delobelle]

bullockbefriending bard <kinch1967 at gmail.com> writes:

> I'm not sure if my terminology is precise enough, but what I want to
> do is:
>
> Given an ordered sequence of n items, enumerate all its possible k-
> segmentations.
>
> This is *not* the same as enumerating the k set partitions of the n
> items because I am only interested in those set partitions which
> preserve the order of the items. i.e. if the input sequence is (1 2 3
> 4 5), then ((1 4) (2 3) (5)) is unacceptable, whereas ((1 2) (3) (4
> 5)) is acceptable. Hence use of term 'segmentations'.
>
> e.g., for input sequence (1 2 3 4 5) and k = 3, I need a function
> which enumerates the following 3-segmentations:
>
> ((1 2 3) (4) (5))
> ((1 2) (3 4) (5))
> ((1 2) (3) (4 5))
> ((1) (2 3 4) (5))
> ((1) (2 3) (4 5))
> ((1) (2) (3 4 5))

All you need to do is find the 'cutting places'.  Here you are cutting
at 2 places, the first cut has to be in position > 0 and the last in
position < 5.  That makes 4 potential cutting places: 1, 2, 3, 4.

So you will have 4C2 = 6 "2-segmentations" of {1, 2, 3, 4, 5} which are
given by the subsets of {1, 2, 3, 4} of size 2, i.e the 2-combinations
of {1, 2, 3, 4}.

Generalising this, if you want to find the "k-segmentations" of a
sequence of length n, you will have (n-1)C(k-1) of them and their
cutting places will be given by (k-1)-combinations of {1, 2, ..., n-1}.

Generating the k-combinations is a standard problem so we're done!

-- 
Arnaud