Computational limits for huge k-th permutation?

Would it be feasible to calculate directly a k-permutation like k = 10^200000000?

If not, What would be the computational limit to calculate huge k-th permutation in a today computer? How can I estimate it?

Like, what's the biggest k-th permutation that I could calculate in less than a day?

*Note, the permutatio process would be something like this: https://math.stackexchange.com/questions/60742/finding-the-n-th-lexicographic-permutation-of-a-string (if there's a better one, please point me to it)

I will try to clarify. I will generate a file with a really huge number consisting on digits filling from 200Mb on size storage to absurd numbers like 300000!. (200 x 10^6 digits to 300k! or 1M!)

I want to calculate directly the permutation that that number represents. Is it possible to calculate in few hours? I have an algorithm almost linear time, if needed, for the job I want it to do.

But I read about 9! permutations take 10mins. So probably some permutation on the upper range of this could not be computed in a reasonable time (less than one day). What would be such upper limit, which permutations more than x! could not be directly calculated in my reasonable time? How to estimate this? What can I expect to compute, just the ones up to 10k! 100k! ? 300000!?

• Yep I read factorial number system and it's intended to use in lexicographic order. Anything about limitations and computational time/limit? Sep 11, 2016 at 21:13
• I think that the reason this hasn't got an answer yet is that no-one understands what your question is. Sep 14, 2016 at 10:43
• Oh, I'll try to rebuild the description. I just want to know what's the expected bigger magnitude of a permutation that I could calculate before getting hands on it, because the programming would take days, to focus at a maximum expected range Sep 14, 2016 at 17:25
• What do you mean with "today computer" ? The kind of machine a developer has on its desk, or the biggest machine we can buy today ? Is 8TB of SSD an option ? Sep 15, 2016 at 6:26

The algorithm described in the Q&A you reference has a time dependency worse than O(n^2). Computing a factorial is worse than O(n) (from Wikipedia), and you have to compute all factorials up to n for each permutation, in descending order.

To avoid this time dependency, you could compute all these factorials in increasing order and storing them.

I wrote a simple program to get some actual figures and, on my developer laptop with .NET BigInteger, I got:

• Computing 1 000 000 factorials takes ~22 minutes;
• The required memory to keep them all would be ~1.12 TB;
• Computing the actual permutation would take ~52 minutes (extrapolated from 100 steps spread over the entire factorials range).

The fastest way to write and reread these factorials from disk would probably be to let the paging mechanism do it (according to Memory Limits for Windows and Windows Server Releases, you should be able to go up to 15.5 TB). So, if you can get a machine with a 2 TB SSD disk for the page file :

• Writing the 1.12 TB of factorials would take ~19 minutes at 1 GB/sec;
• Reading it back would take ~9.5 minutes at 2 GB/sec.

Thus, ~100 minutes would allow you to compute a permutation up to k ~ 10^5 565 709 from a set of 1 000 000 symbols (1000000! ~ 8.263e5565708).

The RAM needed by the algorithm would be quite reasonable (mainly 2 factorials in memory at the same time, ~5 MB).

So you could probably compute in one day a permutation from a set of a few million symbols, or more with a faster machine and a better arbitrary precision arithmetic library,

• I think I didn't manage to explain the question right. Anyhow, I appreciate the benchmark times, that will be partly useful. Also you pointing having to calculate each "digit" on the factorial system. As per storage, I think that is not correct, only it's needed the direct permutation, no need to store all factorials or intermediate stuff. I'm upvotingbthe benchmark so if you get another you get reward even if it does not exactly answer, as I did not correctly asked Sep 20, 2016 at 20:16
• @cristo In the Q&A you cited, an answer details the computation for the 1,000,000th permutation of a set of 10 symbols. That requires 9!, 8!, 7!, ... The same algorithm on a set of 1,000,000 symbols require 1,000,000!, 999,999!, 999,998!, ... On my machine, computing all of these without storing them would take ~1035 days. Sep 21, 2016 at 3:13
• I have a paper with an algo that promises linear time by not giving lexicographically sorted output. Have you checked for 100k! ? If so please say estimated time or your formula to calculate the timing Sep 22, 2016 at 16:47
• If you have a reference to that paper, I'm very interested. I have no formula, I wrote a sample program that just performs the key steps of the algorithm described in the Q&A you cited. It actually computes factorials from 1 to 1 000 000, but only keeps 1 every 10 000 in memory. It then performs 100 steps of the algorithm with these factorials, and multiply the total time by 10 000 to estimate the actual time. Sep 22, 2016 at 17:18
• The factorials are computed the simple way, by a series of multiplications. The intermediate time at the end of the nth iteration of the loop is the time needed to compute n!. Summing 1 000 000 of these intermediate times gives me some very rough estimate of the time needed to execute the algorithm without storing the factorials. There are certainly better algorithms than this one... Sep 22, 2016 at 18:06