Skip to main content
 首页 » 编程设计

python之在 Python 中生成特定的位序列

2025年05月04日12kenshinobiy

我有一个数字列表,代表一行中 1 的数量,我有一个整数代表整个序列的长度。因此,例如,如果我得到列表 [1, 2, 3] 和长度 8,那么唯一可能的位序列是 10110111。但是如果长度是 9,我应该得到 010110111、100110111、101100111 和 101101110。我想知道是否有一种简单的 pythonic 方法可以做到这一点。我现在的方法是

def genSeq(seq, length): 
    strSeq = [str(i) for i in seq] 
    strRep = strSeq + ["x" for i in xrange(length-sum(seq))] 
 
    perm = list(set(permutations(strRep))) 
    legalSeq = [seq for seq in perm if isLegal(seq) and [char for char in seq if char.isdigit()] == strSeq] 
    return [''.join(["1"*int(i) if i.isdigit() else "0" for i in seq]) for seq in legalSeq] 
 
 
def isLegal(seq): 
    for i in xrange(len(seq)-1): 
        if seq[i].isdigit() and seq[i+1].isdigit(): return False 
    return True 
 
print genSeq([1, 2, 3], 9) 

请您参考如下方法:

我的做法如下:

  1. 通过适当的算术算出结果序列中将出现多少个零。我们将此值称为 n,并将输入列表的长度称为 k。

  2. 现在,假设我们为给定的结果序列在一行中写出 n 个零。要创建一个有效的序列,我们需要选择 k 个位置来插入适当数量的 1,我们有 n + 1 个选择 -在任何两个数字之间,或者在开头 或 结尾。所以我们可以使用 itertools.combinations 给我们所有可能的位置组,要求它选择 k 从 0 到 n 的值,包括在内。

  3. 给定一个位置的组合,按升序排列,我们可以算出在第一组 1(组合中的第一个值)、第二组(组合中的第一个值)之前出现了多少个 0组合中的前两个值)等。在迭代时,我们需要在零组(第一个和/或最后一个可能为空)和一组零之间交替;所以一般来说,零组比零组多一组——但我们可以通过在末尾添加一个“虚拟”零长度组来清理它。我们还需要从 ones-positions 中获得“重叠”差异;还好there's a trick for this .

这部分放在一起时很棘手;首先,我会为它编写一个辅助函数:

def make_sequence(one_positions, zero_count, one_group_sizes): 
    zero_group_sizes = [ 
        end - begin 
        for begin, end in zip((0,) + one_positions, one_positions + (zero_count,)) 
    ] 
    return ''.join( 
        '0' * z + '1' * o 
        for z, o in zip(zero_group_sizes, one_group_sizes + [0]) 
    ) 

现在我们可以回到对所有可能序列的迭代:

def generate_sequences(one_group_sizes, length): 
    zero_count = length - sum(one_group_sizes) 
    for one_positions in itertools.combinations( 
        range(zero_count + 1), len(one_group_sizes) 
    ): 
        yield make_sequence(one_positions, zero_count, one_group_sizes) 

我们当然可以将其折叠回一个函数中,但也许您会同意我的看法,最好将如此聪明的东西保留在更易于管理的部分中:)

这比我想要的更脆弱 - one_positions 和 one_group_sizes 序列需要“填充”才能使事情正常进行,这反过来又需要假设它们的类型. one_positions 将是一个元组,因为这是 itertools.combinations 产生的结果,但我已经硬编码了用户提供的 one_group_sizes 的假设是一个列表。有很多解决方法,但我现在有点累了:)

无论如何,测试:

>>> list(generate_sequences([1,2,3], 9)) 
['101101110', '101100111', '100110111', '010110111'] 
 
>>> list(generate_sequences([1,1,1], 9)) 
['101010000', '101001000', '101000100', '101000010', '101000001', '100101000', ' 
100100100', '100100010', '100100001', '100010100', '100010010', '100010001', '10 
0001010', '100001001', '100000101', '010101000', '010100100', '010100010', '0101 
00001', '010010100', '010010010', '010010001', '010001010', '010001001', '010000 
101', '001010100', '001010010', '001010001', '001001010', '001001001', '00100010 
1', '000101010', '000101001', '000100101', '000010101']