2

I am using this library for combinatorics: https://github.com/eoincampbell/combinatorics/

What I need is to find n-th permutation and count elements of fairly large sets (up to about 30 elements), but I get stopped in my tracks before even starting, check out this code:

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;

Everything works peachy just until 20 element large set, once I add 21st, permutations stop working right, eg. here is what permutation.Count returns:

-4249290049419214848

which is far from being the right number.

I am assuming that it all boils down to how huge numbers I use - overflowing ints/longs that library uses. That is why, I am asking for an advice - is there a library? approach? or a fairly quick to implement way to have combinatorics work on bigintegers?

Thanks!

Joseph Wood
  • 7,077
  • 2
  • 30
  • 65
internetofmine
  • 198
  • 12
  • Have you tried to replace `int` with `System.Numeric.BigInteger`? I think it's the largest integer representation .net knows. – Smartis has left SO again Aug 08 '18 at 06:32
  • Do you only need a specific combination and the coun? I assume you could calculate both, without creating the full set of all possible permutations. Even if you switch to a BigInteger based implementation this would overflow your memory quite fast. – Iqon Aug 08 '18 at 06:32
  • Yes I am writing my own BigInteger based solution at the moment, was hoping there might be some library for that that would speed things up, but oh well :) I indeed need random combinations and count. – internetofmine Aug 08 '18 at 06:37
  • 1
    In your example permutation.Count is equal to 21! which exceeds the maximum value of a long integer. To generate a random permutation, you do not need to know the nth. you can simulate a no-discount draw in your list of numbers, using a table showing those that have already been drawn. – Jean-Claude Colette Aug 08 '18 at 06:55

3 Answers3

3

Get the number of possible permuations.

The number of permutations is defined by nPr or n over r

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

Where:

  • n = Number of objects
  • r = the size of the result set

In your example, you want to get all permutations of a given list. In this case 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;
    }
}

Get the nTh permutation

This one depends on how you create/enumerate the permutations. Usually to generate any permutation you do not need to know all previous permutations. In other words, creating a permutation could be a pure function, allowing you to directly create the nTh permutation, without creating all possible ones.

This, however, depends on the algorithms used. But will potentially be a lot faster to create the permutation only when needed (in contrast to creating all possible permutations up front -> performance and very memory heavy).

Here is a great discussion on how to create permutations without needing to calculate the previous ones: https://stackoverflow.com/a/24257996/1681616.

Iqon
  • 1,920
  • 12
  • 20
1

This is too long for a comment, but wanted to follow up on @Iqon's solution above. Below is an algorithm that retrieves the nth lexicographical permutation:

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;
}

Here is a test case and the result of calling nthPerm using the code provided by @Iqon.

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

Here is a link to ideone with working code.

Joseph Wood
  • 7,077
  • 2
  • 30
  • 65
  • 1
    I should have noted that if you set `testIndex = 0`, you will get the 1st permutation (I.e. `myNthPerm` will be identical to `testSet`). If you set `testIndex = numPerms - 1`, `myNthPerm` will be the `testSet` in reverse order. – Joseph Wood Aug 09 '18 at 13:45
1

You can useJNumberTools

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

This API will generate the next nth permutation directly in lexicographic order. So you can even generate next billionth permutation of 100 items.

for generating next nth permutation of given size use:

maven dependency for JNumberTools is:

<dependency>
    <groupId>io.github.deepeshpatel</groupId>
    <artifactId>jnumbertools</artifactId>
    <version>1.0.0</version>
</dependency>
Deepesh Patel
  • 11
  • 4