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.
--
http://mail.python.org/mailman/listinfo/python-list
