2

我试图获得一个序列的 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]不连续。

我在做一些代码打高尔夫球时遇到了这个问题，所以为了利益起见，看到一个简单的解决方案和/或一个有效的解决方案也很好，对我现有的代码不太感兴趣。

4

5 回答 5

7 
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。

where 的 casel > 1是前一个 case 的扩展。我们使用random.sample()拾取位置，但保持offset移动连续结果：通过这种方式，我们确保它们是不重叠的范围 --- 即它们至少l从彼此的距离开始，而不是 1。

于 2013-09-05T16:50:23.360 回答
1

许多解决方案都可以解决这个问题，但如果序列要严格随机，则必须小心。例如，从 0 之间选择一个随机数开始len(seq)-n*l并说第一个序列将从那里开始，然后递归地工作是错误的。

这个问题相当于随机选择n+1整数，使得它们的总和等于len(seq)-l*n。（这些数字将是您的序列之间的“差距”。）要解决它，您可以看到这个问题。

于 2013-09-05T16:26:34.213 回答
1

这在 Python 3.3.2 中对我有用。它应该向后兼容 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))

上面的代码总是会打印 [[1, 2], [3, 4], [5, 6]]

于 2013-09-05T17:03:25.047 回答
0

首先，我认为您需要澄清术语random的含义。

当您对子序列本身设置特定限制时，如何生成真正随机的子序列列表？

据我所知，在这种情况下，任何人都可以实现的最佳“随机性”是生成满足您标准的所有子序列列表，并以随机方式从池中选择您需要的任意数量。

现在，根据我几年前参加的算法课的经验，您的问题似乎是一个典型示例，可以使用贪婪算法对您实际问的内容做出这些大（但可能？）假设来解决首先：

  • 随机的实际意思不是应该随机生成子序列列表（这有点矛盾，就像我之前所说的那样），而是任何可以产生的解决方案都与其他解决方案一样有效（例如6 种解决方案中的任何一种都对输入 [1,2,3,4,5,6] 有效，您不在乎哪一种）
  • 重申上述内容，您只需要可以生成的任何一种可能的解决方案，并且您需要一种可以输出这些有效答案之一的算法。

假设上面是一个贪心算法，它在线性时间内生成一个可能的子序列列表（不包括排序，即 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!")

该算法的要点如下：

  • 您的要求之一是不能有任何重叠，这最终意味着您只需要处理唯一编号和唯一编号。所以我使用 set() 操作来消除所有重复项。然后我整理一下。
  • 休息很简单。我只是遍历排序列表并贪婪地形成子序列。
  • 如果算法不能形成足够数量的子序列，则打印“不可能！”

希望这就是你要找的。

编辑：出于某种原因，我错误地认为子序列中不能有重复值，这个允许它。

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!")
于 2013-09-05T18:33:41.550 回答
0

如果你递归地这样做，它会简单得多。取第一部分（所以其余部分适合）：

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

然后递归剩下要做的事情：

rand_parts(seq - begining _to_end_of_part_you_grabbed, n - 1, l)
于 2013-09-05T16:26:19.730 回答