Prev: Draft paper submission deadline is extended: ISP-10, Orlando, USA
Next: Request to review OWASP ESAPI crypto
From: bmearns on 22 Feb 2010 14:46
On Feb 22, 1:26 pm, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote:
> bmearns wrote:
> > mok-kong shen wrote:
> > [snip]
> >> For indexing permutaions of n 'distinct' objects, there are in my humble
> >> view very good codes available on the internet, see e.g.
>
> >>http://stackoverflow.com/questions/1506078/fast-permutation-number-pe....
>
> > The method described in that link actually is factoradic encoding. As
> > I mentioned, if you have already come up with a method that works,
> > it's very possible that you are already using factoradic without
> > realizing. This is because factoradic is quite intuitive for this
> > application and is intimately related to how you would actually build
> > up a permutation from the set of N items.
>
> Entirely right. If I could be allowed to be explicit (I attempted to
> avoid to be so), I wondered why you had assumed that I did't know that
> in your first post in this thread.

Well based on my original understanding of your problem, factoradic
was the obvious solution, so the fact that you hadn't mentioned it is
why I assumed you didn't know it.


> To tell the entire truth, I asked a time ago for a code for a simplified
> case (with only 2 different kinds of objects) in another
> internet group. One person offered to dig up his codes he did
> previously for the general case (for arbitrarily number of different
> kinds of object). But later he presented only the code from index to
> permutation but not the code from permutation to index. Later, not
> being able to obtain the missing part of his code, I wrote my own code
> for the simplified case and published it. If the general case is simple
> in your opinion, I should be very grateful, if you would kindly give at
> least an adequate pseudo-code of the algorithm, in particular the part
> from index to permutation, so that I could write a C-code based on it.

We seem to be going somewhat in circles again, because I still don't
know exactly what case you're looking for. But for both factoradic
(arranging a set of items into a particular order) and base-N
(choosing each item from the same set of N unique objects, with
replacement) it's just base conversion. The only different is whether
the digit-weight is a power or a factorial.

For base-N, where each item is chosen from a set of N unique items,
and then put back (so it can potentially be used again for another
item):
To convert a numerical value into a sequence, divide the numeric value
by N, using integer division. The remainder tells you which item to
use for the first in the sequence. The integer quotient becomes the
new numerical value, and so you start again, dividing this new value
by N. The remainder is now your second item, and so on, continuing
until the quotient is 0.

For factoradic, the concept is similar, except the divisor changes.
Start by setting W (weight) = 2 (it's 2!, the weight of the second
digit, just as N was the weight of the second digit above). Divide the
numerical value by W: the remainder is the first factoradic-digit and
the integer quotient is your new value. Now you're up to the third
digit which has a weight of 3! = 3*2!. But you already divided
everything by 2!, so you really just want a weight of 3. So divide the
new value by 3, the quotient is the next digit, and the quotient is
the new value. Now the weight should be 4! = 4*3!, but you already
divided everything by 3!, so you just use W=4. And so on.

The only other tricky thing about factoradic is there's an implicit 0-
value digit at the beginning, which has a weight of 0! = 1. It always
has a value of 0 so contributes nothing to the overall value, but it
does represent an item in your list. Notice that the first digit we
produced was the result of mod 2, so it's either a 0 or 1. This
represents the second-to-last item chosen for the permutation, when
there were only two items left to choose from (in the hypothetical
case, in reality, we were building the permutation backwards). So you
pick one of those to be the next item (second to last), and you still
have one left. You have to choose that one at this point, so that
choice contains no information of it's own, which is why its value is
always 0: it can't change the overall value because it has no
information.

Actually there is one more tricky thing about factoradic: figuring out
which item from your set each digit corresponds to. Start at the most
significant, the digit which has a weight of N!. This digit was the
result of a mod N operation, so it can have any value in [0,N-1]. In
other words, it can be any index into your original set of N items.
Therefore, this must have been the first item "chosen" for your
permutation and it's value is simply an index into your set. So pick
that item and put it down as the first item in your sequence. You also
have to remove it from the set, which means the indicies in the set
have changed. Specifically, all the items that had a higher index will
move down by 1. This is what the set looked like when the second item
was "chosen", so the next digit down is simply an index into /this/
set. And so you just keep going like that and by the time you get to
the last one, there's only 1 left and so it of course has index 0, as
described in the last paragraph.

[clip]
> This paragraph of yours is in my understanding different in sense from
> the previous one and so my last paragraph may have been a wrong answer
> due to my misunderstanding of your last paragraph. Now, yes, I "did"
> mean a case like what you wrote "... 3 apples, ......". For I wrote in
> my original post: " ...a number of selected objects, identical or
> different (in kind, size, colour) ....". I thought that should be
> quite clear to the readers (BTW, on later occasions I also mentioned
> "permutatations with repeated elements").

I don't have a lot of formal experience in combinatorics, so I'm sure
I missed some of the important clarifying points in your earlier
posts. I was confusing repetition with replacement, thinking that you
were talking about a set of unique items, but where items are replaced
after being drawn. This would be the base-N system we already
discussed. But now I see you meant that the original set contains non-
unique elements, but the drawing process does not involve replacement.

-Brian
From: Mok-Kong Shen on 22 Feb 2010 15:25
bmearns wrote:

> Well based on my original understanding of your problem, factoradic
> was the obvious solution, so the fact that you hadn't mentioned it is
> why I assumed you didn't know it.

But did you understand that the permutations needed in the context o
my original post were those with (in the general case) repeated
elements? If yes, I highly doubt that employing factoradic number
systems as such would "help", unless you could show otherwise. Or had
you not carefully read my original post at all?

> We seem to be going somewhat in circles again, because I still don't
> know exactly what case you're looking for. But for both factoradic
> (arranging a set of items into a particular order) and base-N
> (choosing each item from the same set of N unique objects, with
> replacement) it's just base conversion. The only different is whether
> the digit-weight is a power or a factorial.

Let me quote my original post:

My humble idea is to have in the drawing a number of selected
objects, identical or different (in kind, size, colour), positioned
in a certain discernable order agreed upon with the communication
partner. These objects represent thus a permutation of them, which
has in the lexicographical ordering of permutations a unique index
to serve as the number to be transmitted.

Should this still be not clear enough, let me use the example in your
last post: One likes to use some fruits in a drawing to hide the bits
to be transmitted and agrees with the partner that these will be
some small number of apples, bananas, oranges and grapes, the exact
number being dependent on the magnitute of the binary number that
corresponds to the index of the permutation in the lexicographical
ordering of these objects. Thus in a particular case one chooses
3 apples, 1 banana, 1 orange, and 2 grapes and ordered them e.g.
as AAOBGAG. One needs on such occassions evidently a code to convert
such an ordering to a number and vice versa from a number to such an
ordering of permutation. Is that clear enough? Is that doable?
Certainly yes, right? What I currently don't have is the C-code for
that. I didn't mentioned this in my original post, because, on the
one hand, as I said, I have a preliminary program design sometime ago
and on the other hand, the person in the other group I mentioned had
in fact (at least according to him) such a code, but unfortunately,
for reasons unknown to me, failed to fulfill his promise of publishing
his entire code (he published 'only' the part from index to permutation
but not the part from permutation to index).

M. K. Shen
From: bmearns on 23 Feb 2010 13:37
On Feb 22, 3:25 pm, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote:
[snip]
> Let me quote my original post:
>
> My humble idea is to have in the drawing a number of selected
> objects, identical or different (in kind, size, colour), positioned
> in a certain discernable order agreed upon with the communication
> partner. These objects represent thus a permutation of them, which
> has in the lexicographical ordering of permutations a unique index
> to serve as the number to be transmitted.

Thank you, but I have a complete history of the discussion. Obviously,
your initial description was unclear to me, so repeating it now
doesn't help anything. Your example below does.

> Should this still be not clear enough, let me use the example in your
> last post: One likes to use some fruits in a drawing to hide the bits
> to be transmitted and agrees with the partner that these will be
> some small number of apples, bananas, oranges and grapes, the exact
> number being dependent on the magnitute of the binary number that
> corresponds to the index of the permutation in the lexicographical
> ordering of these objects. Thus in a particular case one chooses
> 3 apples, 1 banana, 1 orange, and 2 grapes and ordered them e.g.
> as AAOBGAG. One needs on such occassions evidently a code to convert
> such an ordering to a number and vice versa from a number to such an
> ordering of permutation. Is that clear enough? Is that doable?
> Certainly yes, right? What I currently don't have is the C-code for
> that. I didn't mentioned this in my original post, because, on the
> one hand, as I said, I have a preliminary program design sometime ago
> and on the other hand, the person in the other group I mentioned had
> in fact (at least according to him) such a code, but unfortunately,
> for reasons unknown to me, failed to fulfill his promise of publishing
> his entire code (he published 'only' the part from index to permutation
> but not the part from permutation to index).

I don't have any C-code to do this, nor have I encountered the problem
before, but it seems like it should follow pretty closely to the base-
conversion problems I described previously. The only tricky part
should be figuring out the weight at each digit. Obviously the least
sig digit contributing digit has to have a weight of 1 or you would
have wholes in the range. Each higher order digit needs to be weighted
equal to the number of different values you can represent with the
preceding digits, otherwise you will similarly have wholes in your
range.

So you said you're looking for code to go from permutation to index,
so let me see if I can work through the example you gave. I'm coming
up with this as I go, so bear with me if it gets a little windy.

You're initial set (a sequence, actually) is (AAABGGO). The example
permutation you gave is AAOBGAG. We'll assume you started by picking
an A, then another A, and so on, until all that was left was the final
G. As discussed previously, that final "choice" contained no
information and therefore contributes nothing to the value. Therefore,
the preceeding A is the least sig contributor, so it has a weight of
1. When you picked it, your options were A and G, so we'll assume that
we're sorting lexicographically so A would have a digit-value of 0 at
this point (G, had it been picked instead, would have a value of 1).
Therefore, our value as of AG is still 0. There are two different
values you can create with these two characters (0=AG, 1=GA), so the
weight of the next digit is 2.

At this point when creating the permutation, you had AGG, and you
picked G. Since we can't tell the difference between the two G's, they
both have the same digit value at this point, which is 1. This
contribution is therefore 1*2 = 2. Total value as of GAG is 2.
However, there are only three different distinct ways you can permute
{AGG}, so the weight of the next digit is 3.

For that digit, the set was {ABGG}, so be has a value of 1,
contributes 1*3 = 3, and the total value of BGAG is 5. Total number of
permutations of these elements is 4!/2! = 12, so the next weight is
12.

Continuing on, we get pick O from {ABGGO}, so it's digit-value is 3,
it contributes 3*12 = 36, total value of OBGAG is 41, and the next
weight is 5!/2! = 60.
Pick A from {AABGGO}, it's digit value is 0, contribues 0, total value
of AOBGAG is 41, next weight is 6!/2!/2! = 180
Finally pick A from {AAABGGO}, digit value is 0, contributes 0, final
value of AAOBGAG is 41, next weight would be 7!/3!/2! = 420 which
makes sense, because it's the total number of possible arrangements of
the original set.

I'm somewhat confident that's correct, but without more time to
explore it, I'm not completely sure. I'm also not sure off hand how
you would do the opposite: figure out the permutation to use for a
given value. The tricky part is that the weights at each digit depends
on which digits are available then. For instance, if you choose A for
the first (most sig) digit (as in the above example), its weight is
180 as we saw (the remaining set of items is {AABGGO}). However, if
you picked O for the first digit, the remaining set would be {AAABGG},
so it's weight would only be 6!/3!/2! = 60. So I'm really not sure how
to proceed from there. If you have ideas, I'd be very interested to
hear them.

-Brian
From: Mok-Kong Shen on 23 Feb 2010 16:08
bmearns wrote:
[snip]
> ...... If you have ideas, I'd be very interested to
> hear them.

Thank you for having spent effort to do some analysis of the problem
of coding. As said, I coded sometime ago the simplified case of only
2 different kinds of objects. I believe that the same technique could
be applied to the general case, the only thing one should thereby take
particular care of is to keep the index count correct in diverse
possible configurations of the objects as the algorithm steps forward.
I am currently working on a program sketch I did previously. Should
I encounter obstacles, I'll report and we could discuss how best to
overcome them.

M. K. Shen



From: Mok-Kong Shen on 26 Feb 2010 13:00
I have completed the coding for permutations with repeated elements
with a test program attached below.

M. K. Shen

-----------------------------------------------------------------------

#include <stdio.h>
#include <stdlib.h>

// uperm.c Permutations with repeated elements.
// Version 1.0. Release date: 26.2.2010.
// Arrays card, cardsub, perm and integers scard, nperm are to be
// declared. cardsub is work space and has the same size as card.
// card[*] are the cardinalities of (dimcard) sets of different objects.
// perm[*] represent a permutation of all (dimperm) objects, with
// designations of different kinds of objects being given by numerical
// values in [0, dimcard-1].
// permindex gives the index of the permutaion in the lexicographic
// ordering (in the sense of 0 < 1 < 2 ... etc., which may not
// necessarily correspond to the "lexicographic" ordering of the
// "names" of kinds of objects which the user chooses to associate with
// the numerical designations).
// Conditions to be satisfied by data: dimcard >= 2 card[*] >= 1
// sum of cardinalities of the sets == dimperm <= 12.
// Start with initpermsys, thereafter use findperm or findindex.
// Application example: Using the ordering of some selected objects in
// picture to hide a number in steganography.
// Please send comments and critiques to mok-kong.shen(a)t-online.de.

void error(int n)
{ printf("error no. %d\n",n); exit(1);
}

int fac(int n)
{ int i,s=1;
for (i=2; i<=n; i++) s*=i;
return s;
}

int numperm(int dimcard, int *card, int scard)
{ int i,s=fac(scard);
for (i=0; i<dimcard; i++) s/=fac(card[i]);
return s;
}

void initpermsys(int dimperm, int dimcard, int *card, int *scard,
int *nperm)
{ int i,s=0;
for (i=0; i<dimcard; i++)
{ if (card[i]<=0) error(1);
s+=card[i];
}
// We assume 32 bit int
if (dimcard<2 || dimperm>12 || dimperm!=s) error(2);
*scard=s; *nperm=numperm(dimcard,card,s);
printf("valid range of permindex: 0 .. %d\n",*nperm-1);
}

void findpermsub(int permindex, int *perm, int dimcard, int *card,
int scard, int nperm)
{ int is,iss,np;
np=nperm;
for (is=dimcard-1; is>=0; is--) if (card[is]>0)
{ np-=(nperm*card[is])/scard;
if (np<=permindex)
{ iss=is; break;
}
}
perm[0]=iss; permindex-=np;
nperm=(nperm*card[iss])/scard; card[iss]--;
if (--scard==0) return;
findpermsub(permindex,perm+1,dimcard,card,scard,nperm);
}

// Given an index permindex, find the corresponding permutation.
void findperm(int permindex, int *perm, int dimcard, int *card,
int *cardsub, int scard, int nperm)
{ int is;
if (permindex<0 || permindex>=nperm) error(3);
for (is=0; is<dimcard; is++) cardsub[is]=card[is];
findpermsub(permindex,perm,dimcard,cardsub,scard,nperm);
}

void checkperm(int dimperm, int *perm, int dimcard, int *card,
int *cardsub)
{ int is,i;
for (i=0; i<dimperm; i++) cardsub[i]=0;
for (i=0; i<dimperm; i++)
{ is=perm[i];
if (is<0 || is>=dimcard) error(4);
cardsub[is]++;
}
for (is=0; is<dimcard; is++) if (card[is]!=cardsub[is]) error(5);
}

void findindexsub(int *permindex, int *perm, int *card, int scard,
int nperm)
{ int is,p0=perm[0];
for (is=0; is<p0; is++) if (card[is]>0)
{ *permindex+=(nperm*card[is])/scard;
}
nperm=(nperm*card[p0])/scard;
if (--scard==0) return;
card[p0]--;
findindexsub(permindex,perm+1,card,scard,nperm);
}

// Given a permutation perm[*], find its index in the lexicographic
// ordering.
void findindex(int *permindex, int dimperm, int *perm, int dimcard,
int *card, int *cardsub, int scard, int nperm)
{ int is;
checkperm(dimperm,perm,dimcard,card,cardsub);
*permindex=0;
for (is=0; is<dimcard; is++) cardsub[is]=card[is];
findindexsub(permindex,perm,cardsub,scard,nperm);
}


// Test program.
// Example: 2 oranges, 1 apple, 1 banana (designated by 0, 1, 2
// in perm[*])

void printperm(int dimperm, int *perm)
{ int i;
for (i=0; i<dimperm; i++) printf("%3d",perm[i]); printf("\n");
}

#define dimcard 3
int cardsub[dimcard],card[dimcard]={2,1,1};

#define dimperm 4
int perm[dimperm];

int main()
{ int i,permindex,scard,nperm;
initpermsys(dimperm,dimcard,card,&scard,&nperm);
for (i=0; i<nperm; i++)
{ findperm(i,perm,dimcard,card,cardsub,scard,nperm);
printperm(dimperm,perm);
findindex(&permindex,dimperm,perm,dimcard,card,cardsub,scard,nperm);
if (i!=permindex)
{ printf("programming error: %d %d\n",i,permindex);
exit(2);
}
}
return 0;
}
First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4
Prev: Draft paper submission deadline is extended: ISP-10, Orlando, USA
Next: Request to review OWASP ESAPI crypto