计算列表中每个元素出现的连续子列表的数量

Question

我需要计算原始列表中每个元素出现在该列表的连续子列表中的次数.例如,

对于集合[A,B,C]我应该得到连续的子列表[A,B,C],[A,B],[B,C],[A],[B],[C]这给我跟随数字:
A使用3次
B使用4次
C使用3次

列表[A,B,C,D]应为[A,B,C,D],[A,B,C],[B,C,D],[A,B],[B, C],[C,D],[A],[B],[C],[D]和数字:
A使用4次
B使用6次
C使用6次
D使用4次

我有代码生成所有连续的子列表,并允许我进行计算.但是对于大输入它变得太慢,同时我相信我只是错过了一些允许我进行计算而不会生成所有连续子列表的东西.我将非常感谢任何帮助:谷歌关键字,代码等

    public static IEnumerable<int[]> Permutate(int[] a)
    {
        for (int i = 1; i < a.Length; i++)
        {
            for (int j = 0; j < a.Length-i; j++)
            {
                yield return a.Skip(j).Take(i).ToArray();
            }
        }
    }

Answer 1

考虑列表中元素之间的点数,以及列表的第一个元素和开头之间的点数,以及列表的最后一个元素和结尾.

每个子列表由这组点的起点和终点组成.因此,包含特定元素的子列表的数量是该元素左侧和右侧的点数的乘积.

在你的例子[A,B,C,D]中,我将使用'|' 为了点.| A | B | C | d |

对于'B',左边有2个,右边有3个,所以我们有2*3 = 6.

通常,如果原始列表有n个元素,并且您正在考虑元素k,零索引,因此第一个元素是k = 0,依此类推,那么有n + 1个点.其中,k + 1位于元素k的左侧,n + 1 - (k + 1)= nk位于右侧.这意味着存在包含元素k的(k + 1)*(nk)子列表.