Enumerating k-segmentations of a sequence

[Gerard flanagan]

bullockbefriending bard wrote:
> 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))
> 

What Arnaud said.


def nchoosek( n, k ):
     '''
     Generate all subsets of S(n) that have k items.
     S(n) = {1, 2, 3, ..., n}

     >>> list(nksubsets(3, 2))
     [[1, 2], [1, 3], [2, 3]]
     '''
     m = n - k + 1
     indexer = range(0, k)
     seq = range(1, k+1)
     last = range(m, n+1)
     yield seq[:]
     while seq != last:
         high_value = -1
         high_index = -1
         for i in indexer:
             val = seq[i]
             if val > high_value and val < m + i:
                 high_value = val
                 high_index = i
         for j in range(k - high_index):
             seq[j+high_index] = high_value + j + 1
         yield seq[:]

#(minimally tested)
def part(n,k):
     rng = range(1, n+1)
     for comb in nchoosek(n-1,k-1):
         comb = [0] + comb + [n]
         yield [rng[s:t] for (s,t) in (comb[i:i+2] for i in range(k))]


for item in part(5, 2):
     print item

for item in part(5, 3):
     print item

G.