N random, contiguous and non-overlapping subsequen

问题:

I'm trying to get n random and non-overlapping slices of a sequence where each subsequence is of length l, preferably in the order they appear.

This is the code I have so far and it's gotten more and more messy with each attempt to make it work, needless to say it doesn't work.

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

For example if we say rand_parts([1, 2, 3, 4, 5, 6], 2, 2) there are 6 possible results that it could return from the following diagram:

[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]
       ____  ____

So [[3, 4], [5, 6]] would be acceptable but [[3, 4], [4, 5]] wouldn't because it's overlapping and [[2, 4], [5, 6]] also wouldn't because [2, 4] isn't contiguous.

I encountered this problem while doing a little code golfing so for interests sake it would also be nice to see both a simple solution and/or an efficient one, not so much interested in my existing code.

回答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

To understand this, first consider the case l == 1. Then it's basically just returning a random.sample() of the input data in sorted order; in this case the offset variable is always 0.

The case where l > 1 is an extension of the previous case. We use random.sample() to pick up positions, but maintain an offset to shift successive results: in this way, we make sure that they are non-overlapping ranges --- i.e. they start at a distance of at least l of each other, rather than 1.

回答2:

Many solutions can be hacked for this problem, but one has to be careful if the sequences are to be strictly random. For example, it's wrong to begin by picking a random number between 0 and len(seq)-n*l and say that the first sequence will start there, then work recursively.

The problem is equivalent to selecting randomly n+1 integer numbers such that their sum is equal to len(seq)-l*n. (These numbers will be the "gaps" between your sequences.) To solve it, you can see this question.

回答3:

This worked for me in Python 3.3.2. It should be backwards compatible with Python 2.7.

from random import randint as r

def greater_than(n, lis, l):
    for element in lis:
        if n < element + l:
            return False
    return True

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)
    # Setup
    left_to_do = n
    tried = []
    result = []
    # The main loop
    while left_to_do > 0:
        while True:
            index = r(0, len(seq) - 1)
            if greater_than(index, tried, l) and index <= len(seq) - left_to_do * l:
                tried.append(index)
                break
        left_to_do -= 1
        result.append(seq[index:index+l])
    # Done
    return result

a = [1, 2, 3, 4, 5, 6]
print(rand_parts(a, 3, 2))

The above code will always print [[1, 2], [3, 4], [5, 6]]

回答4:

If you do it recursively it's much simpler. Take the first part from (so the rest will fit):

 [0:total_len - (numer_of_parts - 1) * (len_of_parts)]

and then recurse with what left to do:

rand_parts(seq - begining _to_end_of_part_you_grabbed, n - 1, l)

回答5:

First of all, I think you need to clarify what you mean by the term random.

How can you generate a truly random list of sub-sequences when you are placing specific restrictions on the sub-sequences themselves?

As far as I know, the best "randomness" anyone can achieve in this context is generating all lists of sub-sequences that satisfy your criteria, and selecting from the pool however many you need in a random fashion.

Now based on my experience from an algorithms class that I've taken a few years ago, your problem seems to be a typical example which could be solved using a greedy algorithm making these big (but likely?) assumptions about what you were actually asking in the first place:

• What you actually meant by random is not that a list of sub-sequence should be generated randomly (which is kind of contradictory as I said before), but that any of the solutions that could be produced is just as valid as the rest (e.g. any of the 6 solutions is valid from input [1,2,3,4,5,6] and you don't care which one)
• Restating the above, you just want any one of the possible solutions that could be generated, and you want an algorithm that can output one of these valid answers.

Assuming the above here is a greedy algorithm which generates one of the possible lists of sub-sequences in linear time (excluding sorting, which is O(n*log(n))):

def subseq(seq, count, length):
    s = sorted(list(set(seq)))

    result = []
    subseq = []

    for n in s:
        if len(subseq) == length:
            result.append(subseq)
            if len(result) == count:
                return result
            subseq = [n]
        elif len(subseq) == 0:
            subseq.append(n)
        elif subseq[-1] + 1 == n:
            subseq.append(n)
        elif subseq[-1] + 1 < n:
            subseq = [n]

    print("Impossible!") 

The gist of the algorithm is as follows:

• One of your requirements is that there cannot be any overlaps, and this ultimately implies you need to deal with unique numbers and unique numbers only. So I use the set() operation to get rid all the duplicates. Then I sort it.
• Rest is pretty straight forward imo. I just iterate over the sorted list and form sub-sequences greedily.
• If the algorithm can't form enough number of sub-sequences then print "Impossible!"

Hope this was what you were looking for.

EDIT: For some reason I wrongly assumed that there couldn't be repeating values in a sub-sequence, this one allows it.

def subseq2(seq, count, length):
    s = sorted(seq)

    result = []
    subseq = []

    for n in s:
        if len(subseq) == length:
            result.append(subseq)
            if len(result) == count:
                return result
            subseq = [n]
        elif len(subseq) == 0:
            subseq.append(n)
        elif subseq[-1] + 1 == n or subseq[-1] == n:
            subseq.append(n)
        elif subseq[-1] + 1 < n:
            subseq = [n]

    print("Impossible!")