Segmentation algorithm

[chris34525]

Hi,

I have a population of 50 ordered integers (1,2,3,..,50) and I look for a generic way to slice it "n" ways ("n" is the number of cutoff points ranging from 1 to 25) that maintains the order of the elements.

For example, for n=1 (one cutoff point) there are 49 possible grouping alternatives ([1,2-49], [1-2,3-50], [1-3,4-50],...). For n=2 (two cutoff points), the grouping alternatives are like: [1,2,3-50], [1,2-3,4-50],...

Could you recommend any general-purpose algorithm to complete this task in an efficient way?

Thanks,
Chris

[agile]

As I understand you need to generate all possible cutoffs, right?
It's not a complete solution but a direction to think.
In an essence it is necessary to generate all n (1<=n<=25) selections out of 49 (since there are 49 cutoff positions between 50 numbers). I would start with an array of 49 int-s, initialize the first n of them to 1 and remaining elements to 0. Now you need to write a loop that moves the '1'-s around and exhaustively generate all selections. I think it is possible to do with two level loop.
Hope this helps.