Prev: now open all blocked site with our proxy
Next: ANN: Seed7 Release 2010-01-03
From: Thad Smith on 4 Jan 2010 00:04
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
>
> 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?

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
From: Gene on 4 Jan 2010 09:03
On Jan 3, 12:23 pm, Patricia Shanahan <p...(a)acm.org> wrote:
> 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
>
> >http://stackoverflow.com/questions/1506078/fast-permutation-number-pe...
>
> > 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.



From: Thad Smith on 4 Jan 2010 23:34
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
>
> 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?

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
From: Mok-Kong Shen on 6 Jan 2010 10:48
Thad Smith wrote:

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

Thanks in advance.

M. K. Shen
From: Gene on 13 Jan 2010 13:32
On Jan 4, 11:34 pm, Thad Smith <ThadSm...(a)acm.org> wrote:
> 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
>
> >http://stackoverflow.com/questions/1506078/fast-permutation-number-pe...
>
> > 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?
>
> 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;
>
> }

This is a nice piece of work. Thanks for sharing it.
First  |  Prev  |  Next  |  Last
Pages: 1 2 3
Prev: now open all blocked site with our proxy
Next: ANN: Seed7 Release 2010-01-03