PyPE solution to PE problem 24
PyPE solution to PE problem 24
Blueprint information
- Status:
- Complete
- Approver:
- None
- Priority:
- Undefined
- Drafter:
- None
- Direction:
- Needs approval
- Assignee:
- None
- Definition:
- Approved
- Series goal:
- None
- Implementation:
-
Implemented
- Milestone target:
- None
- Started by
- Scott Armitage
- Completed by
- Scott Armitage
Whiteboard
ProjectEule
===
A permutation is an ordered arrangement of objects. For example, 3124 is one
possible permutation of the digits 1, 2, 3 and 4. If all of the permutations
are listed numerically or alphabetically, we call it lexicographic order.
The lexicographic permutations of 0, 1 and 2 are:
012 021 102 120 201 210
What is the millionth lexicographic permutation of the digits 0--9?
Solution
--------
We procede from most- to least-significant digit of the answer. We know that
for a fixed first digit, there are 9! possible permutations of the remaining
digits. So, there are 9! permutations starting with 0, 9! starting with 1,
and so on. This means that the first digit can be found by determining how
many times 9! goes into the desired limit case. For n=10**6, we have that
9! = 362880, which goes into 10**6 twice. This accounts for all permutations
starting with 0 and 1, and thus the answer must begin with the digit 2.
We then shorten our list of available digits by removing the 2 and apply
this same process for the remaining digits, except now we have 8! possible
permutations for each starting digit.
The solution is obtained by repeating this process until there are no more
digits remaining to select from.
Answer
------
2783915460
