Prev: Fractal Bagatelle
Next: Freemasonry and Judaism: Powers Behind Revolutions, by Granite Stone
From: James Waldby on 16 May 2010 00:19
On Sat, 15 May 2010 16:45:16 -0700, jdege(a)jdege.us wrote:

> Factoradic numbers make for a mathematically simple representation of
> the permutations of a set. But the process of generating a specific
> permutation involves shuffling items around.
>
> See http://en.wikipedia.org/wiki/Factorial_number_system#Permutations
[snip example]
> My question: Is there a known algorithm for calculating these indexes?
>
> We could, to eliminate the cost of shifting our elements around, create
> a permutation of the indexes into our set, as described above. Is there
> a way of calculating the new indexes that is cheaper that constructing a
> new permutation set of indexes?

In the above and in the snipped part, your usage of the word
"index" is difficult for me to follow. But I imagine you aren't
asking how to compute the permutation number corresponding to a
given permutation, since that is so trivial[*], but instead want
to convert a permutation number to a factoradic number so that
you can write out the permutation that corresponds to the number.

Look at the 341010! example in the web page, which says,
"341010! stands for 3_6 4_5 1_4 0_3 1_2 0_1, whose value is
((((3×5 + 4)×4 + 1)×3 + 0)×2 + 1)×1 + 0 = 46310." The latter
expression should make it fairly clear how to reverse the process
and produce the factoradic number's digit in reverse order:
Let i=1 and n=perm#; while n is non-zero, produce a digit d
equal to n mod i, then set n to (n-d)/i. This is the same
method discussed in the first answer at
<http://stackoverflow.com/questions/759296/converting-a-decimal-to-a-mixed-radix-base-number>
and in the Goplat entry, 20% along within
<http://forums.xkcd.com/viewtopic.php?f=17&t=13530&start=0&st=0&sk=t&sd=a>.

[*] Ie, write down the factoradic number of the permutation, and
use ordinary arithmetic to convert that to any desired base

--
jiw
From: James Waldby on 16 May 2010 00:25
On Sun, 16 May 2010 04:19:12 +0000, James Waldby wrote:
> On Sat, 15 May 2010 16:45:16 -0700, jdege(a)jdege.us wrote:
>> Factoradic numbers make for a mathematically simple representation of
>> the permutations of a set. But the process of generating a specific
>> permutation involves shuffling items around.
>>
>> See http://en.wikipedia.org/wiki/Factorial_number_system#Permutations
[...]
> [you] want to convert a permutation
> number to a factoradic number so that you can write out the permutation
> that corresponds to the number.
>
> Look at the 341010! example in the web page, which says, "341010! stands
> for 3_6 4_5 1_4 0_3 1_2 0_1, whose value is ((((3×5 + 4)×4 + 1)×3 + 0)×2
> + 1)×1 + 0 = 46310." The latter expression should make it fairly clear
> how to reverse the process and produce the factoradic number's digit in
> reverse order: Let i=1 and n=perm#; while n is non-zero, produce a digit
> d equal to n mod i, then set n to (n-d)/i.

Oops, "add 1 to i" is missing. The "while" should have read:
"while n is non-zero, produce a digit d equal to n mod i, then
set n to (n-d)/i and add 1 to i."

[...]

--
jiw
From: James Waldby on 16 May 2010 02:40
On Sat, 15 May 2010 22:45:31 -0700, jdege(a)jdege.us wrote:
> On May 15, 11:19 pm, James Waldby <n...(a)no.no> wrote:
>> On Sat, 15 May 2010 16:45:16 -0700, jd...(a)jdege.us wrote:
>> > Factoradic numbers make for a mathematically simple representation of
>> > the permutations of a set.  But the process of generating a specific
>> > permutation involves shuffling items around.
>>
>> > Seehttp://en.wikipedia.org/wiki/Factorial_number_system#Permutations
>> [snip example]
>> > My question: Is there a known algorithm for calculating these
>> > indexes?
>>
>> > We could, to eliminate the cost of shifting our elements around,
>> > create a permutation of the indexes into our set, as described above.
>> > Is there a way of calculating the new indexes that is cheaper that
>> > constructing a new permutation set of indexes?
>>
>> In the above and in the snipped part, your usage of the word "index" is
>> difficult for me to follow.  But I imagine you aren't asking how to
>> compute the permutation number corresponding to a given permutation,
>> since that is so trivial[*], but instead want to convert a permutation
>> number to a factoradic number so that you can write out the permutation
>> that corresponds to the number.
>
> No. Assume that the base set is implemented as an array, and that each
> element of the set can be accessed by indexing that array with an
> integer between 0 and n-1, where n is the number of elements in the set.
>
> So, given an index i, and a factoradic number p, I need to access the
> i'th element of the p'th permutation. I can do that by using the usual
> process for creating a permutation, resulting in a new array containing
> copies of the same elements as the original, and then indexing the i'th
> element of the new array. But, if it's expensive top copy around the
> elements, I'd probably not want to do that.
>
> 1: I could implement my base set as an array of pointers to elements, so
> that my permutation would simply be a copy of the pointers.
>
> 2: I could implement my base set as an array of elements, but to permute
> an array of indexes, from 0 to n-1, and then the i'th element of the
> p'th permutation would be an index into the array of elements.
>
> Both of these options add a layer of indirection, in order to avoid
> copying the elements around.

As I still don't understand what you mean, and would have to guess or
make assumptions about what getPermutationNumber() and permuteSet() do,
or how your sets and FactorRadic types work, I won't say more. Maybe
you can get some useful comments by posting in the comp.programming
newsgroup.

[snip code using getPermutationNumber() and permuteSet() etc]

> What I'm wondering is whether there is a known algorithm for such a
> function, that involves less work than permuting the array.

When you repost in comp.programming, it may be useful to give a higher-
level view of the problem you are solving. The discussion so far seems
to be of implementation issues rather than processes subject to better
algorithms. Make your program work; take some measurements; don't bog
down in irrelevant optimization attempts.

--
jiw
 | 
Pages: 1
Prev: Fractal Bagatelle
Next: Freemasonry and Judaism: Powers Behind Revolutions, by Granite Stone