0

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!?

  • See also link 1 and link 2. – rwong Sep 11 '16 at 21:10
  • Yep I read factorial number system and it's intended to use in lexicographic order. Anything about limitations and computational time/limit? – Cristo Sep 11 '16 at 21:13
  • 1
    I think that the reason this hasn't got an answer yet is that no-one understands what your question is. – Peter Taylor Sep 14 '16 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 – Cristo Sep 14 '16 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 ? – Philippe Sep 15 '16 at 6:26
2
+25

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 – Cristo Sep 20 '16 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. – Philippe Sep 21 '16 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 – Cristo Sep 22 '16 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. – Philippe Sep 22 '16 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... – Philippe Sep 22 '16 at 18:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.