서브 세트 빈도를 찾기 위해 숫자 계산

Question

N 세트 (동일한 크기, 한 세트 내에서 중복 없음)에서 자주 발생하는 숫자의 조합을 찾으려고합니다. 예를 들어

는 :

{3, 5, 2, 4, 6, 11} 
{3, 7, 2, 11, 5, 14} 
{8, 2, 1, 11, 14, 6} 
{9, 1, 12, 8, 17, 4} 
{4, 10, 16, 5, 14, 3} 

나는 세트에서 개별 숫자의 발행 수를 찾는 알고리즘을 계산 번호를 사용했다.

public static int[] Counting (int []A, int m) 
{ 
    int n = A.Length; 
    int[] count = new int[m+1]; 
    Array.Clear(count, 0, m+1); 
    for (int k = 0; k < n; k++) 
     count[A[k]] += 1; 
    return count; 
} 

하위 집합과 동일한 작업을 수행하는 알고리즘이 있습니까? 위의 예에서 {2, 11}, {3,2,11}, {11,14}가 더 자주 함께 발생합니다. 출력은 서브 세트의 카운트를 가져야합니다. 즉, 위 예의 경우 {2, 11} 주파수는 입니다.

Answer 1

이 기능을 수행 하시겠습니까?

Func<IEnumerable<int>, IEnumerable<IEnumerable<int>>> getAllSubsets = null; 
getAllSubsets = xs => 
    (xs == null || !xs.Any()) 
     ? Enumerable.Empty<IEnumerable<int>>() 
     : xs.Skip(1).Any() 
      ? getAllSubsets(xs.Skip(1)) 
       .SelectMany(ys => new [] { ys, xs.Take(1).Concat(ys) }) 
      : new [] { Enumerable.Empty<int>(), xs.Take(1) }; 

var source = new int[][] 
{ 
    new [] {3, 5, 2, 4, 6, 11}, 
    new [] {3, 7, 2, 11, 5, 14}, 
    new [] {8, 2, 1, 11, 14, 6}, 
    new [] {9, 1, 12, 8, 17, 4}, 
    new [] {4, 10, 16, 5, 14, 3}, 
}; 

var subsets = source.Select(x => getAllSubsets(x).Select(y => new { key = String.Join(",", y), values = y.ToArray() }).ToArray()).ToArray(); 

var keys = subsets.SelectMany(x => x.Select(y => y.key)).Distinct().ToArray(); 

var query = 
    from key in keys 
    let count = subsets.Where(x => x.Select(y => y.key).Contains(key)).Count() 
    where count > 1 
    orderby count descending 
    select new { key, count, }; 

나는이 결과를 얻을 :

5의 첫 번째 결과는 각 세트에 포함 된 빈 세트입니다.