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

Question

I had a problem finding the most common group of integers from an int [x, 6] array, where x <= 100000. The numbers are between 0 and 50. for example, an 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 that this did not work, but I was asked to send it. I do not just ask for 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

NOW I 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 2

Scroll through the lines and all the numbers in each line. Combine all numbers with all higher numbers and count all combinations. When you are done, you simply sort the result by the score and take the highest value:

 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 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}, }; 

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 length .ThenByDescending(p => p.Key.Count()) .FirstOrDefault(); 

Class ArrayComparer<T> :

 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 result:

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

Output:

Most often: {44, 45} (3)

Answer 4

Make an array of size X (possible numbers, so 50). Sort through all numbers and increase each of them to the corresponding index. Take the highest N numbers from the array (you know which number it is based on the index.

For large X numbers, a more elegant solution may be required.

  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; } 

Easy to reorganize the method more reliable.

Answer 5

  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 a comparison.

  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()); } }