wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> general problem-solving / chatting / whatever >> Factoradics
        
(Message started by: harpanet on Aug 31^st, 2003, 10:25am)

Title: Factoradics
Post by harpanet on Aug 31^st, 2003, 10:25am

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/dnnetsec/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.

Title: Re: Factoradics
Post by Icarus on Aug 31^st, 2003, 2:42pm

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.

Title: Re: Factoradics
Post by harpanet on Sep 1^st, 2003, 8:26am

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.

Title: Re: Factoradics
Post by Icarus on Sep 1^st, 2003, 2:01pm

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*10³ + 2*10² + 0*10¹ + 1*10⁰ = 4000 + 200 + 0 + 1 = 4201

Title: Re: Factoradics
Post by harpanet on Sep 1^st, 2003, 2:10pm

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? :)