c# - 如何从多个数组中查找搜索元素的序列

Question

我有大量的列表，每个列表都可能有一些重复的序列，我需要找到序列(不同数组中重复的元素超过 1 个)

在下面的示例中，数组 1 和数组 2 的元素序列为 010,002,007，数组 2 和数组 3 的元素序列为 011,345,547,800。

array1: 090,010,002,007,310,104,048,610,720    
array2: 456,010,002,007,087,011,345,547,800    
array3: 004,089,870,011,345,547,800,001,002

执行此操作的最佳方法是什么，我知道我们可以在普通 C# 中执行此操作，但它需要大量循环和编程。是否有任何算法来识别在任何数组中顺序常见的超过 1 个元素>

Answer 1

首先，您应该尝试将数组映射为图形我们将定义以下类

    private class Transition
    {
        public int ArrayNum { get; set; }
        public int? NextNum { get; set; }
    }

给定我们的数组

var arrays = new[]
{
      new[] {090, 010, 002, 007, 310, 104, 048, 610, 720},
      new[] {456, 010, 002, 007, 087, 011, 345, 547, 800},
      new[] {004, 089, 870, 011, 345, 547, 800, 001, 002}
};

我们将按如下方式映射转换:

var transitions = new Dictionary<int, List<Transition>>();

for (var i = 0; i < arrays.Length; i++)
{
    for (var j = 0; j < arrays[i].Length; j++)
    {
        var num = arrays[i][j];
        var transition = new Transition { ArrayNum = i, NextNum = j < arrays[i].Length - 1 ? arrays[i][j + 1] : (int?)null };
        if (!transitions.ContainsKey(num))
        {
            transitions.Add(num, new List<Transition> {transition});
        }
        else
        {
            transitions[num].Add(transition);
        }

    }
}

transitions = transitions.OrderBy(x => x.Key).ToDictionary(x => x.Key, x => x.Value);

在有了映射之后，我们将只访问每个数组一次，找到它的相关序列:

private class Sequence
{
    public int FirstArray { get; set; }
    public int SecondArray { get; set; }
    public IList<int> Nums { get; set; }
}



var sequences = new List<Sequence>();
for (var i = 0; i < arrays.Length-1; i++)
{
    List<Sequence> relevantSequences = null;
    for (var j = 0; j < arrays[i].Length - 1; j++)
    {
        var num = arrays[i][j];
        var nextNum = arrays[i][j+1];
        var flows = transitions[num].Where(x => x.NextNum == nextNum && x.ArrayNum > i).ToList();
        if (!flows.Any())
        {
            if (relevantSequences != null)
            {
                sequences.AddRange(relevantSequences);
                relevantSequences = null;
            }
        }
        else 
        {
            if (relevantSequences == null)
            {
                relevantSequences = flows.Select(x => new Sequence { FirstArray = i, SecondArray = x.ArrayNum, Nums = new List<int> {num, nextNum} }).ToList();
            }
            else
            {
                foreach (var flow in flows)
                {
                    var sequence = relevantSequences.SingleOrDefault(x => x.SecondArray == flow.ArrayNum);

                    if (sequence != null)
                    {
                        sequence.Nums.Add(nextNum);
                    }
                    else
                    {
                        relevantSequences.Add(new Sequence { FirstArray = i, SecondArray = flow.ArrayNum, Nums = new List<int> { num, nextNum } });
                    }
                }
            }
        }

    }

    if (relevantSequences != null)
        sequences.AddRange(relevantSequences);
}

希望你会发现它有用。