我在 C# 中选择 k 元素子集来处理大量数据的算法

Question

我正在编写从一组（n 个元素）中选择一个（k 个元素）子集的算法。

我已经成功完成了任务。它适用于小数字。我已经针对 n=6、k=3 和 n=10、k=5 进行了测试。

问题现在开始了，当我需要将它用于大量数据时。有时我需要用它来假设 n = 96000000 和 k = 3000。为了简单地测试一下，让我们关注 n = 786432 和 k = 1000 的示例。那么就有 461946653375201 这样的可能性。作为我函数的第三个参数，有等级编号，因此是特定唯一子集的编号。让我们尝试一些随机数，例如 3264832 工作正常（给了我不同数字的子集），但是对于 4619466533201 一个数字（在子集中）重复了几次，这是错误的。它也必须根据唯一数字设置为子集！

问题是让它正常工作，问题是什么？即使是ulong，数字也太大了？

如果您有任何问题，请随时提出。

这是我的代码：

    public static ulong BinomialCoefficient(ulong N, ulong K)
    {
        ulong result = 1;
        for (ulong i = 1; i <= K; i++)
        {
            result *= N - (K - i);
            result /= i;
        }
        return result;
    }

    public static ulong[] ChooseSubsetByRank(ulong sizeOfSet, ulong sizeOfSubset, ulong rank)
    {
        ulong[] resultingSubset = new ulong[sizeOfSubset];
        ulong x = sizeOfSet;

        for (ulong i = sizeOfSubset; i > 0; i--)
        {
            while (BinomialCoefficient(x, i) > rank)
                x--;

            resultingSubset[i - 1] = x + 1;
            rank = BinomialCoefficient(x + 1, i) - rank - 1;
        }

        return resultingSubset;
    }

下面是运行代码。要测试它，您可以更改下面一行的第三个参数。

        ulong[] arrayTest = Logic.ChooseSubsetByRank(786432, 1000, 4619466533201);
        string test = "";
        for (int i = 0; i < arrayTest.Length; i++)
            test = test + arrayTest[i].ToString() + " ";
        System.Windows.MessageBox.Show(" " + test);

Answer 1

没有希望。你可以不.

正如消费者所说：使用 BigInteger。

您的计算是错误的（如果您使用 ulong 计算，这可能是非常有限的）。

C786432,1000实际上是：

6033573926325594551531868873570215053708823770889227136141180206574788891075585715726697576999866930083212017993760483485644855730323214507786127283118515758667219335061769573572969492263411636472559059114372691043787225874459276616360823293108500929182830806831624098080982165637186175635880811026388564912224747148201420203796293941118006753515861022396665706095036252893420240334110487119413634294555065166398219767688578556791918697815341165100213662715943043737412038535358818942960435634721564898425752479874494445989953267768476995289375942620219089503401832797819758809124329657724691573254079810257990856068363592549560111914326820802223343980843357174727643299789438961341403866942005159819587812937265119974334351031505150775547311257835039161258554849609865661574816771511161168033768782419369241858323336341530982042093999410402417064838718686064312965836862249598770142918659708106482935266574067985412321680292750817019104479650736141502332606724302400412461373311881584020963297 2794378358196663554908049701159834366456284606886794168266806213781328348574528162329821482385328376003983787105147582765294106003242717970905028184448254277535132559848285154724627067149006971942611058817681241693380726079426752198996302468222989501173235443990234536035285178293907719151030361739617559551594228064830763707620685389028035522447949863627287945733060256838660384707937035139356539877447022771370208428621165443004816885196257081158432992757187475969618994919104808971489554069629852693413416304609102875169845346324129407516295130181449479789529329442515854627540043929532722688192177515735759253193321904357440627639900898857321576843424508731803077355490839846475822106981218845137857625788270790774993212246282313530834510551844831827777990316328578108082692861126794573845884319864598633944405784007650945570596286272078875101984275179802066617940558121982633916035520228831180474159722542115921437061278159854866926008706079766235619984343730912442953567847089972356254227774152 0930405646492434115187826250358725619838414271804985504262151914903852317756982823164169039317386590288325447735634073093990554315454074675984209374418472370601938487368346797466773120641197786354810448874133279719288778900575977771615390142369251114230933333304414440429584259637999336326361951407727784740167350888869130319056495693724090460571833340347787573512591305360525021867100967412977356432595931193055600673518590755769122079371874551391109604335857942828885231240186270734717407915723357297223158422168351192854813077120772997147626243694716780586248972224779194439324980417722708188935257224764710176772827714920684441771238017080976044247130698350597778451742562179412286183903132956207422425247625669295018747365569868831493234430432506807649141973141385164105895714924582776136353646355063603077900970311721684350003193075513673577102216248178453150037839339058155869537009962748882565124888447384419571925862145122998752031754294356629734069802846681893733597679234338278813451874062 3993664131802576690485505420542865842569675333314900726976825951448445467650748963731221593412649796639395685018463040431779020656159571608044184646177251839940386267422657877801967082672251079906237183824765375906939480520508656199566649638083679757430680818796170362008227564859519761936618260089868694546582873807181452115865272320

我在 C# 中选择 k 元素子集来处理大量数据的算法

My algorithm for choosing k element subset to handle huge number in C#

c#

algorithm

subset

combinatorics

discrete-mathematics