Author |
Topic: Factoradics (Read 772 times) |
|
harpanet
Junior Member
Posts: 109
|
 |
Factoradics
« on: Aug 31st, 2003, 10:25am » |
 Quote  Modify
|
Has anyone else heard of this term? I did a Google search and came up with only a single link, the article where I first came across it.
http://msdn.microsoft.com/library/default.asp?url=/library/en-us/dnnetse c/html/permutations.asp
Just as a number can be broken down into prime factors, creating a factoradic is breaking a number down into its 'prime' factorials. (e.g. 95 = 3*4! + 3*3! + 2*2! + 1*1! or [3,3,2,1]). Now that on its own does not seem particularly interesting (to me). But what was interesting was that, by manipulating this factoradic, it could be used to very quickly calculate a specified permutation of an array of consecutive integers (starting at 0).
e.g the 0th permutation of the numbers 0-5 is {0,1,2,3,4,5}, while the 385th permutation is {3,1,0,2,5,4}.
Although I understand that both the factoradic and permutations involve factorials, the mapping from one to the other seems somewhat mechanical and I cannot divine it's underlying truth - why does this work? It is very useful though.
|
|
 IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender: 
Posts: 4863
|
|
Re: Factoradics
« Reply #1 on: Aug 31st, 2003, 2:42pm » |
Quote Modify
|
While I have never seen this before, from what I read, there seems to be a couple misconceptions in your post. "Factoradics" have nothing to do with factorization, or any such thing as "prime factorials". What they are is an alternate form of "decimal expression". The individual entries in the factoradic expression for a number correspond to decimal digits.
The claims made in the webpage you linked are:
1) For every positive integer [smiley=a.gif], there is a unique sequence of integers {[smiley=a.gif]i} with 0 [le] [smiley=a.gif]i [le] [smiley=i.gif], such that
[smiley=a.gif] = [sum]i [smiley=a.gif]i [smiley=i.gif]!
(Note: The page linked says that [smiley=a.gif]i [le] [smiley=i.gif] + 1, but this is mistaken - caused I think by his getting confused with the mathematical notation he is using vs the computer algorithm, which for computational reasons adds an extra entry.)
This looks easy enough to prove. It's just like proving that every integer has a unique decimal representation (sans decimal point). The only difference is that instead of having powers of 10, you have factorials. The key to showing it is the formula
[smiley=n.gif]! = 1 + [sum][subi] [smiley=i.gif][cdot][smiley=i.gif]! (1 [le] [smiley=i.gif] < [smiley=n.gif])
2) That there is an easily computed 1-1 relationship between factoradic expressions and permutations.
This seems to be based on this idea: Suppose you want to permute [smiley=k.gif]+1 objects. List them in increasing order (if they aren't ordered, list them in an arbitrary order and define that to be their order). Let [smiley=a.gif] be a non-negative integer < ([smiley=k.gif]+1)!. [smiley=a.gif] has a factoradic expression with entries indexed from 0 to [smiley=k.gif]. The term [smiley=a.gif]k tells you that the left most entry in your permutation will be the ([smiley=a.gif]k+1)th highest object. The term [smiley=a.gif]k-1 tells you the next permutation entry should be the ([smiley=a.gif]k-1+1)th highest of the remaining elements, and so on. Each factoradic "digit" + 1 tells you which of the remaining elements to take next.
For example: To find permutation #17 of the 4 letters a,b,c,d: first find the factoradic for 17: 17 = 2*3! + 2*2!+1*1! So the factoradic is (2, 2, 1). Add 1 to each of them: (3,3,2)
Term Fac.+1 from element
1 3 abcd c
2 3 abd d
3 2 ab b
Permutation #17 is cdba.
The reason it works is that each digit in the factoradic has a max value of one less than the maxvalue of the next digit on the left. Just like every time you choose an element for your next position in the permutation, you have one less choice than you had the time before.
|
| « Last Edit: Aug 31st, 2003, 3:06pm by Icarus » |
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
harpanet
Junior Member
Posts: 109
|
|
Re: Factoradics
« Reply #2 on: Sep 1st, 2003, 8:26am » |
Quote Modify
|
Thanks Icarus, I'll spend some time digesting your explanation.
BTW, my references to factorization and 'prime' factorials were not misconceptions but rather (failed) attempts to compare the concept to something more familiar. Maybe I should have compared it to Polynomial coefficients or something.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Factoradics
« Reply #3 on: Sep 1st, 2003, 2:01pm » |
Quote Modify
|
Oh. Sorry then. But really what factoradics should be compared to is exactly what the writer of your link and I did compare them to, which is decimal expressions.
[ 4, 2, 0, 1 ] = 4*4! + 2*3! + 0*2! + 1*1! = 96 + 12 + 0 + 1 = 109
4201 = 4*103 + 2*102 + 0*101 + 1*100 = 4000 + 200 + 0 + 1 = 4201
|
|
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
harpanet
Junior Member
Posts: 109
|
|
Re: Factoradics
« Reply #4 on: Sep 1st, 2003, 2:10pm » |
Quote Modify
|
You're right. I shouldn't have tried to compare them to anything except what they actually are.  .
BTW. One of the questions on Project Euler http://mathschallenge.net/index.php?section=project asks for the millionth permutation of 0..9. With this algorithm, instant answer. Is coming across factoradics the day before serendipity or what?
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print