Sam-Elie Sam-Elie - 5 months ago 56
Vb.net Question

C# / VB .Net Performance tuning, Generate all possible Lottery combinations

Trying to generate all possible draws(combinations) for a lottery of unique 6 out of 42.

Actually looking for the most efficient way to do this (so that the actual generation does not take days).

Aside from the processing HOG (which is to be expected) .. i'm running into a memory limitation issue .. where my machine of 12GB ram cant hold 10% of the amount on number, let alone all combos.

So i decided to look into a Database alternative.
But with that i have the problem of duplicates (since i do not have the whole list in memory to check for existence).

I tried a lot of code versions but all are resource consuming.

Currently looking for alternatives that actually work :)

Here's my latest code sample that employs a database for later record processing and filtering and duplication removal:

public List<Draw> getDrawsContaining(List<int> initialBalls)
{
if (initialBalls == null)
initialBalls = new List<int>();

if (initialBalls.Count >= 6)
return new List<Draw> { new Draw(initialBalls) };

List<Draw> toReturn = new List<Draw>();
for (int i = 1; i <= 42; i++)
{
if (initialBalls.IndexOf(i) != -1)
continue;

initialBalls.Add(i);
toReturn.AddRange(getDrawsContaining(initialBalls));
initialBalls.Remove(i);
}

return toReturn;//.Distinct(dc).ToList();
}


AND say in the Page_Load i fire this :

try
{
using (SqlConnection connection = new SqlConnection(sqlConnectionString))
{
connection.Open();
String query = "TRUNCATE TABLE Draws";

SqlCommand command = new SqlCommand(query, connection);
//command.Parameters.Add("@id", "abc");

command.ExecuteNonQuery();
connection.Close();
}

DataTable dt = new DataTable("Draws");
dt.Columns.Add("Ball1");
dt.Columns.Add("Ball2");
dt.Columns.Add("Ball3");
dt.Columns.Add("Ball4");
dt.Columns.Add("Ball5");
dt.Columns.Add("Ball6");

for (int j = 1, k = 1; j <= 42 && k <= 42; )
{
List<Draw> drawsPart = getDrawsContaining(new List<int> { j, k });

if (drawsPart.Count > 0)
{
foreach (Draw d in drawsPart)
{
d.Balls.OrderBy(c => c);

DataRow dr = dt.NewRow();
dr["Ball1"] = d.Balls[0];
dr["Ball2"] = d.Balls[1];
dr["Ball3"] = d.Balls[2];
dr["Ball4"] = d.Balls[3];
dr["Ball5"] = d.Balls[4];
dr["Ball6"] = d.Balls[5];

dt.Rows.Add(dr);
}

DataTable tmp = dt.Copy();
dt.Rows.Clear();

AsyncDBSave AsyncDBSaveInstance = new AsyncDBSave(tmp, AsyncDBSaveDispose);
Thread t = new Thread(new ThreadStart(AsyncDBSaveInstance.commit));
t.Start();
}

k++;
if (k == 43) { j++; k = 1; }
}
}
catch (Exception ex)
{
var v = ex.Message;
throw;
}

Answer

Here we go... all very fast and efficient:

using System;
using System.Diagnostics;

static class Program
{
    static void Main(string[] args)
    {

        byte[] results = new byte[6 * 5245786];
        byte[] current = new byte[6];
        int offset = 0;
        var watch = Stopwatch.StartNew();
        Populate(results, ref offset, current, 0);
        watch.Stop();
        Console.WriteLine("Time to generate: {0}ms", watch.ElapsedMilliseconds);
        Console.WriteLine("Data size: {0}MiB",
            (results.Length * sizeof(byte)) / (1024 * 1024));
        Console.WriteLine("All generated; press any key to show them");
        Console.ReadKey();
        for (int i = 0; i < 5245786; i++)
        {
            Console.WriteLine(Format(results, i));
        }
    }
    static string Format(byte[] results, int index)
    {
        int offset = 6 * index;
        return results[offset++] + "," + results[offset++] + "," +
           results[offset++] + "," + results[offset++] + "," +
           results[offset++] + "," + results[offset++];
    }

    static void Populate(byte[] results, ref int offset, byte[] current, int level)
    {
        // pick a new candidate; note since we're doing C not P, assume ascending order
        int last = level == 0 ? 0 : current[level - 1];
        for (byte i = (byte)(last + 1); i <= 42; i++)
        {
            current[level] = i;
            if (level == 5)
            {
                // write the results
                results[offset++] = current[0];
                results[offset++] = current[1];
                results[offset++] = current[2];
                results[offset++] = current[3];
                results[offset++] = current[4];
                results[offset++] = current[5];
            }
            else
            {
                // dive down
                Populate(results, ref offset, current, level + 1);
            }
        }
    }
}