python - 将列表与其他列表的元素按保留顺序进行比较

Question

我有一些单词列表。一些列表彼此共享常用词。我正在尝试查看每个列表，还有哪些其他列表具有相同顺序的常用词。例如，假设这些是我的列表(为简单起见，使用字母而不是单词/字符串):

list1 = [a,b,c,d]
list2 = [f,n,a,b,g]
list3 = [x,f,g,z]
list4 = [y,a,b,f,g,k]

在这里我们可以看到 list1 中的 [a,b] 也以该顺序出现在 list2 和 list4 中。我们还可以看到 list3 中的 [f,g] 出现在 list4 中。所以我们将这些列表相互映射如下:

list1: list2, list4 #(contains [a,b])
list2: list1, list4 #(contains [a,b])
list3: list4 #(contains [f,g])
list4: list1, list2, list3 #(contains [a,b] and [f,g])

您可以忽略评论，因为那是为了解释，它只是相互映射的列表名称。请注意，即使 list2 具有元素“f”和“g”，但由于它们的顺序不在 [f,g]，因此它不会映射到 list3 或 list4。

我已经使用 set.intersection() 编写了一个函数来获取我所有列表中的常用词，但它不关心顺序。因此，我似乎无法弄清楚要使用哪种数据结构或算法才能以这种方式将列表相互映射。

我正在尝试以下操作，其中 wordlists 是我的列表列表，每个列表都包含各自的单词量:

filelist = {}
for i in range(0, len(wordlists)):
    current_wordlist = wordlists[i]
    for j, j_word in enumerate(current_wordlist):
        if current_wordlist[j] == j_word:
            if j_word not in filelist:
                filelist[i] = {j}
            else:
                filelist[i].append(j)

但它没有正确映射，因为它没有映射到正确的列表编号。我将不胜感激一些反馈或一些其他的检查技巧。

我怎样才能实现这一目标？

Answer 1

首先，我将创建一个帮助程序，为每个列表创建一组连续的项目:

def create_successive_items(lst, n):
    return set(zip(*[lst[i:] for i in range(n)]))

然后您可以简单地检查基于这些集合的所有列表的交集:

list1 = ['a','b','c','d']
list2 = ['f','n','a','b','g']
list3 = ['x','f','g','z']
list4 = ['y','a','b','f','g','k']


lists = [list1, list2, list3, list4]

# First look for two elements
i = 2

all_found = []

while True:
    # find all "i" successive items in each list as sets
    succ = [create_successive_items(lst, i) for lst in lists]
    founds = []
    # Check for matches in different lists
    for list_number1, successives1 in enumerate(succ, 1):
        # one only needs to check all remaining other lists so slice the first ones away
        for list_number2, successives2 in enumerate(succ[list_number1:], list_number1+1):
            # Find matches in the sets with intersection
            inters = successives1.intersection(successives2)
            # Print and save them
            if inters:
                founds.append((inters, list_number1, list_number2))
                print(list_number1, list_number2, inters)

    # If we found matches look for "i+1" successive items that match in the lists
    # One could also discard lists that didn't have "i" matches, but that makes it
    # much more complicated.
    if founds:
        i += 1
        all_found.append(founds)
    # no new found, just end it
    else:  
        break

这会打印匹配项:

1 2 {('a', 'b')}
1 4 {('a', 'b')}
2 4 {('a', 'b')}
3 4 {('f', 'g')}

并且这些在 all_founds 中也可用，并且可以使用和/或转换，即转换为 dict:

matches = {}
for match, idx1, idx2 in all_found[0]:
    matches.setdefault(idx1, []).append(idx2)
    matches.setdefault(idx2, []).append(idx1)

>>> matches
{1: [2, 4], 
 2: [1, 4], 
 3: [4], 
 4: [1, 2, 3]}