I'm looking for the algorithm to convert a lotto ticket number to an integer value an back again.

Let's say the lotto number can be between 1 and 45 and a tickets contains 6 unique numbers. This means there are a maximum of 8145060 unique lotto tickets.

eg:

01-02-03-04-05-06 = 1
01-02-03-04-05-07 = 2
        .
        .
        .
39-41-42-43-44-45 = 8145059
40-41-42-43-44-45 = 8145060

I'd like to have a function (C# preferable but any language will do) which converts between a lotto ticket and an integer and back again. At the moment I use the quick and dirty method of pre-calculating everything, which needs a lot of memory.

CodePudding user response：

there seem to be actually 45^6 distinct numbers, a simple way is to treat the ticket number as a base-45 number and convert it to base 10:

 static ulong toDec(string input){
     ulong output = 0;
     var lst = input.Split('-').ToList();
     for (int ix =0; ix< lst.Count; ix  )
     {
        output = output   ( (ulong.Parse(lst[ix])-1) *(ulong) Math.Pow(45 , 5-ix));
     }
     return output;
 }

examples:

• 01-01-01-01-01-01 => 0
• 01-01-01-01-01-02 => 1
• 01-01-01-01-02-01 => 45
• 45-45-45-45-45-45 => 8303765624

CodePudding user response：

For enumerating integer combinations, you need to use the combinatorial number system. Here's a basic implementation in C#:

using System;
using System.Numerics;
using System.Collections.Generic;

public class CombinatorialNumberSystem
{
    // Helper functions for calculating values of (n choose k).
    // These are not optimally coded!
    // ----------------------------------------------------------------------
    protected static BigInteger factorial(int n) {
        BigInteger f = 1;
        while (n > 1) f *= n--;
        return f;
    }
    
    protected static int binomial(int n, int k) {
        if (k > n) return 0;
        return (int)(factorial(n) / (factorial(k) * factorial(n-k)));
    }
    
    // In the combinatorial number system, a combination {c_1, c_2, ..., c_k}
    // corresponds to the integer value obtained by adding (c_1 choose 1)  
    // (c_2 choose 2)   ...   (c_k choose k)
    // NOTE: combination values are assumed to start from zero, so
    // a combination like {1, 2, 3, 4, 5} will give a non-zero result
    // ----------------------------------------------------------------------
    public static int combination_2_index(int[] combo) {
        int ix = 0, i = 1;
        Array.Sort(combo);
        foreach (int c in combo) {
            if (c > 0) ix  = binomial(c, i);
            i  ;
        }
        return ix;
    }
    
    // The reverse of this process is a bit fiddly. See Wikipedia for an
    // explanation: https://en.wikipedia.org/wiki/Combinatorial_number_system
    // ----------------------------------------------------------------------
    public static int[] index_2_combination(int ix, int k) {
        List<int> combo_list = new List<int>();
        while (k >= 1) {
            int n = k - 1;
            if (ix == 0) {
                combo_list.Add(n);
                k--;
                continue;
            }
            int b = 0;
            while (true) {
                // (Using a linear search here, but a binary search with
                // precomputed binomial values would be faster)
                int b0 = b;
                b = binomial(n, k);
                if (b > ix || ix == 0) {
                    ix -= b0;
                    combo_list.Add(n-1);
                    break;
                }
                n  ;
            }
            k--;
        }
        int[] combo = combo_list.ToArray();
        Array.Sort(combo);
        return combo;
    }
}

The calculations are simpler if you work with combinations of integers that start from zero, so for example:

00-01-02-03-04-05 = 0
00-01-02-03-04-06 = 1
        .
        .
        .
38-40-41-42-43-44 = 8145058
39-40-41-42-43-44 = 8145059

You can play around with this code at ideone if you like.