How to find a group of integers(N) amongst records, that contains 6 integers

Question

I'm having problem with finding most common group of integers among int[x,6] array, where x <= 100000. Numbers are between 0 and 50. eg input. (N = 2)

14 24 44 36 37 45 - here
01 02 06 24 33 44
10 17 34 40 44 45 - here
12 13 28 31 37 47
01 06 07 09 40 45
01 05 06 19 35 44
13 19 20 26 31 47
44 20 30 31 45 46 - here
02 04 14 23 30 34
27 30 41 42 44 49
03 06 15 27 37 48

output:

44, 45 (3) // appeared 3 times

Attached code I tried. Now I understand it doesn't work, but I was asked me to post it. I'm not just asking help without even trying.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;

namespace TotoLotek
{
    class Program
    {

        static void Main(string[] args)
        {
            StreamReader czytnik = new StreamReader("dane_wejsciowe.txt");
            List<int[]> lista = new List<int[]>();

            string linia = "";
            while ((linia = czytnik.ReadLine()) != null)
            {
                string[] numery = linia.Split(' ');
                int[] tablica_intow = new int[6];
                for (int i = 0; i < 6; i++)
                {
                    tablica_intow[i] = int.Parse(numery[i]);
                }
                lista.Add(tablica_intow);
            }

            czytnik.Close();

            int[] tablica = new int [50];

            for (int i = 0; i< lista.Count(); i++)
            {
                for (int j = 0; j < 6; j++)
                {
                    tablica[lista[i][j]]++;
                }
            }

            int maks = tablica[0];
            int maks_indeks = 0;
            for (int i = 0; i < 50; i++)
            {
                if (tablica[i] > maks)
                {
                    maks = tablica[i];
                    maks_indeks = i;
                }
            }

            Console.Write("{0}({1}) ", maks_indeks, maks);

            List<int[]> lista2 = new List<int[]>();

            for (int i = 0; i < lista.Count(); i++)
            {
                for (int j = 0; j < 6; j++)
                {
                    if (lista[i][j] == maks_indeks)
                        lista2.Add(lista[i]);
                    break;
                }
            }

            int[] tablica2 = new int[50];
            for (int i = 0; i < lista2.Count(); i++)
            {
                for (int j = 0; j < 6; j++)
                {
                    tablica2[lista2[i][j]]++;
                }
            }


            int maks2 = tablica2[0];
            int maks_indeks2 = 0;
            for (int i = 0; i < 50; i++)
            {
                if (tablica2[i] > maks2 && i != maks_indeks)
                {
                    maks2 = tablica2[i];
                    maks_indeks2 = i;
                }
            }


            Console.Write("{0}({1}) ", maks_indeks2, maks2);

            int xdddd = 2;
        }
    }
}

Answer 1

Loop through the rows and all the numbers in each row. Pair each number with all higher numbers and count all combinations. When you are done you just sort the result on the count and take the highest:

int[][] numbers = {
  new int[] { 14, 24, 44, 36, 37, 45 },
  new int[] { 01, 02, 06, 24, 33, 44 },
  new int[] { 10, 17, 34, 40, 44, 45 },
  new int[] { 12, 13, 28, 31, 37, 47 },
  new int[] { 01, 06, 07, 09, 40, 45 },
  new int[] { 01, 05, 06, 19, 35, 44 },
  new int[] { 13, 19, 20, 26, 31, 47 },
  new int[] { 44, 20, 30, 31, 45, 46 },
  new int[] { 02, 04, 14, 23, 30, 34 },
  new int[] { 27, 30, 41, 42, 44, 49 },
  new int[] { 03, 06, 15, 27, 37, 48 }
};

var count = new Dictionary<KeyValuePair<int, int>, int>();
foreach (int[] row in numbers) {
  foreach (int i in row) {
    foreach (int n in row.Where(n => n > i)) {
      KeyValuePair<int, int> key = new KeyValuePair<int, int>(i, n);
      if (count.ContainsKey(key)) {
        count[key]++;
      } else {
        count.Add(key, 1);
      }
    }
  }
}

KeyValuePair<KeyValuePair<int, int>, int> most =
  count.ToList().OrderByDescending(n => n.Value).First();

Console.WriteLine("{0}, {1} ({2})", most.Key.Key, most.Key.Value, most.Value);

Output:

44, 45 (3)

Answer 2

NOW I HAVE IMPROVED MY ALGORITHM. NOW IT WORKS!!!!

class Program
{
    static void Main(string[] args)
    {
        List<int[]> list = new List<int[]>();
        list.Add(new int[] { 10, 20, 30, 40, 50});
        list.Add(new int[] { 10, 20, 30, 40, 50 });
        list.Add(new int[] { 10, 20, 30, 40, 50 });
        list.Add(new int[] { 10, 20, 30, 40, 50 });
        list.Add(new int[] { 10, 20, 30, 40, 50 });

        // The N
        int amountInCombination = 4;

        Dictionary<String, int> dictionary = new Dictionary<String, int>();
        foreach (int[] ints in list)
        {
            List<String> names = GetAllElemntCombinationsInRow(amountInCombination, ints);
            int count = 0;
            foreach (string name in names)
            {
                if (dictionary.TryGetValue(name, out count))
                {
                    dictionary[name]++;
                }
                else
                {
                    dictionary.Add(name, 1);
                }
            }

        }
        KeyValuePair<String, int> result = dictionary.OrderByDescending(e => e.Value).First();

        Console.WriteLine("{0} ({1})", result.Key, result.Value);
        //dictionary.OrderByDescending(e=>e.Value).First()
    }

    public static List<String> GetAllElemntCombinationsInRow(int amountInCombination, int[] row)
    {
        List<String> result = new List<string>();
        List<String> tempUniq = new List<string>();
        for (int i = 0; i < row.Count(); i++)
        {
            tempUniq = new List<string>();
            if (amountInCombination != 1)
            {
                int[] temp = new int[row.Length-i-1];
                Array.Copy(row,i+1, temp,0,row.Length-i-1);
                tempUniq = GetAllElemntCombinationsInRow(amountInCombination - 1, temp);
            }
            else
            {
                result.Add(row[i].ToString());
            }
            if (tempUniq.Count != 0)
            {
                for (int j = 0; j < tempUniq.Count; j++)
                {
                    result.Add(row[i].ToString() + "," + tempUniq[j]);
                }
            }
        }
        return result;
    }
}

Answer 3

var input = new int[][]
{
    new [] {14, 24, 44, 36, 37, 45},//- here
    new [] {01, 02, 06, 24, 33, 44},
    new [] {10, 17, 34, 40, 44, 45},//- here
    new [] {12, 13, 28, 31, 37, 47},
    new [] {01, 06, 07, 09, 40, 45},
    new [] {01, 05, 06, 19, 35, 44},
    new [] {13, 19, 20, 26, 31, 47},
    new [] {44, 20, 30, 31, 45, 46},//- here
    new [] {02, 04, 14, 23, 30, 34},
    new [] {27, 30, 41, 42, 44, 49},
    new [] {03, 06, 15, 27, 37, 48},
};

The implementation:

var matches = new List<int[]>();
for (int i = 0; i < input.Length; i++)
{
    // Compare with all the next arrays
    // "j = i + 1", to do not compare twice
    for (int j = i + 1; j < input.Length; j++)
    {
        var match = input[i].Intersect(input[j]).ToArray();
        if (match.Length > 1) // The smallest group contains 2 elements 
        {
            matches.Add(match);
        }
    }
}

var comparer = new ArrayComparer<int>();
var mostCommon = matches
    .GroupBy(p => p, comparer)

    // Sort by frequency
    .OrderByDescending(p => p.Count())

    // Sort by the group's length
    .ThenByDescending(p => p.Key.Count())
    .FirstOrDefault();

The ArrayComparer<T> class:

public class ArrayComparer<T> : EqualityComparer<IEnumerable<T>>
{
    public override bool Equals(IEnumerable<T> x, IEnumerable<T> y)
    {
        return x != null && y != null &&
            (x == y || Enumerable.SequenceEqual(x,y));
    }

    public override int GetHashCode(IEnumerable<T> obj)
    {
        return obj.Sum(p => p.GetHashCode() + p.GetHashCode());
    }
}

Display the result:

if (mostCommon != null)
{
    Console.WriteLine("Most common: {{{0}}} ({1})",
        string.Join(", ", mostCommon.Key), mostCommon.Count());
}
else
{
    Console.WriteLine("Not found.");
}

Output:

Most common: {44, 45} (3)

Answer 4

Make an array of size X (possible numbers, so 50). Iterate through all numbers and increment each one to the appropriate index. Grab the highest N numbers out of the array (you know which number it is based on the index.

A more elegant solution might be required for large numbers of X.

            int[][] numbers =
            {
                new[] {14, 24, 44, 36, 37, 45},
                new[] {01, 02, 06, 24, 33, 44},
                new[] {10, 17, 34, 40, 44, 45},
                new[] {12, 13, 28, 31, 37, 47},
                new[] {01, 06, 07, 09, 40, 45},
                new[] {01, 05, 06, 19, 35, 44},
                new[] {13, 19, 20, 26, 31, 47},
                new[] {44, 20, 30, 31, 45, 46},
                new[] {02, 04, 14, 23, 30, 34},
                new[] {27, 30, 41, 42, 44, 49},
                new[] {03, 06, 15, 27, 37, 48}
            };

        int[] counts = new int[50];

        foreach (var rowOfNumbers in numbers)
        {
            foreach (var number in rowOfNumbers)
            {
                counts[number]++;
            }
        }

        int[] top = new[] {0, 0};

        for (int i = 0; i < counts.Length; i++)
        {
            if (counts[i] > top[0])
                top[0] = i;

            else if (counts[i] > top[1])
                top[1] = i;
        }

Could easily refactor to a method to be more robust.