6

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;
        }
    }
}
6
  • 2
    Can you post the code you tried? Feb 15, 2013 at 11:13
  • 1
    Are the numbers all between 1 and 50?
    – leppie
    Feb 15, 2013 at 11:18
  • Yes, they are. I've forgotten to mention that.
    – Patryk
    Feb 15, 2013 at 11:19
  • 2
    So, what's not working exactly? Do you get incorrect answer or no answer at all? I think it might help if you remove irrelevant code blocks (like usings and reading the input) and make variable names to be more english-like. I'm fine with something East-European, but most of the people here more used to words table, not tablica
    – J0HN
    Feb 15, 2013 at 11:20
  • 1
    Look to my improved algorithm. Now its works with any amount of N you provide.
    – Maris
    Feb 16, 2013 at 8:56

5 Answers 5

4

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)
2
  • @Patryk: The principle would be the same for any valye of N. You can make a recursive function that creates all combinations of the length N from an array, and use that for the third loop. Make a class to use as key in the dictionary, that contains an array and implements IEquatable<T>.
    – Guffa
    Feb 15, 2013 at 11:49
  • Why the downvote? If you don't explain what you think is wrong, it can't improve the answer.
    – Guffa
    Feb 15, 2013 at 12:07
1

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;
    }
}
1
  • I have improved it. You can test it, it works on any amount of amountInCombination(N)
    – Maris
    Feb 16, 2013 at 8:44
1
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)

1

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.

2
  • That would give the most common number and the second most common number, not the most common combination of two numbers.
    – Guffa
    Feb 15, 2013 at 14:21
  • Woops, missed that part, sorry!
    – Greg B
    Feb 15, 2013 at 14:28
0
  var pairs = numbers.Select(x =>
                                  {
                                    List<KeyValuePair<int, IList<int>>> pairList = new List<KeyValuePair<int, IList<int>>>();
                                    for (int i = 0; i <= 4; i++)
                                    {
                                      for (int j = i + 1; j <= 5; j++)
                                      {
                                        //Get the pair
                                        var pair = new List<int> { x.Skip(i).First(), x.Skip(j).First() };
                                        //Pair should be unique, so make the ID the sum
                                        pairList.Add(new KeyValuePair<int, IList<int>>(pair.Sum(), pair));
                                      }
                                    }
                                    return pairList;
                                  }).SelectMany(x => x.Select(y => y.Value)).GroupBy(x => x, new PairComparer()).ToList();
  int iHighest = pairs.Max(p => p.Count());
  var highestPairs = pairs.Where(pair => pair.Count() == iHighest);

Here is the comparer.

 public class PairComparer : IEqualityComparer<IList<int>>
{

  public bool Equals(IList<int> x, IList<int> y)
  {
    return x.All(i => y.Contains(i));
  }

  public int GetHashCode(IList<int> obj)
  {
    return obj.Sum(x => x.GetHashCode());
  }
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.