c# - 计算列表的每个元素出现在多少个连续的子列表中

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次

我有代码可以生成所有连续的子列表并允许我进行计算。但是对于大输入来说，它变得太慢了，同时我相信我只是错过了一些让我在不生成所有连续子列表的情况下进行计算的东西。 如果有任何帮助，我将不胜感激:google 关键字、代码等

    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) = n-k 在右侧。这意味着有 (k+1) * (n-k) 个包含元素 k 的子列表。