Q: Indexing a special kind of permutations
Mok-Kong Shen
Permutations of n different objects can be ordered and thus mapped to
numbers. There are good algorithms for doing the conversions. See
http://stackoverflow.com/questions/1506078/fast-permutation-number-permutation-mapping-algorithms
If there are only two kinds of objects (say, black and white), with n
even and n/2 objects of each kind, are there good algorithms of doing
the same?
Thanks,
M. K. Shen
Patricia Shanahan
This is equivalent to the problem of specifying a set of n/2 unique
numbers each in the range from 1 through n. Regard the selected set as
the index values for the black elements. Any index not in the set gets a
white element.
There are n choices for the first number, n-1 choices for the second
one, ..., 1+n/2 choices for the last of the n/2 selected numbers.
Patricia
Mok-Kong Shen
Sorry for my poor knowledge, I don't yet quite understand you. For
exalmple, with n=3 (and 1/0 for black/white), how does the entire
ordering look like (giving a part of it is sufficient) and how does
one compute, e.g. the index for 0 1 1 0 0 1?
Thanks in advance.
M. K. Shen
Patricia Shanahan
Sorry, I should have been clearer. I'm not giving a complete solution,
just an idea for an approach that might work, when combined with ideas
from the link you posted.
Patricia
Mok-Kong Shen
I am clueless and should appreciate it, if someone could kindly give
me a bit more help.
M. K. Shen
Thad Smith
I wrote some code for this a while back. I don't recall the technique,
but I'll look for code and give a detailed reply later.
It was a very general routine that lets the caller specify the number of
elements for each distinct item, plus the minimum and maximum number of
elements in the set of permutations (for example: 3 A's, 2 B's, 5 C's,
all permutations with 6 to 10 elements). It then maps an index to a
permutation or vice-versa.
--
Thad
Gene
> Mok-Kong Shen wrote:
>
> > Permutations of n different objects can be ordered and thus mapped to
> > numbers. There are good algorithms for doing the conversions. See
>
>
> > If there are only two kinds of objects (say, black and white), with n
> > even and n/2 objects of each kind, are there good algorithms of doing
> > the same?
>
> This is equivalent to the problem of specifying a set of n/2 unique
> numbers each in the range from 1 through n. Regard the selected set as
> the index values for the black elements. Any index not in the set gets a
> white element.
>
> There are n choices for the first number, n-1 choices for the second
> one, ..., 1+n/2 choices for the last of the n/2 selected numbers.
>
> Patricia
Yes! Except that I think after you've made the first choice, say it's
k_1, then the next choice must be k_2 in[1..k_1), then k_3 in [1..k_2)
and so forth. Otherwise there's more than one way to get each
combination, which is what we're really computing an ordering on, just
as you say: n choose n/2.
Thad Smith
Here is C code to compute a permutation from an index and the number of each
unique element, along with a test driver. For example
permx 3 2 4
computes permutation 3 using 2 1's and 4 2's. The permutations are in lexical
order, with permutation 0 being the lowest value.
You could extend the range by using unsigned long long or other extended integer
type.
/* PERMX.C - Compute permutation index from permutation and inverse.
**
** These routines compute a permutation index from a given full permutation
** using all elements of a multi-set (duplicate items allowed).
**
** 031130 Thad Smith - original version.
*/
#include <stdlib.h>
typedef unsigned char tElem; /* element value for permutation, 0..max */
typedef unsigned long tPermX; /* permutation index, 0..max */
/* Function: XtoPerm
** Description: This function computes the permutation from a permutation
** index. The permutations are in lexical order.
** On entry:
** On exit: return value = status (see return comment)
** ret=0: perm[] contains permutation.
*/
int /* 0=perm returned, 1=index out of range,
** 2=overflow, 3=telems mismatch */
XtoPerm (
tElem perm[], /* resulting permutation [0..telems-1] */
tPermX permx, /* permutation index */
size_t nelems, /* number of unique elements in set */
size_t telems, /* total number of elements in set */
int elemCount[] /* elemCount[i] = number of copies of elements i
** in the set, i=0..nelems-1 */
) {
tPermX tnp; /* total number of permutations */
tPermX ntnp; /* temp px */
tPermX lcc; /* number of permutations for remaining elements
** after item i chosen */
tPermX plcc; /* prev value of lcc */
int te; /* total number of elements */
int c; /* single element count */
int r; /* return code */
int i, j; /* temp */
/* compute total number of permutations */
tnp = 1;
te = 0;
for (i=0; i < nelems; i++) {
c = elemCount[i];
for (j=1; j <= c; j++) {
te++;
ntnp = tnp * te;
if (ntnp/te < tnp) return 2; /* overflow */
tnp = ntnp / j;
}
}
if (te != telems) return 3; /* count mismatch */
if (permx >= tnp) return 1; /* index too high */
/* Find the first element */
plcc = lcc = 0;
for (i=0; i < nelems; i++) {
c = elemCount[i];
if (c == 0) continue;
lcc += (double)tnp*c/telems;
if (lcc > permx) {
/* assign first element */
elemCount[i]--;
perm[0] = i;
r = XtoPerm (perm+1,permx-plcc,nelems,telems-1,elemCount);
elemCount[i]++;
return r;
}
plcc = lcc;
}
return 0;
}
#include <stdio.h>
int main (int argc, char *argv[]) {
int nelems, telems;
tPermX px; /* specified perm index */
int i;
int s; /* return status */
int count[20];
tElem perm[100]; /* permutation */
if (argc > 3 && argc < 22) {
px = atol (argv[1]);
nelems = argc-2;
telems = 0;
for (i=0; i < argc-2; i++) {
count[i] = atoi (argv[i+2]);
if (count[i] <= 0) goto help;
telems += count[i];
if (telems > sizeof perm / sizeof (perm[0])) goto help;
}
s = XtoPerm (perm, px, nelems, telems, count);
printf ("stat=%d, perm:", s);
for (i=0; i < telems; i++) {
printf ("%d ", (int)perm[i]+1);
}
printf ("\n");
} else {
help:
printf ("Use: permx index n1 n2 ... nn\n"
" permx = index of permutation\n"
" nx = number of copies of item x in set\n");
return 1;
}
return 0;
}
--
Thad
Mok-Kong Shen
> Here is C code to compute a permutation from an index and the number of
> each unique element, along with a test driver. For example
> permx 3 2 4
> computes permutation 3 using 2 1's and 4 2's. The permutations are in
> lexical order, with permutation 0 being the lowest value.
[snip]
I have tried your code. It's excellent. I also need however the
code for conversion from a permutation to its index. Please be
kind enough to supply it too.
Gene
> Mok-Kong Shen wrote:
>
> > Permutations of n different objects can be ordered and thus mapped to
> > numbers. There are good algorithms for doing the conversions. See
>
This is a nice piece of work. Thanks for sharing it.
Mok-Kong Shen
[snip]
> If there are only two kinds of objects (say, black and white), with n
> even and n/2 objects of each kind, are there good algorithms of doing
> the same?
I have now a code that does that, where p(n1,n2)=(n1+n2)!/(n1!*n2!).
Set n1=n2=n/2 when invoking either procedure below. For indications of
eventual errors or possibilities of improvements I should be grateful.
M. K. Shen
-----------------------------------------------------------------
typedef unsigned long int ULI;
ULI index(int *perm, int n1, int n2)
{ if (n1==0 || n2==0) return 0;
if (perm[0]==0) return index(perm+1,n1-1,n2);
else return p(n1-1,n2)+index(perm+1,n1,n2-1);
}
void genperm(int *perm, ULI index, int n1, int n2)
{ int i;
ULI u;
if (index==0)
{ for (i=0; i<n1; i++) perm[i]=0; for (i=0; i<n2; i++) perm[n1+i]=1;
return; }
u=p(n1-1,n2);
if (index<u) { perm[0]=0; genperm(perm+1,index,n1-1,n2); }
else { perm[0]=1; genperm(perm+1,index-u,n1,n2-1); }
}
James Dow Allen
> ... I have now a code that does that, where p(n1,n2)=(n1+n2)!/(n1!*n2!).
> ... For indications of
> eventual errors or possibilities of improvements I should be grateful.
My suggestions:
1. You don't give details of p(), which may be
important for speed. (And I'd give it a
name which is longer or capitalized or both.)
2. If the index is too large the code does not
fail gracefully, and may even segfault.
A minimum workaround for this is to add
assert(index < p(n1, n2));
or even
index %= p(n1, n2);
at the beginning of genparm().
3. Good: genparm() is set up "neatly" so that
a good compiler may always use tail-recursion,
instead of actually re-invoking genparm().
(I personally would make this tail-recursion
more explicit, perhaps just coding it as a loop.)
4. You use index() as a function name, and as
argument name in another function in the same module.
I'd avoid this. I'd avoid use of "index"
altogether, as this is a reserved function-name in
The Library We Believe In(tm), regardless of
whether it is reserved in The Standard(tm).
5. The arrangement of white space in your
C code is undesirable. Switch to True Style.
6. When providing code for perusal it is
usually best, when practical, to provide a complete
standalone unit. Here that would mean, supplying
the p() function and at least a trivial main().
James Dow Allen