Prev: now open all blocked site with our proxy
Next: ANN: Seed7 Release 2010-01-03
From: Mok-Kong Shen on 19 Jan 2010 18:06
Mok-Kong Shen wrote:
[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); }
}


From: James Dow Allen on 20 Jan 2010 14:13
On Jan 20, 6:06 am, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote:
> ... 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.
> [snip]

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
First  |  Prev  | 
Pages: 1 2 3
Prev: now open all blocked site with our proxy
Next: ANN: Seed7 Release 2010-01-03