derangement: code review request

[Joe Wright]

At the risk of developing a larger reputation as a dullard, I would like to
continue this discussion at a level that I can understand. The following
code, I believe, produces exactly the behavior--with good style--that we're
looking for from K&R2 §5.

#include <stdio.h>
void swap(int *px, int *py);
int main(void){
int a = 3;
int b = 5;
swap(&a, &b);
printf ("a equals %d\n", a);
printf ("b equals %d\n", b);
return 0;
}
void swap(int *px, int *py){
int tmp = *px;
*px = *py;
*py = tmp;
}

Q1) Does anyone think that this is lacking in any fashion?
Q2) If prototype and declaration are not the same thing, then which line
number is which?

MPJ

P.S. I've read this thread, but I simply need to back up a bit.

#include <stdio.h>

void swap(int*, int*); /* This is a prototype and declaration */

int main(void) {
int a = 3;
int b = 5;
swap(&a, &b);
printf("a equals %d\n", a);
printf("b equals %d\n", b);
return 0;
}

void swap(int *px, int *py) { /* This is the definition */
int tmp = *px;
*px = *py;
*py = tmp;
}

 

[Dan Pop]

void swap(int*, int*); /* This is a prototype and declaration */

Incorrect: prototype is not a standalone concept in C. The correct
comment is: "This is a prototype declaration".

You can have prototype declarations and prototype definitions, but you
can't have standalone prototypes.

Dan

 

[Dan Pop]

Minneslowta except to show that you're type A. To the topic though, would I
not be fine calling those prototypes *coconuts or *Krijn OR indeed would
void swap(int *a, int *a); ^ ^
work swell? MPJ

It wouldn't. Even if the identifiers used in a function prototype
declaration are otherwise ignored, you're still not allowed to redeclare
an identifier at function prototype scope. Unless their names are
supposed to convey some useful information to the reader, you can simply
omit them in a function declaration:

void swap(int *, int *);

is just fine. If you insist on using identifiers, just use different
identifiers:

void swap(int *coconuts, int *Krijn);

These identifiers don't have to match the ones used in the function
definition, but it is considered good programming practice to have the
same identifiers in the declaration and in the definition (if you choose
to use identifiers in the declaration).

In programs where you need to swap variables of more than one type,
using functions, this function should be named int_swap() or iswap().

And, since you're relatively new here: arguing with Mark McIntyre is
generally neither fun nor instructive; he's our resident idiot.

Dan

 

[Merrill & Michele]

In <[email protected]> "Merrill & Michele"

It wouldn't. Even if the identifiers used in a function prototype
declaration are otherwise ignored, you're still not allowed to redeclare
an identifier at function prototype scope. Unless their names are
supposed to convey some useful information to the reader, you can simply
omit them in a function declaration:

void swap(int *, int *);

is just fine. If you insist on using identifiers, just use different
identifiers:

void swap(int *coconuts, int *Krijn);

These identifiers don't have to match the ones used in the function
definition, but it is considered good programming practice to have the
same identifiers in the declaration and in the definition (if you choose
to use identifiers in the declaration).

It is not considered the best of style by me. It makes code 'overcody' to
repeat identifiers. When I see a bunch of fruit-flying Dutchmen, then I
know that this is where I was telling my self something.

In programs where you need to swap variables of more than one type,
using functions, this function should be named int_swap() or iswap().

That's still down the road a bit, but this puts you in the fairway.

And, since you're relatively new here: arguing with Mark McIntyre is
generally neither fun nor instructive; he's our resident idiot.

Well then he's closer to my abilities than I thought. MPJ

 

[Keith Thompson]

In <[email protected]> Joe Wright


Incorrect: prototype is not a standalone concept in C. The correct
comment is: "This is a prototype declaration".

You can have prototype declarations and prototype definitions, but you
can't have standalone prototypes.

C99 6.2.1p2 says:

A _function prototype_ is a declaration of a function that
declares the types of its parameters.

Since "function prototype" is in italics, this is the definition of
the term. We can assume, I think, that "prototype" is equivalent to
"function prototype"; the standard uses the term "prototype" by itself
in this sense in a number of places. A prototype is a kind of
declaration.

So Joe Wright is quite correct. This:

void swap(int*, int*);

is a declaration; it's also a prototype.

It would also be correct to say that it's a "prototype declaration";
the standard uses that phrase in an example in 6.9.1p14.
(Interestingly, it uses the term to refer to a function definition
that includes a prototype.)

 

[Keith Thompson]

And, since you're relatively new here: arguing with Mark McIntyre is
generally neither fun nor instructive; he's our resident idiot.

Dan Pop is our resident curmudgeon. He seems to enjoy insulting
people for some reason. I suggest you ignore his abuse and decide for
yourself who's an idiot and who isn't.

 

[Merrill & Michele]

Dan Pop is our resident curmudgeon. He seems to enjoy insulting
people for some reason. I suggest you ignore his abuse and decide for
yourself who's an idiot and who isn't.

Mr. Pop's brilliant and passionate to a fault. Let's not hold it against
him. MPJ

 

[Joe Wright]

Incorrect: prototype is not a standalone concept in C. The correct
comment is: "This is a prototype declaration".

You can have prototype declarations and prototype definitions, but you
can't have standalone prototypes.

Dan

You're a tough judge my friend. I wonder, may I ask you for Chapter
and Verse with any reference to 'standalone prototypes' or any
indication that the word 'prototype' is not a noun (English: the
name of a thing.) in its own right?

In N869 every reference to 'prototype' has it a noun. The word
'standalone' does not occur even once.

 

[Dan Pop]

You're a tough judge my friend. I wonder, may I ask you for Chapter
and Verse with any reference to 'standalone prototypes' or any
indication that the word 'prototype' is not a noun (English: the
name of a thing.) in its own right?

In N869 every reference to 'prototype' has it a noun. The word
'standalone' does not occur even once.

Now, check the *definition* of "prototype" in the C standard and you
might get the point.

Dan

 

[Dan Pop]

C99 6.2.1p2 says:

A _function prototype_ is a declaration of a function that
declares the types of its parameters.

Since "function prototype" is in italics, this is the definition of
the term. We can assume, I think, that "prototype" is equivalent to
"function prototype"; the standard uses the term "prototype" by itself
in this sense in a number of places. A prototype is a kind of
declaration. ^^^^^^^^^^^^^^^^^^^^^^^^

^^^^^^^^^^^
Precisely my point.

So Joe Wright is quite correct. This:

void swap(int*, int*);

is a declaration; it's also a prototype.

It is a prototype declaration. If saying "this is a declaration and a
declaration" makes sense in English, then Joe Wright is quite correct.

Dan

 

[Dan Pop]

(e-mail address removed) (Dan Pop) writes:
[...]

And, since you're relatively new here: arguing with Mark McIntyre is
generally neither fun nor instructive; he's our resident idiot.

Dan Pop is our resident curmudgeon. He seems to enjoy insulting
people for some reason. I suggest you ignore his abuse and decide for
yourself who's an idiot and who isn't.

Anyone who attempted to argue with Mark McIntyre on a rational basis
reached the same conclusion, usually expressed under the euphemism
"you cannot read". The last one I remember was P.J. Plauger.

Dan

 

[Merrill & Michele]

(e-mail address removed) (Dan Pop) writes:
[...]

And, since you're relatively new here: arguing with Mark McIntyre is
generally neither fun nor instructive; he's our resident idiot.

Dan Pop is our resident curmudgeon. He seems to enjoy insulting
people for some reason. I suggest you ignore his abuse and decide for
yourself who's an idiot and who isn't.

Anyone who attempted to argue with Mark McIntyre on a rational basis
reached the same conclusion, usually expressed under the euphemism
"you cannot read". The last one I remember was P.J. Plauger.

True or not, at least your insults are straightforward, unlike the
henpecking that some equate to criticism.

I'm going to shuffle with my derangement code now. The thing I can't figure
out is how to pass the address of buysfor[0] back to the prog that called
it. Pointers have me tied up in knots right now. MPJ

 

[Lawrence Kirby]

On Wed, 10 Nov 2004 22:37:41 -0600, Merrill & Michele wrote:

....

/* initialize and permute */
for (i = 0; i < FAMSIZ; ++ i) buysfor = i;
m = 0;
while (m < FAMSIZ){
t = rand();
if (t > topnum) continue;
n = t % FAMSIZ;
swap (&buysfor[m] , &buysfor[n]);
++ m;
}

This clearly doesn't guarantee a derangement, but with a small
modification it can. This is very similar to a naive shuffle
algorithm, and the fix is essentially the same.

/*out to console*/
putchar('\n');
for (i = 0;i < FAMSIZ; i ++) printf("%3d",i);
putchar('\n');
for (i = 0;i < FAMSIZ; i ++) printf("%3d",buysfor);
putchar('\n');

/* remove collisions */
for (m = 0; m < FAMSIZ; ++ m){
while (buysfor[m] == m){
t = rand();
if (t > topnum) continue;
n = t % FAMSIZ;
if ((n == m) || (buysfor[m] == n)) continue;
swap (&buysfor[m] , &buysfor[n]);
}
}

Well I guess that works. But can you be sure that

1. this could generate every possible derangement? Maybe,
but prove it.

2. Every possible derangement is equally likely? Probably not,
even with the work you did with topnum.

....

I think I finally got it. I couldn't get my head around the do-while
control loops. MPJ

Try this:



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

#define FAMSIZ 20 /* between 2 and 2,000 */

static int randrange(int range);

int main(void){
int buysfor[FAMSIZ];
int i;

/* get vanilla rand started well */

srand((unsigned)time(NULL));
for (i = 0; i < 9; ++i) (void)rand();

/* derangement */

buysfor[0] = 0;
for (i = 1; i < FAMSIZ; ++i) {
int t = randrange(i);
buysfor = buysfor[t];
buysfor[t] = i;
}

/* out to console */

putchar('\n');

for (i = 0;i < FAMSIZ; i++) printf("%3d",i);
putchar('\n');

for (i = 0;i < FAMSIZ; i++) printf("%3d",buysfor);
putchar('\n');

return 0;
}

/* Wrapper for rand() which returns a random number
0 <= number < range where each value is equally likely
as long as rand() returns values between 0 and RAND_MAX
with equal probability. range <= RAND_MAX.
*/

static int randrange(int range)
{
int num, high;

high = RAND_MAX - RAND_MAX % range;
while ((num = rand()) >= high)
;
return (num / (RAND_MAX / range));

}

 

[Keith Thompson]

Anyone who attempted to argue with Mark McIntyre on a rational basis
reached the same conclusion, usually expressed under the euphemism
"you cannot read". The last one I remember was P.J. Plauger.

Hmm. I just did a groups.google.com search for Mark's postings to
comp.lang.c and read a more or less random sampling of the recent
ones. Everything I read seemed perfectly sensible.

I'm sure I've read a lot of Mark's articles in the past, but I haven't
kept mental track of who posted what, so I can't really judge him on
that basis.

Perhaps he's improved recently, or perhaps I picked a
non-representative sample. In any case, I'll continue to judge each
article on its own merits and not (except for a few special cases) on
the basis of anyone's opinion of the poster. (The "special cases" do
not include anyone participating in, or mentioned in, this thread.)

 

[Mark McIntyre]

Mr. Pop's brilliant and passionate to a fault.

True. I do wish he'd stick to C tho.

Let's not hold it against him.

On the other hand, he's very very egotistical and vindictive. Treat
anything he says about anyone else with a pinch of salt.

 

[Mark McIntyre]

(e-mail address removed) (Dan Pop) writes:
[...]

Anyone who attempted to argue with Mark McIntyre on a rational basis
reached the same conclusion, usually expressed under the euphemism
"you cannot read". The last one I remember was P.J. Plauger.

Hmm. I just did a groups.google.com search for Mark's postings to
comp.lang.c and read a more or less random sampling of the recent
ones. Everything I read seemed perfectly sensible.

I expect he's thinking of the "do we cast malloc" debate that went on 10
months ago, during which many of us got a bit excited at PJ's apparent
position that casting malloc was perfectly alright. I believe at one point
PJ even seemed to be asserting that the cast was *necessary* in case there
were no valid conversion from void* to some other pointer type. Hmm.

T'would be nice tho if other people would stop holding grudges, and grow
up.

 

[Merrill & Michele]

On Wed, 10 Nov 2004 22:37:41 -0600, Merrill & Michele wrote:

...

/* initialize and permute */
for (i = 0; i < FAMSIZ; ++ i) buysfor = i;
m = 0;
while (m < FAMSIZ){
t = rand();
if (t > topnum) continue;
n = t % FAMSIZ;
swap (&buysfor[m] , &buysfor[n]);
++ m;
}

This clearly doesn't guarantee a derangement, but with a small
modification it can. This is very similar to a naive shuffle
algorithm, and the fix is essentially the same.

/*out to console*/
putchar('\n');
for (i = 0;i < FAMSIZ; i ++) printf("%3d",i);
putchar('\n');
for (i = 0;i < FAMSIZ; i ++) printf("%3d",buysfor);
putchar('\n');

/* remove collisions */
for (m = 0; m < FAMSIZ; ++ m){
while (buysfor[m] == m){
t = rand();
if (t > topnum) continue;
n = t % FAMSIZ;
if ((n == m) || (buysfor[m] == n)) continue;
swap (&buysfor[m] , &buysfor[n]);
}
}

Well I guess that works. But can you be sure that

1. this could generate every possible derangement? Maybe,
but prove it.

2. Every possible derangement is equally likely? Probably not,
even with the work you did with topnum.

...

I think I finally got it. I couldn't get my head around the do-while
control loops. MPJ

Try this:



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

#define FAMSIZ 20 /* between 2 and 2,000 */

static int randrange(int range);

int main(void){
int buysfor[FAMSIZ];
int i;

/* get vanilla rand started well */

srand((unsigned)time(NULL));
for (i = 0; i < 9; ++i) (void)rand();

/* derangement */

buysfor[0] = 0;
for (i = 1; i < FAMSIZ; ++i) {
int t = randrange(i);
buysfor = buysfor[t];
buysfor[t] = i;
}

/* out to console */

putchar('\n');

for (i = 0;i < FAMSIZ; i++) printf("%3d",i);
putchar('\n');

for (i = 0;i < FAMSIZ; i++) printf("%3d",buysfor);
putchar('\n');

return 0;
}

/* Wrapper for rand() which returns a random number
0 <= number < range where each value is equally likely
as long as rand() returns values between 0 and RAND_MAX
with equal probability. range <= RAND_MAX.
*/

static int randrange(int range)
{
int num, high;

high = RAND_MAX - RAND_MAX % range;
while ((num = rand()) >= high)
;
return (num / (RAND_MAX / range));

}

I need a little time to digest this. My claim is that for most values of
FAMSIZ (range), we need to toss out some values for rand. My opinion as to
how many we toss out has differed with others by one. This difference can
be reconciled by comparing with strict inequality, but I see you have a >=.
(I can keep typing til the boy finishes his bottle.) RAND_MAX is usually 0
x 7fff = 32767 and FAMSIZ is usually going to be 52. That would make high =
32767 - 32767 % 52 = 32767 - 7 = 32760 . For kicks and giggles, let's
doublecheck. 32760 % 52 = 0 . I just don't see how it is you don't have
one too many zeros because rand() is fine with returning a zero.

As far as program control goes, I'm completely lost. You pass range, which
is FAMSIZ in my code and rely on the peculiarities of c to have an integer
returned. I'd prattle on about the things I don't get, but .... MPJ

 

[Dan Pop]

(e-mail address removed) (Dan Pop) writes:
[...]

Anyone who attempted to argue with Mark McIntyre on a rational basis
reached the same conclusion, usually expressed under the euphemism
"you cannot read". The last one I remember was P.J. Plauger.

Hmm. I just did a groups.google.com search for Mark's postings to
comp.lang.c and read a more or less random sampling of the recent
ones. Everything I read seemed perfectly sensible.

I expect he's thinking of the "do we cast malloc" debate that went on 10
months ago, during which many of us got a bit excited at PJ's apparent
position that casting malloc was perfectly alright.

Nope, I'm thinking of a more recent one, on a different topic.

Dan

 

[Lawrence Kirby]

....

buysfor[0] = 0;
for (i = 1; i < FAMSIZ; ++i) {
int t = randrange(i);
buysfor = buysfor[t];
buysfor[t] = i;
}

This looks like a case of premature publication by me.
I believe this does always produce a derangement, but it
doesn't produce all possible derangements because in some
cases an order N derangement can't be constructed from an
order N-1 derangement in this way (eg. 2 3 0 1 would have
to be constructed from 2 1 0 which isn't a derangement).

So it fails to meet my conditions. Those can be met with
the method of: perform a random shuffle, repeat IN FULL while
the result is not a derangement. The random shuffle needs
to be implemented correctly to make all permutations equally
likely.

An algorithm that meets my conditions though direct
construction of a derangement (as I attempted) looks to be
more "interesting".

....

I need a little time to digest this. My claim is that for most values of
FAMSIZ (range), we need to toss out some values for rand. My opinion as to
how many we toss out has differed with others by one. This difference can
be reconciled by comparing with strict inequality, but I see you have a >=.
(I can keep typing til the boy finishes his bottle.) RAND_MAX is usually 0
x 7fff = 32767 and FAMSIZ is usually going to be 52. That would make high =
32767 - 32767 % 52 = 32767 - 7 = 32760 . For kicks and giggles, let's
doublecheck. 32760 % 52 = 0 . I just don't see how it is you don't have
one too many zeros because rand() is fine with returning a zero.

After the while loop you will have a value between 0 and 32759 inclusive
i.e. 32760 distinct values. 32767/52 is 630 and 630*52 is 32760. The range
of values after the loop is divided into 52 subranges of 630 values, the
final division by 630 maps 0-629 onto 0, 630-1259 onto 1, ..., 32130-32759
onto 51.

As far as program control goes, I'm completely lost. You pass range,
which is FAMSIZ in my code

It isn't in my code, which is key point to why it generates derangements
directly. randrange(range) is just a drop-in replacement for (rand() %
range), but it is potentially better behaved in the numbers it generates.

and rely on the peculiarities of c to have an
integer returned. I'd prattle on about the things I don't get, but ....

Well it relies on simple C constructs, I'm not sure what peculiarities you
are referring to although the calculation is perhaps non-obvious. It is
perhaps not *quite* as efficient as it could be when mathematically
RAND_MAX+1 is exactly divisible by range, but calculations involving
RAND_MAX+1 can be awkward in C's integer arithmetic so a simplification
has been made.

Lawrence

 

[Merrill & Michele]

...

buysfor[0] = 0;
for (i = 1; i < FAMSIZ; ++i) {
int t = randrange(i);
buysfor = buysfor[t];
buysfor[t] = i;
}

This looks like a case of premature publication by me.
I believe this does always produce a derangement, but it
doesn't produce all possible derangements because in some
cases an order N derangement can't be constructed from an
order N-1 derangement in this way (eg. 2 3 0 1 would have
to be constructed from 2 1 0 which isn't a derangement).

So it fails to meet my conditions. Those can be met with
the method of: perform a random shuffle, repeat IN FULL while
the result is not a derangement. The random shuffle needs
to be implemented correctly to make all permutations equally
likely.

An algorithm that meets my conditions though direct
construction of a derangement (as I attempted) looks to be
more "interesting".

The only way I could get it was to start with any map of a set onto itself,
permute randomly and remove collisions in separate steps.

After the while loop you will have a value between 0 and 32759 inclusive
i.e. 32760 distinct values. 32767/52 is 630 and 630*52 is 32760. The range
of values after the loop is divided into 52 subranges of 630 values, the
final division by 630 maps 0-629 onto 0, 630-1259 onto 1, ..., 32130-32759
onto 51.

If you have 0 through 32759 after the while loop, then you're good to go. I
don't see how that is achieved with while((num = rand()) >= high), but the
operative part of the sentence is "I don't see."

It isn't in my code, which is key point to why it generates derangements
directly. randrange(range) is just a drop-in replacement for (rand() %
range), but it is potentially better behaved in the numbers it generates.


Well it relies on simple C constructs, I'm not sure what peculiarities you
are referring to although the calculation is perhaps non-obvious.

Those simple C constructs send me scrambling for a textbook. Off to Ted's
MPJ