6

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)); } }
Improve this question
4
  • Unless I have misunderstood, you shouldn't consider repetitions. Commented Apr 18, 2015 at 13:59
  • @Atuos I want to generate every possible password. And passwords can have repetitions, so. Commented Apr 18, 2015 at 14:07
  • yes it does. I tried your program with the list [1,1,2,3]: permutation # 1 outputs 1,1,2,3; permutation # 2 outputs 1,1,3,2; permutation # 24 outputs 3,2,1,1 Commented Apr 18, 2015 at 14:22
  • Please read the edited question, sorry for not making it clear earlier. I don't want repetitions in input. I want to give same input, output should generate permutations with repetitions. I hope I'm clear now. Commented Apr 18, 2015 at 14:27

3 Answers 3

Reset to default
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
Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

This is way off: 000000000001 is not permutation at all, since permutation should contain all digits from 0-9 exactly once.
@Riko Well the OP is expecting an output including 1111111111, so how do you explain that? You are right though, this is not technically a permutation, but then, its is the question itself which is void.
2

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.

Improve this answer

2 Comments

Huh. I have no idea if I should give you an upvote or not. Your post actually answers the question as written, however the questioner seemed to use the term permutation wrong (since he talked about repetitions). Also, the question was asked two years ago. Quite sad, since you answer is quite good, but I think, nobody would find it by searching. Edit: upvoted you because your question is the only real answer for actual permutations here.
I was asked this question in an interview several years ago. The interviewer was patient as I walked through deriving this in the interview. I didn't get the job but I did finish my white-boarded code later. This and the wikipedia article make it so much clearer now. en.wikipedia.org/wiki/Factorial_number_system I'd like to retry that interview again now knowing it's as simple as dividing by increasing numbers and saving the remainder.
0

WITHOUT REPETITIONS:

Since you only need 1000000000th permutation, you can brute-force this problem. Start with string: "0123456789" and use C++ equivalent of next_permuation, for which you can get function here: http://codeforces.ru/blog/entry/3980. Just iterate one million times and you will arrive to solution.

There is fancier greedy solution which runs very fast and you can read about it here: https://math.stackexchange.com/questions/60742/finding-the-n-th-lexicographic-permutation-of-a-string

WITH REPETITIONS:

This problem is very simple with repetitions since it is equivalent to just taking number and padding it with 0s at beginning.

1st permuation: 000000001 15th permuation 000000015 etc.
Improve this answer

7 Comments

I don't only need 1000000000th permutation. I need all possible permutations. My code gives me all permutations without repetitions. Now 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.
Both my answers can be used to generate all of them. In first case just start with "0123456789" and keep iterating, in second use what I wrote :) hope this helps
I don't get the second part i.e. WITH REPETITIONS. Can you explain it further please? Or maybe provide some useful link for me to read. I don't understand how would we be able to cover all permutations. Like 1122334455,1111000000 etc.
When you will iterate all numbers up to 10^10 you will go over all iterations. You can just go over all numbers and convert them in strings and pad with 0s.
@user3834119 If you want to generate all 10 digit combinations, you will need to iterate over that range of numbers [0-9999999999]. Once you've done that, you can simply pad each number with the number of zeroes it is short of being of length 10 digits. We pad with zeroes, because they are omitted (meaningless) in the integer representation of a number, every other digit in the number is significant.
|

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.