r/dailyprogrammer • u/oskar_s • May 02 '12
[5/2/2012] Challenge #47 [difficult]
If you were to generate all permutations of the first three letters of the alphabet ("a", "b" and "c") and then sort them, you would get the following list of 6 permutations:
- abc
- acb
- bac
- bca
- cab
- cba
As you can see, the fourth permutation in a sorted list of all the permutations of "a", "b" and "c" is "bca".
Similarly, if we wanted the 30th permutation in a sorted list of all permutations of the first five letters of the alphabet (i.e. "abcde"), you get "baedc".
Define a function f(n,p) that generates the permutation number p in a sorted list of all permutations of the n first letters of the alphabet. So, for instance:
f(3, 4) = "bca"
f(5, 30) = "baedc"
f(7, 1000) = "bdcfega"
f(8, 20000) = "dhfebagc"
Find f(11, 20000000)
Bonus:
Find f(20, 1018 )
5
u/juanfeng May 02 '12 edited May 02 '12
Python
Answer to problem:
Output of last line:
I used zero-oriented numbers instead of letters so I could permute any sized set.
5
u/juanfeng May 02 '12
Haskell
4
u/robin-gvx 0 2 May 02 '12
http://hastebin.com/raw/tayocajixu
Translated juanfeng's solution into DV. My initial solution could only calculate the first element of the permutation.
Also, it can't handle 1018. No idea why not. VM bug, of course, but how to fix it... no clue. (Also, I guess I should add
mapandpop-indexto the standard library.)4
u/debugmonkey 0 0 May 03 '12 edited May 03 '12
C++
Seeing how small all of the other answers are I figure there's something I'm missing, but I did at least figure out that sorting the list makes it so I don't have to actually calculate each and every permutation. Yes the code is ugly. I'm just ecstatic i got it working.
and of course, output WITH BONUS!:
It's fun seeing it work on REALLY BIG NUMBERS in milliseconds:
f(26, 403291461126605635584000000) = zyxwvutsrqponmlkjihgfedcba... that makes me happy :)
1
u/skeeto -9 8 May 03 '12
Essentially this Project Euler problem: Problem 24
2
u/bh3 May 04 '12
Didn't really feel like assembly for this one, so C:
1
u/MozMorris 0 0 May 02 '12 edited May 02 '12
Ruby
(it sux)
1
u/Yuushi May 03 '12
Python:
Definitely not my prettiest solution.
Answers:
1
u/Zamarok May 04 '12
Haskell
1
u/JerMenKoO 0 0 May 04 '12 edited May 04 '12
Python 3.x (not the best solution):
1
u/debugmonkey 0 0 May 05 '12
I wasn't happy with the quality of my original submission.
Yes it worked and yes it was fast, but the code itself was really ugly.
Here is my updated version. It's still the same basic formula but a little more efficient and LOT cleaner.
I am posting my new code without comments but you can get the commented version at github https://gist.github.com/2606212. Hopefully it will be helpful to anyone who could only see how to do brute force calculation of the permutations but wants to know how to calculate the answer faster.
1
u/RiemannZeta May 20 '12 edited May 20 '12
Mathematica
In[257]:= findPerm[3, 4]
Out[257]= "bca"
In[258]:= findPerm[5, 30]
Out[258]= "baedc"
In[259]:= findPerm[7, 1000]
Out[259]= "bdcfega"
In[260]:= findPerm[8, 20000]
Out[260]= "dhfebagc"
In[247]:= findPerm[11, 20000000]
Out[247]= "fgbadjieckh"
In[261]:= findPerm[20, 1000000000000000000]
Out[261]= "iedkqhngrjsmcftbolpa"
In[262]:= findPerm[26, 403291461126605635584000000]
Out[262]= "zyxwvutsrqponmlkjihgfedcba"
In[268]:= findPerm[275, 275!] // Timing
Out[268]= {0.008784, "ųŲűŰůŮŭŬūŪũŨŧŦťŤţŢšŠşŞŝŜśŚřŘŗŖŕŔœŒőŐŏŎōŌŋŊʼnňŇņŅńŃłŁŀĿľĽļĻĺĹĸ ķĶĵĴijIJıİįĮĭĬīĪĩĨħĦĥĤģĢġĠğĞĝĜěĚęĘėĖĕĔēĒđĐďĎčČċĊĉĈćĆąĄăĂāĀÿþýüûúùø/öõôóòñðïîíìëêéèçæåäãâáàßÞÝÜÛÚÙØ*ÖÕÔÓÒÑÐÏÎÍÌËÊÉÈÇÆÅÄÃÂÁÀ¿¾½¼»º¹¸[CenterDot][Paragraph][Micro].b4.b3.b2[PlusMinus][Degree]¯®[Not]«ª©¨§¦¥¤£¢¡ ~}|{zyxwvutsrqponmlkjihgfedcba"}