c# - 我在 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

没有希望。你可以不。

正如 spender 所说:使用 BigInteger。

您的计算是错误的(如果您使用 ulong 进行计算，这可能是非常有限的)。

C786432,1000 在现实中:

6033573926325594551531868873570215053708823770889227136141180206574788891075585715726697576999866930083212017993760483485644855730323214507786127283118515758667219335061769573572969492263411636472559059114372691043787225874459276616360823293108500929182830806831624098080982165637186​​175635880811026388564912224747148201420203796293941118006753515861022396665706095036252893420240334110487119413634294555065166398219767688578556791918697815341165100213662715943043737412038535358818942960435634721564898425752479874494445989953267768476995289375942620219089503401832797819758809124329657724691573254079810257990856068363592549560111914326820802223343980843357174727643299789438961341403866942005159819587812937265119974334351031505150775547311257835039161258554849609865661574816771511161168033768782419369241858323336341530982042093999410402417064838718686064312965836862249598770142918659708106482935266574067985412321680292750817019104479650736141502332606724302400412461373311881584020963297279 4378358196663554908049701159834366456284606886794168266806213781328348574528162329821482385328376003983787105147582765294106003242717970905028184448254277535132559848285154724627067149006971942611058817681241693380726079426752198996302468222989501173235443990234536035285178293907719151030361739617559551594228064830763707620685389028035522447949863627287945733060256838660384707937035139356539877447022771370208428621165443004816885196257081158432992757187475969618994919104808971489554069629852693413416304609102875169845346324129407516295130181449479789529329442515854627540043929532722688192177515735759253193321904357440627639900898857321576843424508731803077355490839846475822106981218845137857625788270790774993212246282313530834510551844831827777990316328578108082692861126794573845884319864598633944405784007650945570596286272078875101984275179802066617940558121982633916035520228831180474159722542115921437061278159854866926008706079766235619984343730912442953567847089972356254227774152093 040564649243411518782625035872561983841427180498550426215191490385231775698282316416903931738659028832544773563407309399055431545407467598420937441847237060193848736834679746677312064119778635481044887413327971928877890057597777161539014236925111423093333330441444042958425963799933632636195140772778474016735088886913031905649569372409046057183334034778757351259130536052502186710096741297735643259593119305560067351859075576​​9122079371874551391109604335857942828885231240186270734717407915723357297223158422168351192854813077120772997147626243694716780586248972224779194439324980417722708188935257224764710176772827714920684441771238017080976044247130698350597778451742562179412286183903132956207422425247625669295018747365569868831493234430432506807649141973141385164105895714924582776136353646355063603077900970311721684350003193075513673577102216248178453150037839339058155869537009962748882565124888447384419571925862145122998752031754294356629734069802846681893733597679234338278813451874062399 36641318025766904855054205428658425696753333149007269768259514484454676507489637312215934126497966393956850184630404317790206561595716080441846461772518399403862674226578778019670826722510799062371838247653759069394805205​​08656199566649638083679757430680818796170362008227564859519761936618260089868694546582873807181452115865272320