combinatorics - 查找彩票组合的排名

Question

我需要找到彩票组合的等级/索引并能够逆向过程(根据等级找到彩票组合)。

考虑一个彩票游戏，5 个球从 1 到 45，1 个强力球从 1 到 20。不允许重复，顺序无关紧要。组合数为:

(45 * 44 * 43 * 42 * 41 / 5!) * 20 = 24,435,180

第一个组合(索引 0)是:

1, 2, 3, 4, 5, 1

最后的组合(索引 24,435,179)是:

41, 42, 43, 44, 45, 20

如何在不详尽枚举所有组合的情况下将组合转换为其索引，反之亦然？

我遇到了 this MSDN 文章，其中展示了如何获取给定索引的组合。但是，我不知道如何从组合中获取索引。我试过:

Choose(c1,k) + Choose(c2,k-1) + Choose(c3,k-2) + Choose(c4,k-3) ...

其中ci是有序组合集合中位置i的数，k是集合的大小。由于组合的索引取决于元素的范围，因此这是行不通的。此外，我不确定它是否适用于集合中不同大小的元素(例如主池的范围是 1-45，强力球的范围是 1-20)

Answer 1

我想通了。我创建了一个新的组合类，基于 MSDN example ，它可以将组合转换为索引，反之亦然。为每个号码池检索单独的索引。然后组合所有索引以表示具有不同大小的元素的组合。

还创建了一个 Pool 类来表示池的设置(元素范围、大小等)。池类:

public class Pool {
    public int From { get; set; }
    public int To { get; set; }
    public int Size { get; set; }
    public int Numbers { get { return (To - From + 1); } }
    public Pool(int From, int To, int Size) {
        this.From = From;
        this.To = To;
        this.Size = Size ;
    }
}

组合类:

class Combination {

    public Pool[] Pools { get; set; }
    public long[][] Data { get; set; } //First index represents pool index, second represents the numbers

    public Combination(Pool[] Pools, long[][] Data) {
        this.Pools = Pools;
        this.Data = Data;
        if (Data.GetLength(0) != Pools.Length) {
            throw (new ArgumentException("Invalid data length"));
        }

        for (int i = 0; i < Data.GetLength(0); i++) {
            if (Data[i].Length != Pools[i].Size) {
                throw (new ArgumentException("Invalid data length"));
            }
        }
    }

    public static Combination FromIndex(long Index, Pool[] Pools) {
        long[][] elements = new long[Pools.Length][];

        long[] c = new long[Pools.Length - 1];
        long cumulative = 1;
        for (int i = 0; i < Pools.Length - 1; i++) {
            c[i] = Combination.Choose(Pools[i].Numbers, Pools[i].Size);
            checked {
                cumulative *= c[i];
            }
        }

        for (int i = Pools.Length - 1; i >= 1; i--) {
            long ind = Index / cumulative;
            Index -= ind * cumulative;

            cumulative /= c[i - 1];
            elements[i] = Combination.FromIndex(ind, Pools[i]);
        }
        elements[0] = Combination.FromIndex(Index, Pools[0]);


        return (new Combination(Pools, elements));
    }

    public static long[] FromIndex(long Index, Pool Pool) {
        long[] ans = new long[Pool.Size];
        long a = (long)Pool.Numbers;
        long b = (long)Pool.Size;
        long x = GetDual((long)Pool.Numbers, (long)Pool.Size, Index);

        for (int k = 0; k < Pool.Size; k++) {
            ans[k] = LargestV(a, b, x);
            x -= Choose(ans[k], b);
            a = ans[k];
            b--;
        }

        for (int k = 0; k < Pool.Size; k++) {
            ans[k] = ((long)Pool.Numbers - 1) - ans[k];
        }


        //Transform to relative
        for (int i = 0; i < ans.Length; i++) {
            ans[i] += Pool.From;
        }

        return (ans);
    }

    private static long GetDual(long To, long Size, long m) {
        return (Choose(To, Size) - 1) - m;
    }

    public static long Choose(long To, long Size) {
        if (To < 0 || Size < 0)
            throw new Exception("Invalid negative parameter in Choose()");
        if (To < Size)
            return 0;  // special case
        if (To == Size)
            return 1;

        long delta, iMax;

        if (Size < To - Size) {
            delta = To - Size;
            iMax = Size;
        } else {
            delta = Size;
            iMax = To - Size;
        }

        long ans = delta + 1;

        for (long i = 2; i <= iMax; ++i) {
            checked {
                ans = (ans * (delta + i)) / i;
            }
        }

        return ans;
    }

    private static long LargestV(long a, long b, long x) {
        long v = a - 1;

        while (Choose(v, b) > x)
            --v;

        return v;
    }

    public long ToIndex() {
        long Index = 0;
        long cumulative = 1;

        for (int i = 0; i < Pools.Length; i++) {
            checked {
                Index += ToIndex(i) * cumulative;
                cumulative *= Combination.Choose(Pools[i].Numbers, Pools[i].Size);
            }
        }

        return (Index);

    }

    public long ToIndex(int PoolIndex) {
        long ind = 0;
        for (int i = 0; i < Pools[PoolIndex].Size; i++) {
            long d = (Pools[PoolIndex].Numbers - 1) - (Data[PoolIndex][i] - Pools[PoolIndex].From);
            ind += Choose(d, Pools[PoolIndex].Size - i);
        }

        ind = GetDual(Pools[PoolIndex].Numbers, Pools[PoolIndex].Size, ind);
        return (ind);
    }

    public override string ToString() {
        string s = "{ ";

        for (int i = 0; i < Data.Length; ++i) {
            for (int k = 0; k < Data[i].Length; k++) {
                s += Data[i][k] + " ";
            }
            if (i != Data.Length - 1) {
                s += "| ";
            }
        }
        s += "}";
        return s;
    }
}

要查看实际效果:

        //Create pools
        Pool[] pools = new Pool[2];
        pools[0] = new Pool(1, 45, 5);
        pools[1] = new Pool(1, 20, 1);

        //Create a combination
        long[][] data = new long[][] { new long[] { 41, 42, 43, 44, 45 }, new long[] { 20 } };
        Combination combination = new Combination(pools, data);

        //Get index from combination:
        long index = combination.ToIndex(); 
        Console.WriteLine("Index: " + index);

        //Get combination from index:
        Combination combFromIndex = Combination.FromIndex(index, pools);
        Console.WriteLine("Combination: " + combFromIndex);

输出:

Index: 24435179
Combination: { 41 42 43 44 45 | 20 }