python - 确定0和1的python列表中序列类型的最有效方法？

Question

假设我们有随机大小的 python 列表，其值以 0 和 1 的随机序列排列。确定序列是否是最多 3 个位置的以下类型之一并为“序列类型”返回以下字符串之一的好方法是什么？：

• 0 (只有 0) [0,0,0]

• 1 (只有 1) [1,1]

• 01（以 0 开头然后遇到 1 x 之后的位数）[0,0,0,0,1]

• 10（10 的倒数）[1,0,0,0,0]

• 010（以0开头，在0之后遇到1 x位数，然后在1之后遇到0 x位数）[0,0,0,1,0,1,1,0]

• 101（与上述相反）[1,1,1,1,1,0,0,1,0,1,0,1]

我可以想到简单的案例，然后是一种天真的方法，您可以在其中嵌套循环并保留一个计数器，但是有没有更优雅的方法来做到这一点？

def sequence_type(sequence):
    
if 0 not in sequence:
    return '1'

elif 1 not in sequence:
    return '0'

else:
    if sequence[0] == 0:
        # loop through for sequence type 0xx
    elif sequence[0] == 1:
        # loop through for sequence type 1xx

编辑：在检查类型时，我们不关心序列末尾的内容，而是查看前 3 个“唯一”数字时的序列。

例如： [0,0,1,0,1,0] 是 010 类型，因为：

• 0 是第一个数字，它是我们的“起点”
• 然后我们向右走，看到它是另一个 0 所以它不是唯一的，跳过并再次向右移动
• 然后遇到一个 1，我们记录这个，因为它是唯一的，再次向右移动
• 看到数字是 0 并且是唯一的（我们现在数了 3 位），所以模式是 010。

标签： pythonlistalgorithmsequence

Answer 1

您可以通过位进行返回序列类型。类型的第一位总是等于第一位。如果在第一个位置之后找到反位，则该类型将有两位或三位数字，第二位是第一位的倒数。如果该位出现在倒数的位置之后，则序列类型为 3 位（再次交替）：

def seqType(seq):
    bit = seq[0]                 # seq type starts with first bit
    try: p = seq.index(1-bit)    # search position of inverse bit
    except: return str(bit)      # not found --> single digit type
    if bit not in seq[p+1:]:     # search for initial bit after inverse
        return f"{bit}{1-bit}"   # not found --> two digit type
    return f"{bit}{1-bit}{bit}"  # --> 3 digit type

    

输出：

tests = ([0,0,0],[1,1],[0,0,0,0,1],[1,0,0,0,0],
         [0,0,0,1,0,1,1,0],[1,1,1,1,1,0,0,1,0,1,0,1])    
for seq in tests:
    print(seq,seqType(seq))
    
[0, 0, 0] 0
[1, 1] 1
[0, 0, 0, 0, 1] 01
[1, 0, 0, 0, 0] 10
[0, 0, 0, 1, 0, 1, 1, 0] 010
[1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1] 101 

如果您想要更高级的方法，可以使用 zip 函数计算类型以压缩相同的连续位。压缩序列的前 3 位将对应于序列类型：

def seqType(seq):
    return "".join(str(a) for a,b in zip(seq,seq[1:]+[2]) if a!=b)[:3])

或者，如果您喜欢递归解决方案：

def seqType(seq):
    if len(seq) == 1:  return str(seq[0])
    if seq[0]==seq[1]: return seqType(seq[1:])
    return str(seq[0]) + seqType(seq[1:])[:2]