一次将乐透票号转换为整数值并返回的算法

Question

我正在寻找算法，以将乐透票证号码转换为整数值，再一次返回。

假设乐透号在1到45之间，一张票包含6个唯一的号码。这意味着最多有8145060张彩票。

例：

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

我希望有一个函数(C#更好，但任何语言都可以)，它可以在乐透票和整数之间进行转换，然后再返回。目前，我使用快速和肮脏的方法预先计算一切，这需要大量的内存。

Answer 1

要枚举整数组合，需要使用组合数系统。下面是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;
    }
}

如果使用从零开始的整数组合，则计算更简单，因此，例如：

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

如果你愿意的话，你可以在ideone玩这个代码。

Answer 2

实际上似乎有45^6个不同的数字，一个简单的方法是将票号作为一个基数-45号，并将其转换为基数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;
 }

例子：

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