如何在字符串的列表/数组中找到类似的模式

最简单的编码方式是构建一个字典,然后循环遍历每个数组中的每个项。对于每个项目,请执行以下操作:

检查该项是否在字典中,如果是,则将列表添加到数组中。 如果该项不在词典中,请添加它和列表。

正如你所说,这是非生产代码性能并不重要,所以这种方法应该可以很好地工作。

这是一个解决方案,使用 SuffixTree 用于定位子序列的模块:

#!/usr/bin/env python
from SuffixTree  import SubstringDict
from collections import defaultdict
from itertools   import groupby
from operator    import itemgetter
import sys

def main(stdout=sys.stdout):
    """
    >>> import StringIO
    >>> s = StringIO.StringIO()
    >>> main(stdout=s)
    >>> print s.getvalue()
    [['Mi', 'Fa']] In Arrays (1, 2)
    [['So', 'La', 'Ti']] In Arrays (1, 3)
    [['Jim', 'Bob', 'So']] In Arrays (2, 3)
    [['So']] In Arrays (1, 2, 3)
    <BLANKLINE>
    """
    # array of arrays of strings
    arr = [
        ["Do", "Re", "Mi", "Fa", "So", "La", "Ti",],
        ["Mi", "Fa", "Jim", "Bob", "So",],
        ["Jim", "Bob", "So", "La", "Ti",],
    ]

####    # 28 seconds  (27 seconds without lesser substrs inspection (see below))
####    N, M = 100, 100
####    import random
####    arr = [[random.randrange(100) for _ in range(M)] for _ in range(N)]

    # convert to ASCII alphabet (for SubstringDict)
    letter2item = {}
    item2letter = {}
    c = 1
    for item in (i for a in arr for i in a):
        if item not in item2letter:
            c += 1
            if c == 128:
                raise ValueError("too many unique items; "
                                 "use a less restrictive alphabet for SuffixTree")
            letter = chr(c)
            letter2item[letter] = item
            item2letter[item] = letter
    arr_ascii = [''.join(item2letter[item] for item in a) for a in arr]

    # populate substring dict (based on SuffixTree)
    substring_dict = SubstringDict()
    for i, s in enumerate(arr_ascii):
        substring_dict[s] = i+1

    # enumerate all substrings, save those that occur more than once
    substr2indices = {}
    indices2substr = defaultdict(list)
    for str_ in arr_ascii:
        for start in range(len(str_)):
            for size in reversed(range(1, len(str_) - start + 1)):
                substr = str_[start:start + size]
                if substr not in substr2indices:
                    indices = substring_dict[substr] # O(n) SuffixTree
                    if len(indices) > 1:
                        substr2indices[substr] = indices
                        indices2substr[tuple(indices)].append(substr)
####                        # inspect all lesser substrs
####                        # it could diminish size of indices2substr[ind] list
####                        # but it has no effect for input 100x100x100 (see above)
####                        for i in reversed(range(len(substr))):
####                            s = substr[:i]
####                            if s in substr2indices: continue
####                            ind = substring_dict[s]
####                            if len(ind) > len(indices):
####                                substr2indices[s] = ind
####                                indices2substr[tuple(ind)].append(s)
####                                indices = ind
####                            else:
####                                assert set(ind) == set(indices), (ind, indices)
####                                substr2indices[s] = None
####                        break # all sizes inspected, move to next `start`

    for indices, substrs in indices2substr.iteritems():
        # remove substrs that are substrs of other substrs
        substrs = sorted(substrs, key=len) # sort by size
        substrs = [p for i, p in enumerate(substrs)
                   if not any(p in q  for q in substrs[i+1:])]
        # convert letters to items and print
        items = [map(letter2item.get, substr) for substr in substrs]
        print >>stdout, "%s In Arrays %s" % (items, indices)

if __name__=="__main__":
    # test
    import doctest; doctest.testmod()
    # measure performance
    import timeit
    t = timeit.Timer(stmt='main(stdout=s)',
                     setup='from __main__ import main; from cStringIO import StringIO as S; s = S()')
    N = 1000
    milliseconds = min(t.repeat(repeat=3, number=N))
    print("%.3g milliseconds" % (1e3*milliseconds/N))

处理100个列表,每个列表包含100个项目,大约需要30秒。 SubstringDict 在上面的代码中,可以通过以下方式模拟 grep -F -f .

旧解决方案:

在Python中(将其保存到“group_patterns.py”文件中):

#!/usr/bin/env python
from collections import defaultdict
from itertools   import groupby

def issubseq(p, q):
    """Return whether `p` is a subsequence of `q`."""
    return any(p == q[i:i + len(p)] for i in range(len(q) - len(p) + 1))

arr = (("Do", "Re", "Mi", "Fa", "So", "La", "Ti",),
       ("Mi", "Fa", "Jim", "Bob", "So",),
       ("Jim", "Bob", "So", "La", "Ti",))

# store all patterns that occure at least twice
d = defaultdict(list) # a map: pattern -> indexes of arrays it's within
for i, a in enumerate(arr[:-1]):
    for j, q in enumerate(arr[i+1:]): 
        for k in range(len(a)):
            for size in range(1, len(a)+1-k):
                p = a[k:k + size] # a pattern
                if issubseq(p, q): # `p` occures at least twice
                    d[p] += [i+1, i+2+j]

# group patterns by arrays they are within
inarrays = lambda pair: sorted(set(pair[1]))
for key, group in groupby(sorted(d.iteritems(), key=inarrays), key=inarrays):
    patterns = sorted((pair[0] for pair in group), key=len) # sort by size
    # remove patterns that are subsequences of other patterns
    patterns = [p for i, p in enumerate(patterns)
                if not any(issubseq(p, q)  for q in patterns[i+1:])]
    print "%s In Arrays %s" % (patterns, key)

以下命令:

$ python group_patterns.py

打印:

[('Mi', 'Fa')] In Arrays [1, 2]
[('So',)] In Arrays [1, 2, 3]
[('So', 'La', 'Ti')] In Arrays [1, 3]
[('Jim', 'Bob', 'So')] In Arrays [2, 3]

这个解决方案效率极低。

正如其他人提到的,你想要的功能是Intersect。如果你正在使用。NET 3.0考虑使用LINQ的Intersect函数。

看见 the following post for more information

考虑使用LinqPAD进行实验。

www.linqpad.net

我用了大约10分钟的Perl就破解了下面的程序。它并不完美,它使用了一个全局变量,它只是打印出程序在每个列表中看到的每个元素的计数,但它很好地近似了你想要做的事情,而且非常容易编码。

您真的希望每个数组共享所有元素子集的所有组合吗?如果你愿意,你可以更智能地枚举所有元素,但如果你只想在每个数组中至少存在一次所有元素,你可以在下面的输出中使用Unix命令“grep-v 0”,这将显示所有数组共有的所有元素的交集。你的问题缺少一点细节,所以我无法完美地实现解决你问题的东西。

如果你做的数据分析比编程多,脚本对于从这样的文本数据中提问非常有用。如果你不知道如何用这样的脚本语言编写代码,我会花一两个月的时间阅读如何用Perl、Python或Ruby编写代码。它们对于像这样的一次性黑客攻击来说非常棒,尤其是在你真的不知道自己想要什么的情况下。编写这样一个程序的时间和大脑成本非常低,因此(如果你很快)你可以多次编写和重写,同时仍然探索问题的定义。

#!/usr/bin/perl -w

use strict;

my @Array1 = ( "Do", "Re", "Mi", "Fa", "So", "La", "Ti");
my @Array2 = ( "Mi", "Fa", "Jim", "Bob", "So" );
my @Array3 = ( "Jim", "Bob", "So", "La", "Ti" );

my %counts;
sub count_array {
    my $array = shift;
    my $name  = shift;
    foreach my $e (@$array) {
        $counts{$e}{$name}++;
    }
}

count_array( \@Array1, "Array1" );
count_array( \@Array2, "Array2" );
count_array( \@Array3, "Array3" );

my @names = qw/ Array1 Array2 Array3 /;
print join ' ', ('element',@names);
print "\n";

my @unique_names = keys %counts;
foreach my $unique_name (@unique_names) {
    my @counts = map {
        if ( exists $counts{$unique_name}{$_} ) {
            $counts{$unique_name}{$_};
        } else {
            0;
        }
    }
    @names;

    print join ' ', ($unique_name,@counts);
    print "\n";
}

程序的输出为:

element Array1 Array2 Array3
Ti 1 0 1
La 1 0 1
So 1 1 1
Mi 1 1 0
Fa 1 1 0
Do 1 0 0
Bob 0 1 1
Jim 0 1 1
Re 1 0 0

看起来您想对数据集使用交集函数。交集会选择两个(或多个)集合中共同的元素。

这种观点的问题在于,集合不能包含多个元素,即每个集合不能包含一个以上的Jim,而且它也不能将一行中的几个元素识别为一种模式,但是你可以修改一个比较函数来进一步查看。

可能有像interview这样的函数在包上工作(有点像集合,但容忍相同的元素)。

这些函数在大多数语言中应该是标准的,或者很容易自己编写。

我相信还有一种更优雅的方式,但是。..

既然这不是生产代码,为什么不直接破解它,将每个数组转换为分隔字符串,然后在每个字符串中搜索您想要的模式呢?也就是

        private void button1_Click(object sender, EventArgs e)
        {

            string[] array1 = { "do", "re", "mi", "fa", "so" };
            string[] array2 = { "mi", "fa", "jim", "bob", "so" };
            string[] pattern1 = { "mi", "fa" };
            MessageBox.Show(FindPatternInArray(array1, pattern1).ToString());
            MessageBox.Show(FindPatternInArray(array2, pattern1).ToString());

        }

        private bool FindPatternInArray(string[] AArray, string[] APattern)
        {
            return string.Join("~", AArray).IndexOf(string.Join("~", APattern)) >= 0;
        }

首先,从计算每个项目开始。 你制作一个临时列表:“Do”=1,“Mi”=2,“So”=3,以此类推。 您可以从临时列表中删除所有匹配=1的值(例如:“Do”)。 临时列表包含非唯一项的列表(将其保存在某处)。

现在,您尝试从临时列表中的一个列表和原始列表中的后续列表中创建两个列表。 “所以”+“拉”=2,“鲍勃”+“所以”=2,以此类推。 删除具有=1的值。 你有至少出现两次的情侣列表(保存在某个地方)。

现在,尝试从临时列表中选取几个项目,并从原始列表中选取以下项目,从而制作一个包含3个项目的列表。 (“Mi”,“Fa”)+“So”=1,(“Mi”,“法”)+”Jim“=1,(”So“,”La“)+”Ti“=2 删除具有=1的值。 您有至少出现两次的3个项目的列表(保存)。

然后你继续这样做,直到临时列表为空。

最后,您将所有已保存的列表合并。

这个算法不是最优的(我认为我们可以用合适的数据结构做得更好),但它很容易实现:)

假设密码由英语字母表中的九个字符(26个字符)组成。如果每个可能的密码都可以在毫秒内测试,那么测试所有可能的密码需要多长时间?