使用唯一元素创建所有可能的子序列

Question

我有一系列形式的元素：

A111 T112 I113 A114 S115 I116 D117 F118 K119 R120 E121 T122 C123 V124 V125 V126 T112

约束每个元素只出现一次。在上面的序列中，T112 出现了两次。所以我需要创建满足约束的所有可能的子序列，即：

T112 I113 A114 S115 I116

I116 K119 R120 E121 T122 C123 V124 V125 V126 T112

在更复杂的情况下，我有以下必须满足相同约束的序列：

A111 T112 I113 A114 T112 S115 I116 D117 I116 K119 R120 E121 T122 C123 V124 V125 V126

这次T112也是I116出现了两次。在这种情况下，我需要以下子序列：

A111 T112 I113 A114

I113 A114 T112 S115 I116 D117

D117 I116 K119 R120 E121 T122 C123 V124 V125 V126

当然一个元素可能出现2次以上。有没有不用遗传算法解决这个问题的有效方法？

Answer 1

代码：

list  = ["A111", "T112", "I113", "A114", "T112", "S115", "I116", "D117", "I116", "K119", "R120", "E121", "T122", "C123", "V124", "V125", "V126"]

subsequence = []
for item in list:
    if item in subsequence:
        print subsequence
        index = subsequence.index(item)+1
        subsequence = subsequence[index:]
    subsequence.append(item)
print subsequence

将打印：

['A111', 'T112', 'I113', 'A114']
['I113', 'A114', 'T112', 'S115', 'I116', 'D117']
['D117', 'I116', 'K119', 'R120', 'E121', 'T122', 'C123', 'V124', 'V125', 'V126']

Answer 2

您可以维护一个运行集合，以跟踪重复的字符串：

def partitions(s):

    lst = s.split()
    flags = set()
    for l in lst:
        if l in flags:
            yield list(flags)
            flags.clear()
        flags.add(l)
    yield list(flags)

>>> s = "A111 T112 I113 A114 T112 S115 I116 D117 I116 K119 R120 E121 T122 C123 V124 V125 V126"
>>> x = partitions(s)
>>> print list(x)
[['A111', 'I113', 'T112', 'A114'], ['D117', 'S115', 'T112', 'I116'], ['R120', 'T122', 'E121', 'V125', 'V124', 'V126', 'C123', 'K119', 'I116']]

使用唯一元素创建所有可能的子序列

Create all possible subsequence with unique elements

python

algorithm

sequence