How to get nth permutation when repetition is allowed?

Question

Project Euler 24: What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

What if repetitions are allowed? like 1111111111,1223344457 etc. How can I get millionth permutation where repetitions are also included in counting.

And please note that input would still be the same. No repetitions in input.

I want to generate all possible passwords of length 10. And passwords can contain repeated characters so I want my function to work for that too.

Here is the code which gives nth permutation of a string. It works by exploiting the fact that for n elements there are n! permutations. And in lexicographic permutation first (n-1)! permutations would start with first digit and so on.

How can I modify this to get strings with repetitions also? Any particular algorithm which I should use?

To clarify things, I don't only need millionth permutation. I need all possible permutations. I can get all permutations without repetitions by running a for loop on this function. But I can't get permutations with repetitions. I want permutations with repetitions. Since I want to get all possible passwords. Think of all the possible passwords that you can have of 10 letters if only numbers were allowed. 10^10. I want all of them.

import java.util.*;

public class NthPermutation{

    private static int Factorial(int n){  
        if (n < 0)
            return 0;
         int ans = 1;
         for (int i=1;i<=n;++i)
            ans *= i;
         return ans;
     }

     public static String getNth(List<Integer> original, int permNum){

         List<Integer> numbers = new ArrayList<Integer>(original);  
         String nth = "";
         permNum--;
         int N = numbers.size();  

         for (int i=1;i<N;++i){
             int j = permNum / Factorial(N - i); 
             permNum = permNum % Factorial(N - i);
             nth = nth + numbers.get(j);
             numbers.remove(j);

         if (permNum==0)
             break;
         }

         for (int i=0; i<numbers.size();i++)
             nth = nth + numbers.get(i);

         return nth;
      }

      public static void main(String[] args){

          List<Integer> numbers = new ArrayList<Integer>();     
          for (int i = 0; i < 10; i++) 
              numbers.add(i);

          System.out.println(getNth(numbers,1000000)); 
       }
}

Answer 1

We need to first understand the Factorial Number System (or Factoradic number system) to solve this question. A factorial number system uses factorial values instead of powers of numbers (binary system uses powers of 2, decimal uses powers of 10) to denote place-values (or base).

The place values (base) are –

5!= 120 4!= 24 3!=6 2!= 2 1!=1 0!=1 etc.. The digit in the zeroth place is always 0. The digit in the first place (with base = 1!) can be 0 or 1. The digit in the second place (with base 2!) can be 0,1 or 2 and so on. Generally speaking, the digit at nth place can take any value between 0-n.

First few numbers represented as factoradics-

0 -> 0 = 0*0!
1 -> 10 = 1*1! + 0*0!
2 -> 100 = 1*2! + 0*1! + 0*0!
3 -> 110 = 1*2! + 1*1! + 0*0!
4 -> 200 = 2*2! + 0*1! + 0*0!
5 -> 210 = 2*2! + 1*1! + 0*0!
6 -> 1000 = 1*3! + 0*2! + 0*1! + 0*0!
7 -> 1010 = 1*3! + 0*2! + 1*1! + 0*0!
8 -> 1100 = 1*3! + 1*2! + 0*1! + 0*0!
9 -> 1110
10-> 1200

There is a direct relationship between n-th lexicographical permutation of a string and its factoradic representation.

For example, here are the permutations of the string “abcd”.

0  abcd       6  bacd        12  cabd       18  dabc
1  abdc       7  badc        13  cadb       19  dacb
2  acbd       8  bcad        14  cbad       20  dbac
3  acdb       9  bcda        15  cbda       21  dbca
4  adbc       10  bdac       16  cdab       22  dcab
5  adcb       11  bdca       17  cdba       23  dcba

We can see a pattern here, if observed carefully. The first letter changes after every 6-th (3!) permutation. The second letter changes after 2(2!) permutation. The third letter changed after every (1!) permutation and the fourth letter changes after every (0!) permutation. We can use this relation to directly find the n-th permutation.

Once we represent n in factoradic representation, we consider each digit in it and add a character from the given string to the output. If we need to find the 14-th permutation of ‘abcd’. 14 in factoradics -> 2100.

Start with the first digit ->2, String is ‘abcd’. Assuming the index starts at 0, take the element at position 2, from the string and add it to the Output.

Output                    String
  c                         abd
  2                         012

The next digit -> 1.String is now ‘abd’. Again, pluck the character at position 1 and add it to the Output.

Output                    String
 cb                         ad
 21                         01

Next digit -> 0. String is ‘ad’. Add the character at position 1 to the Output.

Output                   String
 cba                        d
 210                        0

Next digit -> 0. String is ‘d’. Add the character at position 0 to the Output.

Output                   String
 cbad                      ''
 2100

To convert a given number to Factorial Number System, successively divide the number by 1,2,3,4,5 and so on until the quotient becomes zero. The remainders at each step form the factoradic representation.

For example, to convert 349 to factoradic,

              Quotient        Remainder        Factorial Representation

349/1            349               0                             0
349/2            174               1                            10
174/3            58                0                           010
58/4             14                2                          2010
14/5             2                 4                         42010
2/6              0                 2                        242010

Factoradic representation of 349 is 242010.

Answer 2

If repetition is allowed, then:

• the first permutation is 0000000000
• the second permutation is 0000000001
• the tenth permutation is 0000000009
• the hundredth permutation is 0000000099
• the thousandth permutation is 0000000999
• the millionth permutation is 0000999999

and so on.

All of these are simply the number n-1 padded with enough number of zeroes on the left to make the whole string of length 10.

So to get the actual nth combination, all you would have to do is (below snippet in Python, you can convert to Java easily):

>>> def find_nth_combination(n):
...     print "0" * (10-len(str(n-1))) + str(n-1)
... 
>>> find_nth_combination(1)
0000000000
>>> find_nth_combination(100)
0000000099
>>> find_nth_combination(9062300000)
9062299999
>>> find_nth_combination(12300000)
0012299999

In case you want to solve this with repetition, you can have a look here (code is in Python).

---

To get all permutations, simply go through all the numbers.

So, you will need to do something like:

for x in xrange(1, 1001):
    find_nth_combination(x)

which will output:

0000000000
0000000001
...
...
0000000997
0000000998
0000000999