将列表与其他列表进行比较，以保留顺序的方式比较元素。

Question

将列表与其他列表进行比较，以保留顺序的方式比较元素。

3

我有几个单词列表，其中一些列表共享相同的单词。我试图找出每个列表中，哪个其他列表具有相同顺序的共同单词。例如，假设这些是我的列表（为简单起见，使用字母而不是单词/字符串）：

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

在这里，我们可以看到列表1中的[a,b]以相同的顺序出现在列表2和列表4中。我们还可以看到列表3中的[f,g]在列表4中出现。因此，我们将按照以下方式将这些列表映射到彼此：

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)

但由于它没有映射到正确的列表编号，因此它无法正确映射。我会感激您的反馈或其他检查方法的技巧。

我该如何实现这一点？

- FlameDra

2个回答

0

你可以使用元组集合来增加一些乐趣。由于元组是可哈希的，你只需要编写几个辅助函数，就可以从给定列表中获取所有连续有序子列表，并使用集合交集进行比较。

from itertools import permutations
def radix(rg, n_len):
    """
    Returns all ordered sublists of length n_len from
    the list rg
    :type rg: list[char]
    :type n_len: int
    """
    for x in range(0, len(rg) - n_len + 1):
        yield tuple(rg[x:x + n_len])

def all_radixes(rg):
    """
    Returns all ordered sublists of length 2 or longer
    from the given list
    :type rg: list[char]
    """
    for x in range(2, len(rg) + 1):
        for result in radix(rg, x):
            yield result

def compare_lists(rg1, rg2):
    s1 = set(all_radixes(rg1))
    s2 = set(all_radixes(rg2))
    return s1 & s2

list1 = 'a,b,c,d'.split(',')
list2 = 'f,n,a,b,g'.split(',')
list3 = 'x,f,g,z'.split(',')
list4 = 'y,a,b,f,g,k'.split(',')

all_lists = [ list1, list2, list3, list4 ]
for z in permutations(all_lists, 2):
    print 'Intersection of %s and %s: %s' % (z[0], z[1], compare_lists(z[0], z[1]),)

- 2ps

1

顺便提一下：set(x for x in all_radixes(rg1)) 和 set(all_radixes(rg1)) 是相同的。 - MSeifert

没错，谢谢。 - 2ps

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- MSeifert · Accepted Answer

首先，我会创建一个助手来为每个列表创建一组连续的项目：

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]}