Calculate how many contiguous sublists each element of a list appears in

Question

I need to calculate how many times each element from an original list appears in contiguous sublists of that list. For example,

for set [A, B, C] I should get contiguous sublists [A, B, C], [A, B], [B,C], [A], [B], [C] and this give me follow numbers:
A used 3 times
B used 4 times
C used 3 times

for the list [A, B, C, D] it should be [A, B, C, D], [A, B, C], [B, C, D], [A,B], [B,C], [C,D], [A], [B], [C], [D] and numbers:
A used 4 times
B used 6 times
C used 6 times
D used 4 times

I have code which generate all contiguous sublists and which allow me to make my calculation. But for large input it become too slow and at the same time I believe that I just missed something that allow me to make my calculation without generating all contiguous sublists. I will be very appreciated for any help: google keywords, code, etc

    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

Consider the number of points between elements in your list, as well as between the first element and the beginning of the list, and the last element and the end of the list.

Each sublist consists of a starting point and and ending point from this set of points. Thus the number of sublists containing a specific element is the product of the number of points to the left of and to the right of that element.

In your example [A,B,C,D], I'll use '|' for the points. |A|B|C|D|

For 'B', there are 2 to the left and 3 to the right, so we have 2*3=6.

In general, if the original list has n elements, and you're considering element k, zero-indexed so the first element is k=0 and so on, then there are n+1 points. Of these, k+1 are to the left of element k, and n+1 - (k+1) = n-k are to the right. This means there are (k+1) * (n-k) sublists that contain element k.