On Nov 26, 12:15 am, [EMAIL PROTECTED] wrote: > bullockbefriending bard napisa³(a): > > > > > 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)) > > > The reason I want to do this is to use it in some simple one- > > dimensional clustering, i.e. each set item (won't be just integers as > > above) will have a value of interest, and i'll select the particular > > set partition which minimises Sigma SSD (sum of squared differences > > from mean) of these values. > > > It seems overkill to generate the full list of set partitions > > [including e.g. ((1 4) (2) (3 5))] because I intend to begin by > > sorting the input sequence such that element 1 < element 2 < ... < > > element n. > > > Structural Recursion not being my strong point, any ideas on how to go > > about this would be much appreciated! > > I'm not sure if I correctly understood the semantics of what you need. > Anyway it looks like a nice exercise in nested generators: > > def segmentations(sequence, k): > assert 1 <= k <= len(sequence) > if k == 1: > yield [sequence] > else: > for headlen in xrange(1, len(sequence) - k + 2): > head, tail = sequence[:headlen], sequence[headlen:] > for tail_seg in segmentations(tail, k - 1): > yield [head] + tail_seg > > for segmentation in segmentations((1, 2, 3, 4, 5), 3): > print segmentation > > Regards, > Marek
Exactly what I needed. Thank you all for examples and also for explaining how to think about problems of this nature! -- http://mail.python.org/mailman/listinfo/python-list
