每个长度为N个随机,连续和非重叠的子序列

Question

我试图获得序列的n个随机和非重叠切片,其中每个子序列的长度为l,最好是它们出现的顺序.

这是我到目前为止的代码,每次尝试使它工作变得越来越混乱,不用说它不起作用.

def rand_parts(seq, n, l):
    """
    return n random non-overlapping partitions each of length l.
    If n * l > len(seq) raise error.
    """
    if n * l > len(seq):
        raise Exception('length of seq too short for given n, l arguments')
    if not isinstance(seq, list):
        seq = list(seq)
    gaps = [0] * (n + 1)
    for g in xrange(len(seq) - (n * l)):
        gaps[random.randint(0, len(gaps) - 1)] += 1
    result = []
    for i, g in enumerate(gaps):
        x = g + (i * l)
        result.append(seq[x:x+l])
        if i < len(gaps) - 1:
            gaps[i] += x
    return result

例如,如果我们说rand_parts([1, 2, 3, 4, 5, 6], 2, 2)有6种可能的结果可以从下图中返回:

[1, 2, 3, 4, 5, 6]
 ____  ____

[1, 2, 3, 4, 5, 6]
 ____     ____ 

[1, 2, 3, 4, 5, 6]
 ____        ____ 

[1, 2, 3, 4, 5, 6]
    ____  ____ 

[1, 2, 3, 4, 5, 6]
    ____     ____ 

[1, 2, 3, 4, 5, 6]
       ____  ____

所以[[3, 4], [5, 6]]这是可以接受的,但[[3, 4], [4, 5]]不会因为它重叠而且[[2, 4], [5, 6]]也不会因为[2, 4]不是连续的.

我在做一些小码打高尔夫球时遇到了这个问题,所以为了兴趣起见,看到一个简单的解决方案和/或一个有效的解决方案也不错,对我现有的代码并不那么感兴趣.

Answer 1

def rand_parts(seq, n, l):
    indices = xrange(len(seq) - (l - 1) * n)
    result = []
    offset = 0
    for i in sorted(random.sample(indices, n)):
        i += offset
        result.append(seq[i:i+l])
        offset += l - 1
    return result

要理解这一点,首先要考虑这个案例l == 1.然后它基本上只是random.sample()按排序顺序返回一个输入数据; 在这种情况下,offset变量始终为0.

这种情况l > 1是前一种情况的延伸.我们random.sample()用来获取位置,但保持一个offset移位连续结果:这样,我们确保它们是非重叠范围 - 即它们起始于至少l彼此的距离,而不是1.