计算巨大的排列 - 计算元素并获得第 n 个元素

Question

我将这个库用于组合学： https://github.com/eoincampbell/combinatorics/

我需要的是找到第 n 个排列并计算相当大的集合（最多约 30 个元素）的元素，但我什至在开始之前就停了下来，请查看此代码：

int[] testSet = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21};

var permutation = new Permutations<int>(testSet);
var test = permutation.Count;

一切都很好，直到 20 个元素大集合，一旦我添加第 21 个，排列就停止工作，例如。这是 permutation.Count returns:

-4249290049419214848

这与正确的数字相去甚远。

我假设这一切都归结为我使用了多少数字——溢出了图书馆使用的 ints/longs。这就是为什么，我要征求意见 - 有图书馆吗？方法？或者一种相当快速的实现方式来让组合数学在双整数上工作？

谢谢！

Answer 1

获取可能的排列数。

排列数由 nPr 或 n over r

定义

           n!     
P(n,r) = -------- 
         (n - r)!

其中：

n = 对象数
r = 结果集的大小

在您的示例中，您想要获取给定列表的所有排列。在这种情况下 n = r.

public static BigInteger CalcCount(BigInteger n, BigInteger r) 
{
    BigInteger result = n.Factorial() / (n - r).Factorial();
    return result;
}

public static class BigIntExtensions 
{
    public static BigInteger Factorial(this BigInteger integer) 
    {
        if(integer < 1) return new BigInteger(1);

        BigInteger result = integer;
        for (BigInteger i = 1; i < integer; i++)
        {
            result = result * i;
        }

        return result;
    }
}

得到第n个排列

这取决于您如何 create/enumerate 排列。通常要生成任何排列，您不需要知道所有以前的排列。换句话说，创建排列可以是一个纯函数，允许您直接创建 nTh 排列，而不需要创建所有可能的排列。

然而，这取决于所使用的算法。但是仅在需要时创建排列可能会快得多（与预先创建所有可能的排列相反 -> 性能和非常大的内存）。

这里有一个关于如何创建排列而不需要计算之前的排列的精彩讨论：。

Answer 2

评论太长了，但想跟进@Iqon 上面的解决方案。下面是一个检索 n^th lexicographical 排列的算法：

public static int[] nthPerm(BigInteger myIndex, int n, int r, BigInteger total)
{
    int j = 0, n1 = n;
    BigInteger temp, index1 = myIndex;

    temp = total ;
    List<int> indexList = new List<int>();

    for (int k = 0; k < n; k++) {
           indexList.Add(k);
    }

    int[] res = new int[r];

    for (int k = 0; k < r; k++, n1--) {
        temp /= n1;
        j = (int) (index1 / temp);
        res[k] = indexList[j];
        index1 -= (temp *  j);
        indexList.RemoveAt(j);
    }

    return res;
}

这是一个测试用例和使用@Iqon 提供的代码调用 nthPerm 的结果。

public static void Main()
{
    int[] testSet = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21};
    BigInteger numPerms, n, r;
    n = testSet.Length;
    r = testSet.Length;
    numPerms = CalcCount(n, r);
    Console.WriteLine(numPerms);

    BigInteger testIndex = new BigInteger(1234567890987654321);
    int[] myNthIndex = nthPerm(testIndex, (int) n, (int) r, numPerms);
    int[] myNthPerm = new int[(int) r];

    for (int i = 0; i < (int) r; i++) {
           myNthPerm[i] = testSet[myNthIndex[i]];
    }

    Console.WriteLine(string.Join(",", myNthPerm));
}

// Returns 1,12,4,18,20,19,7,5,16,11,6,8,21,15,13,2,14,9,10,17,3

这是一个 link 到 ideone 的工作代码。

Answer 3

您可以使用JNumberTools

   List<String> list = new ArrayList<>();
   //add elements to list;
    
   JNumberTools.permutationsOf(list)
       .uniqueNth(1000_000_000) //next 1 billionth permutation
       .forEach(System.out::println);

这个API会直接按照字典顺序生成下一个第n个排列。因此，您甚至可以生成 100 个项目的下一个十亿次排列。

要生成给定大小的下一个第 n 个排列，请使用：

JNumberTools 的 Maven 依赖项是：

<dependency>
    <groupId>io.github.deepeshpatel</groupId>
    <artifactId>jnumbertools</artifactId>
    <version>1.0.0</version>
</dependency>

计算巨大的排列 - 计算元素并获得第 n 个元素

Counting huge permutations - counting elements and getting nth element

c#

permutation

combinatorics

large-data

获取可能的排列数。

得到第n个排列