derangement: code review request

[Merrill & Michele]

A derangement is a mapping of a set onto itself leaving no element fixed. I
realized that that was what I was programming when I was asked to randomly
determine who buys presents for whom this year in my wife's family.
Obviously, one does not buy for himself. The code is followed by some
questions.

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

#define fam_size 20
//must be between 2 and randmax minus one

int main(void)
{
int i,t,a[fam_size],b[fam_size],notdone1,notdone2;
int m,j;
time_t timer;
long counter, top_num;

//determine good random numbers
srand(time(&timer));
top_num=RAND_MAX-(RAND_MAX%fam_size)-1;

//initialize arrays

for (i=0;i<fam_size;i++){
a=b=0;
}
//main control structures
counter=0;
notdone1=1;

while(notdone1)
{
//ignore this first while loop
//this will ultimately play with
//any given derangement to see if it's
//suitable
for(j=0;j<fam_size;j++)

{
notdone2=1;
while(notdone2){

++counter;
t=rand();
m=t%fam_size;
if ((b[m]==0)&&(m!=j)&&(t<=top_num)){
a[j]=m;
b[m]=1;
notdone2=0;
}
else {
notdone2=1;
}
/* bad luck checker
starts us over except for counter*/
if ((j==fam_size-1)&&(b[j]==0)){
for (i=0;i<fam_size;i++){
a=b=0;
}
notdone2=0;
j=-1;
}
//end notdone2 while
}
//end j loop
}

for(i=0;i<fam_size;i++)
printf("%d %d\n",i,a);
printf("counter= %d\n",counter);
notdone1=0;
//end outer while
}
return 0;
}

Q1) Is this code ANSI-compliant and C99-compliant?

Q2) The obvious style shortcomings are mostly a product of my IDE looking
different than what is copy/pasted (no Mr. Mair, I am not ready to be weened
off the tit). What style shortcomings do you see that don't involve
spacing?

Q3) There's at least one major design flaw. It follows the remark "bad luck
checker" and covers the event that the final element can only be mapped to
itself, which happens 1 out of every fam_size times that the program is run.
Any ideas how to make that less hideous?

++thanks. MPJ
----------------------------------
*OT* I had been teaching my nine-month-old during feedings:

"My big eater
hates Derek Jeter"

I guess I'll have to find new material *end OT*

 

[Pedro Graca]

[newbie -- just one answer]

Merrill & Michele wrote:

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

#define fam_size 20
//must be between 2 and randmax minus one

int main(void)
{
int i,t,a[fam_size],b[fam_size],notdone1,notdone2;
int m,j;
time_t timer;
long counter, top_num;

^^^^

printf("counter= %d\n",counter);

counter is a long, it needs %ld in the format for printf()

notdone1=0;
//end outer while
}
return 0;
}

Q1) Is this code ANSI-compliant and C99-compliant?

AFAICT // comments aren't ANSI-compatible

 

[Eric Sosman]

A derangement is a mapping of a set onto itself leaving no element fixed. I
realized that that was what I was programming when I was asked to randomly
determine who buys presents for whom this year in my wife's family.
Obviously, one does not buy for himself. The code is followed by some
questions.

[code snipped; see up-thread]

Q1) Is this code ANSI-compliant and C99-compliant?

Q2) The obvious style shortcomings are mostly a product of my IDE looking
different than what is copy/pasted (no Mr. Mair, I am not ready to be weened
off the tit). What style shortcomings do you see that don't involve
spacing?

Q3) There's at least one major design flaw. It follows the remark "bad luck
checker" and covers the event that the final element can only be mapped to
itself, which happens 1 out of every fam_size times that the program is run.
Any ideas how to make that less hideous?

I was going to attempt Q1 and Q2, but I'm still
suffering from post-Game-7 fogginess and can't seem to
summon any enthusiasm for studying the implementation
of an inferior algorithm. Sorry about that -- I'm not
trying to dictate your algorithm choice, but I'm just
unable to maintain interest in it.

Q3 addresses the algorithm selection, and is thus
off-topic here. Nonetheless, let me suggest a different
approach:

- Use just one array indicating who buys for whom.
That is, buys_for == j means that person `i'
buys for person `j'; you seek a permuation such
that buys_for != i for all relevant `i'.

- Initialize the array with any permutation at all;
buys_for = i (even though it doesn't meet your
goal) is fine.

- For each array position, if buys_for == i then
generate a random j != i and exchange buys_for
with buys_for[j]. This exchange[*] always removes
a self-collision and cannot create a new one, so one
pass over the array eliminates all collisions.

[*] In light of some tiresome discussions that crop
up on this group all too frequently, it's interesting to
note that this exchange can be done without a temporary
variable *and* without the XOR hack or any of its kin.
Do you see why?

 

[Merrill & Michele]

Merrill & Michele wrote:
A derangement is a mapping of a set onto itself leaving no element fixed. I
realized that that was what I was programming when I was asked to randomly
determine who buys presents for whom this year in my wife's family.
Obviously, one does not buy for himself. The code is followed by some
questions.

[snip]
:
I was going to attempt Q1 and Q2, but I'm still
suffering from post-Game-7 fogginess and can't seem to
summon any enthusiasm for studying the implementation
of an inferior algorithm. Sorry about that -- I'm not
trying to dictate your algorithm choice, but I'm just
unable to maintain interest in it.

Is the algorithm sufficient and less expensive than a penny to run? I'll
concede that it's less than elegant.

Q3 addresses the algorithm selection, and is thus
off-topic here. Nonetheless, let me suggest a different
approach:

- Use just one array indicating who buys for whom.
That is, buys_for == j means that person `i'
buys for person `j'; you seek a permuation such
that buys_for != i for all relevant `i'.

- Initialize the array with any permutation at all;
buys_for = i (even though it doesn't meet your
goal) is fine.

- For each array position, if buys_for == i then
generate a random j != i and exchange buys_for
with buys_for[j]. This exchange[*] always removes
a self-collision and cannot create a new one, so one
pass over the array eliminates all collisions.

[*] In light of some tiresome discussions that crop
up on this group all too frequently, it's interesting to
note that this exchange can be done without a temporary
variable *and* without the XOR hack or any of its kin.
Do you see why?

Thank you for your attention. I'm not quite there on 'why.' I tried it on
paper with a small family but couldn't get past my blinder about how this
keeps me away from not having an odd man out at the end. I'm going to need
time to actually code this. MPJ

 

[Merrill & Michele]

Merrill & Michele wrote:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define fam_size 20
//must be between 2 and randmax minus one

int main(void)
{
int i,t,a[fam_size],b[fam_size],notdone1,notdone2;
int m,j;
time_t timer;
long counter, top_num;

^^^^

printf("counter= %d\n",counter);

:
counter is a long, it needs %ld in the format for printf()

AFAICT // comments aren't ANSI-compatible

Thank you for your reply. I wasn't sure whether the appellation of newbie
was to apply to you or me, but it is not defined in C. I'll change my
printf. I'm shocked that // is non-conforming. In my head, I have them as
"the old-style c comments." MPJ

 

[Keith Thompson]

"Pedro Graca" wrote: [...]
AFAICT // comments aren't ANSI-compatible

Thank you for your reply. I wasn't sure whether the appellation of newbie
was to apply to you or me, but it is not defined in C. I'll change my
printf. I'm shocked that // is non-conforming. In my head, I have them as
"the old-style c comments." MPJ

"//" comments are supported in C99 and C++, but not in C90. Many
pre-C99 compilers support them as an extension.

It's often considered a bad idea to use "//" comments in code posted
to Usenet. Usenet software often wraps long lines, which is more
likely to break a "//" comments than "/* ... */" comments. (It can
also break string literals, of course.) Even better, keep any posted
code below 72 columns or so.

 

[Pedro Graca]

I wasn't sure whether the appellation of newbie
was to apply to you or me

It was a self-assessment.
I don't call other people newbies (yet -- lol).



There's one more reason to comment code with /* ... */

<code snippet>
/* Comment lines that are too big and span two (or more) lines
when posted to usenet do not generate errors for copy/pasters */

// Comment lines that are too big and span two (or more) lines
when posted to usenet *do* generate errors for copy/pasters

Oops! -- syntax error at 'when'

 

[Dan Pop]

printf. I'm shocked that // is non-conforming. In my head, I have them as
"the old-style c comments." MPJ

They can be considered ancient-style C comments, in the sense that they
were in C's ancestry, the B language, but didn't make their way into C
until C99.

It's safer (for you) to avoid them in code you post here. If someone
else wants to compile your code in ANSI conforming mode, the compiler
must diagnose your comments. Furthermore, it is an excellent idea for
you to compile your code in ANSI conforming mode, until you get to the
point where any deviation from ANSI C is deliberate, rather than
accidental.

Dan

 

[Tim Rentsch]

A derangement is a mapping of a set onto itself leaving no element fixed. I
realized that that was what I was programming when I was asked to randomly
determine who buys presents for whom this year in my wife's family.
Obviously, one does not buy for himself. The code is followed by some
questions.

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

#define fam_size 20
//must be between 2 and randmax minus one

int main(void)
{
int i,t,a[fam_size],b[fam_size],notdone1,notdone2;
int m,j;
time_t timer;
long counter, top_num;

//determine good random numbers
srand(time(&timer));
top_num=RAND_MAX-(RAND_MAX%fam_size)-1;

//initialize arrays

for (i=0;i<fam_size;i++){
a=b=0;
}
//main control structures
counter=0;
notdone1=1;

while(notdone1)
{
//ignore this first while loop
//this will ultimately play with
//any given derangement to see if it's
//suitable
for(j=0;j<fam_size;j++)

{
notdone2=1;
while(notdone2){

++counter;
t=rand();
m=t%fam_size;
if ((b[m]==0)&&(m!=j)&&(t<=top_num)){
a[j]=m;
b[m]=1;
notdone2=0;
}
else {
notdone2=1;
}
/* bad luck checker
starts us over except for counter*/
if ((j==fam_size-1)&&(b[j]==0)){
for (i=0;i<fam_size;i++){
a=b=0;
}
notdone2=0;
j=-1;
}
//end notdone2 while
}
//end j loop
}

for(i=0;i<fam_size;i++)
printf("%d %d\n",i,a);
printf("counter= %d\n",counter);
notdone1=0;
//end outer while
}
return 0;
}

Q1) [omitted, no response here]

Q2) The obvious style shortcomings are mostly a product of my IDE looking
different than what is copy/pasted (no Mr. Mair, I am not ready to be weened
off the tit). What style shortcomings do you see that don't involve
spacing?

The code uses K&R bracing style (braces on the same line as control
keywords) in some places and Berkeley bracing style (braces on lines
by themselves) in other places. There is some evidence that using K&R
bracing style results in fewer program errors, but whether that's true
or not it would be better to pick one style or the other and follow
that exclusively.

A couple of the names use abbreviations as part of the name (eg,
'fam_size'). I recommend using the whole word, and always avoiding
abbreviations. It takes a certain amount of intestinal fortitude to
do this, as the temptation to make exceptions is strong (but don't
give in!). The more I follow this practice the more I see the
benefits. For function local variables, it's common to allow single
letters to be used as "words"; these aren't abbreviations in the
sense meant here.

Using flag variables (notdone1, notdone2) for while loops isn't
necessarily bad style, but usually it's an indicator that something is
wrong somewhere.

Q3) There's at least one major design flaw. It follows the remark "bad luck
checker" and covers the event that the final element can only be mapped to
itself, which happens 1 out of every fam_size times that the program is run.
Any ideas how to make that less hideous?

How about this:

void
generate_random_derangement( unsigned a[], unsigned n ){
unsigned i, j, t, r, r_limit;

r_limit = RAND_MAX - RAND_MAX % n;

for( i = 0; i < n; i++ ) a = i;

for( i = 0; i < n; i++ ){
do {
do r = rand(); while( r >= r_limit );
j = r % n;
if( a != j ){
t = a, a = a[j], a[j] = t;
}
} while( a == i );
}
}

The 'a == i' test guarantees that each element has been swapped to
something other than itself, and the 'a != j' test guarantees that
swaps won't accidentally cause another element to get a bad value.

 

[Dan Pop]

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

#define fam_size 20

Write macro names in all caps. Reserve lower case for object and function
names.

//must be between 2 and randmax minus one

// comments are syntax errors in ANSI C. The sequence //* has different
semantics in ANSI C vs C99.

int main(void)
{
int i,t,a[fam_size],b[fam_size],notdone1,notdone2;

a and b are misnamed. Reserve one letter identifiers to loop counters
and temporary variables.

int m,j;
time_t timer;
long counter, top_num;

//determine good random numbers
srand(time(&timer));

Make it srand(time(NULL)) as long as you don't need the value returned
by time() for any other purposes.

top_num=RAND_MAX-(RAND_MAX%fam_size)-1;

White space is your friend in expressions. Don't be afraid to use it to
provide additional parsing clues to the eye of the reader.

//initialize arrays

for (i=0;i<fam_size;i++){
a=b=0;
}
//main control structures
counter=0;
notdone1=1;

while(notdone1)
{

Avoid multiple bracing styles in the same program (compare to the for loop
above). Choose one style and use it consistently.

//ignore this first while loop
//this will ultimately play with
//any given derangement to see if it's
//suitable
for(j=0;j<fam_size;j++)

{
notdone2=1;
while(notdone2){

++counter;
t=rand();
m=t%fam_size;
if ((b[m]==0)&&(m!=j)&&(t<=top_num)){
a[j]=m;
b[m]=1;
notdone2=0;
}
else {
notdone2=1;
}
/* bad luck checker
starts us over except for counter*/
if ((j==fam_size-1)&&(b[j]==0)){
for (i=0;i<fam_size;i++){
a=b=0;
}
notdone2=0;
j=-1;

If you compiled this with a VAX C compiler (a pre-ANSI compiler) you'd
have gotten what you deserved: some older compilers treated =- like -=,
so, instead of assigning -1 to j you'd have ended up decrementing j.

The original form of the op= operators was =op, until Ritchie realised
the problem mentioned above and changed them. However, because some
code using the old form was still in use, many compilers kept supporting
both versions of these operators, until ANSI C formally required a
diagnostic for =op.

OTOH, j = -1 has *always* been unambiguous, because white space acts as
token separator in C.

}
//end notdone2 while
}
//end j loop
}

for(i=0;i<fam_size;i++)
printf("%d %d\n",i,a);
printf("counter= %d\n",counter);

^^ ^^^^^^^
A good compiler, properly invoked, would have detected this bug for you.
You got what you deserved for your choice of crappy tools.

notdone1=0;
//end outer while
}
return 0;
}

Q1) Is this code ANSI-compliant and C99-compliant?

This is what I get if I compile it in ANSI conforming mode:

fangorn:~/tmp 59> gcc -ansi -pedantic -Wall -O test.c
test.c:6: error: parse error before '/' token
test.c:15: error: parse error before '/' token
test.c:17: warning: type defaults to `int' in declaration of `top_num'
test.c:17: error: conflicting types for `top_num'
test.c:13: error: previous declaration of `top_num'
test.c:17: error: ISO C forbids data definition with no type or storage class
test.c:19: error: parse error before '/' token
test.c:26: warning: type defaults to `int' in declaration of `notdone1'
test.c:26: error: ISO C forbids data definition with no type or storage class
test.c:28: error: parse error before "while"
test.c:32:39: missing terminating ' character
test.c:41: warning: type defaults to `int' in declaration of `t'
test.c:41: error: initializer element is not constant
test.c:41: error: ISO C forbids data definition with no type or storage class
test.c:42: warning: type defaults to `int' in declaration of `m'
test.c:42: error: initializer element is not constant
test.c:42: error: ISO C forbids data definition with no type or storage class
test.c:43: error: parse error before "if"
test.c:45: warning: type defaults to `int' in declaration of `b'
test.c:45: warning: ISO C90 forbids variable-size array `b'
test.c:45: error: variable-size type declared outside of any function
test.c:45: error: variable-sized object may not be initialized
test.c:45: error: ISO C forbids data definition with no type or storage class
test.c:46: warning: type defaults to `int' in declaration of `notdone2'
test.c:46: error: ISO C forbids data definition with no type or storage class
test.c:47: error: parse error before '}' token
test.c:57: warning: type defaults to `int' in declaration of `notdone2'
test.c:57: error: redefinition of `notdone2'
test.c:46: error: `notdone2' previously defined here
test.c:57: error: ISO C forbids data definition with no type or storage class
test.c:58: warning: type defaults to `int' in declaration of `j'
test.c:58: error: ISO C forbids data definition with no type or storage class
test.c:59: error: parse error before '}' token
test.c:67: error: parse error before string constant
test.c:67: warning: type defaults to `int' in declaration of `printf'
test.c:67: warning: conflicting types for built-in function `printf'
test.c:67: error: ISO C forbids data definition with no type or storage class
test.c:68: warning: type defaults to `int' in declaration of `notdone1'
test.c:68: error: redefinition of `notdone1'
test.c:26: error: `notdone1' previously defined here
test.c:68: error: ISO C forbids data definition with no type or storage class
test.c:69: error: parse error before '/' token

Obviously, your // comments have completely upset the compiler. If I
replace them by correct ANSI C comments, the output is a lot cleaner:

fangorn:~/tmp 62> gcc -ansi -pedantic -Wall -O test.c
test.c: In function `main':
test.c:67: warning: int format, long int arg (arg 2)

As I said, a good compiler can catch this bug, if kindly asked to.

Q2) The obvious style shortcomings are mostly a product of my IDE looking
different than what is copy/pasted (no Mr. Mair, I am not ready to be weened
off the tit). What style shortcomings do you see that don't involve
spacing?

I'm sorry but your actual spacing makes your code *very* difficult to
follow: one space per indentation level is just not enough for my eyes.

The other style shortcomings already pointed out.

Q3) There's at least one major design flaw. It follows the remark "bad luck
checker" and covers the event that the final element can only be mapped to
itself, which happens 1 out of every fam_size times that the program is run.
Any ideas how to make that less hideous?

I didn't even follow your algorithm, and you didn't bother explaining it
to us, so instead of suggesting a fix I can only suggest a replacement.
You only need one vector of family members, the other is the implied
0, 1, 2 .. fam_size - 1 sequence. Initialise the vector with the implicit
values, then for each element of the vector compute a random replacement
position and swap the two members. If the random replacement is
itself, compute another random replacement. If the swap would result in
any of the two members ending up in its original place (compare the
value and the place), compute another replacement. At the end, no one
should be in its original position:

fangorn:~/tmp 68> cat test.c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define FAMSIZ 20
#define RND (rand() % FAMSIZ)
#define SWAP(i, j) \
(tmp = members, members = members[j], members[j] = tmp)

int main(void)
{
int i, j, tmp, members[FAMSIZ];

for (i = 0; i < FAMSIZ; i++) members = i;
srand(time(NULL));

for (i = 0; i < FAMSIZ; i++) {
while (1) {
j = RND;
if (j == i) continue;
if (members == j || members[j] == i) continue;
break;
}
SWAP(i, j);
printf("%3d", i);
}
putchar('\n');
for (i = 0; i < FAMSIZ; i++) printf("%3d", members);
putchar('\n');
return 0;
}
fangorn:~/tmp 69> gcc -ansi -pedantic -O -Wall test.c
fangorn:~/tmp 70> ./a.out
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
11 13 19 4 8 10 16 1 3 6 14 17 5 9 2 12 15 7 0 18

Of course, there is a much simpler solution, but less random: compute
a random shift value in the range 1 .. FAMSIZ-1 and relocate each member
to position (i + shift) % FAMSIZ:

shift = rand() % (FAMSIZ-1) + 1;
for (i = 0; i < FAMSIZ; i++) members = (i + shift) % FAMSIZ;

The derangement is still perfect.

Dan

 

[Merrill & Michele]

wrote in message news:[email protected]...

A derangement is a mapping of a set onto itself leaving no element fixed. I
realized that that was what I was programming when I was asked to randomly
determine who buys presents for whom this year in my wife's family.
Obviously, one does not buy for himself. The code is followed by some
questions.

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

#define fam_size 20
//must be between 2 and randmax minus one

int main(void)
{
int i,t,a[fam_size],b[fam_size],notdone1,notdone2;
int m,j;
time_t timer;
long counter, top_num;

//determine good random numbers
srand(time(&timer));
top_num=RAND_MAX-(RAND_MAX%fam_size)-1;
"Tim Rentsch" <[email protected]> wrote:

Thank God there's another American who knows the singular for the noun
denoting a male college graduate.

Q1) [omitted, no response here]

Q2) The obvious style shortcomings are mostly a product of my IDE looking
different than what is copy/pasted (no Mr. Mair, I am not ready to be weened
off the tit). What style shortcomings do you see that don't involve
spacing?

The code uses K&R bracing style (braces on the same line as control
keywords) in some places and Berkeley bracing style (braces on lines
by themselves) in other places. There is some evidence that using K&R
bracing style results in fewer program errors, but whether that's true
or not it would be better to pick one style or the other and follow
that exclusively.

A couple of the names use abbreviations as part of the name (eg,
'fam_size'). I recommend using the whole word, and always avoiding
abbreviations. It takes a certain amount of intestinal fortitude to
do this, as the temptation to make exceptions is strong (but don't
give in!). The more I follow this practice the more I see the
benefits. For function local variables, it's common to allow single
letters to be used as "words"; these aren't abbreviations in the
sense meant here.

One of the reasons I use abbreviations is that I'm not 100% sure at this
point what is #defined in my headers, and I don't want any collisions. As I
get sharper, I'll incorporate your criticism.

Using flag variables (notdone1, notdone2) for while loops isn't
necessarily bad style, but usually it's an indicator that something is
wrong somewhere.

Q3) There's at least one major design flaw. It follows the remark "bad luck
checker" and covers the event that the final element can only be mapped to
itself, which happens 1 out of every fam_size times that the program is run.
Any ideas how to make that less hideous?

How about this:

void
generate_random_derangement( unsigned a[], unsigned n ){
unsigned i, j, t, r, r_limit;

r_limit = RAND_MAX - RAND_MAX % n;

for( i = 0; i < n; i++ ) a = i;

for( i = 0; i < n; i++ ){
do {
do r = rand(); while( r >= r_limit );
j = r % n;
if( a != j ){
t = a, a = a[j], a[j] = t;
}
} while( a == i );
}
}

The 'a == i' test guarantees that each element has been swapped to
something other than itself, and the 'a != j' test guarantees that
swaps won't accidentally cause another element to get a bad value.

Thank you for your thoughtful response. I'm working on the code right now
as suggested by Mr. Sosman, and it looks a lot like the above. I think you
err by one in r_limit or want strict inequality with your test vs r. I
actually did the math just now and know that
0x7fff=16^3*7+(16^2+16^1+16^0)15=32767. This makes 32768 equiprobable
outcomes. Assume RAND_MAX were 30 and fam_size were 8. r_limit would be
24, and there would be 25 equiprobable outcomes, which mod fam_size puts a
feather on the zero outcome. (It's kind of funny that I'm prattling on
about a=0 outcome, as it represents buying for my father-in-law, and the
chance that I draw zero is zero)

Are you ever going to get in trouble with r declared as an int? Can
RAND_MAX be 10^9 without forcing the implementation to make the ints wider
as well? MPJ

 

[Alan Balmer]

Furthermore, it is an excellent idea for
you to compile your code in ANSI conforming mode, until you get to the
point where any deviation from ANSI C is deliberate, rather than
accidental.

Well put. I'd add that to my cookie file, if I had one.

 

[Richard Harter]

A couple of the names use abbreviations as part of the name (eg,
'fam_size'). I recommend using the whole word, and always avoiding
abbreviations. It takes a certain amount of intestinal fortitude to
do this, as the temptation to make exceptions is strong (but don't
give in!). The more I follow this practice the more I see the
benefits. For function local variables, it's common to allow single
letters to be used as "words"; these aren't abbreviations in the
sense meant here.

As a subsidiary note, I read a study some years ago that tested the
suggestion that code use a dictionary of abreviations, with names
containing abbreviations strictly using the dictionary. The result
was a significant gain in productivity and readability of code.

The important thing is to have a standard style that is readily
observable. Perhaps the greatest objection to "using the whole word"
(other than the length of resulting identifiers) is that all too often
there is no fixed rule for specifying what whole words are used.

 

[Dan Pop]

Are you ever going to get in trouble with r declared as an int? Can
RAND_MAX be 10^9 without forcing the implementation to make the ints wider
as well? MPJ

If rand() is specified as a function returning int and any conforming
implementation of rand() *must* be able to return RAND_MAX, the conclusion
should be obvious.

In real world implementations, it is the value of RAND_MAX that is chosen
according to the properties of type int (among other criteria), and not
the other way round.

The standard requires both INT_MIN and RAND_MAX to be at least 32767.
However, the type of RAND_MAX need not be int, only its value must be
in the range of the type int (it is defined as an integer constant
expression).

Dan

 

[Tim Rentsch]

As a subsidiary note, I read a study some years ago that tested the
suggestion that code use a dictionary of abreviations, with names
containing abbreviations strictly using the dictionary. The result
was a significant gain in productivity and readability of code.

That's what I would expect. It's nice to have it confirmed
by actual experiment.

The important thing is to have a standard style that is readily
observable. Perhaps the greatest objection to "using the whole word"
(other than the length of resulting identifiers) is that all too often
there is no fixed rule for specifying what whole words are used.

That may be. If so, it seems easy to resolve: simply choose a
particular edition of any unabridged dictionary as the authority.

Normally a team or project will also want to use other things (eg,
"DSL") as words, depending on the project; for "words" like that it's
good to have an explicit list, with the condition that getting a
"word" on the list is decided either by unanimous agreement amongst
the developers (or perhaps by the project lead, if there is one).

Choosing a rule for identifier naming is like designing good
code generally - "the fewer special cases the better."

 

[Keith Thompson]

A couple of the names use abbreviations as part of the name (eg,
'fam_size'). I recommend using the whole word, and always avoiding
abbreviations. It takes a certain amount of intestinal fortitude to
do this, as the temptation to make exceptions is strong (but don't
give in!). The more I follow this practice the more I see the
benefits. For function local variables, it's common to allow single
letters to be used as "words"; these aren't abbreviations in the
sense meant here.

That's mostly good advice, but it shouldn't be applied universally.
Some abbreviations are so obvious that it doesn't make sense to expand
them, such as "IO" rather than "input_output". (And if I were writing
code that handled PCMCIA devices, I wouldn't even know how to expand
the abbreviation; all I can remember is "People Can't Memorize
Computer Industry Acronyms".)

The set of abbreviations that are sufficiently obvious depends
strongly on the domain and the expected audience. In my work, "GPT"
and "GSI" are obvious; most people who don't know what they stand for
are unlikely to want to read my code anyway.

Unfortunately, most people tend to err in the direction of
abbreviating too much.

HTH, HAND, YMMV.

 

[Keith Thompson]

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


If you compiled this with a VAX C compiler (a pre-ANSI compiler) you'd
have gotten what you deserved: some older compilers treated =- like -=,
so, instead of assigning -1 to j you'd have ended up decrementing j.

The original form of the op= operators was =op, until Ritchie realised
the problem mentioned above and changed them. However, because some
code using the old form was still in use, many compilers kept supporting
both versions of these operators, until ANSI C formally required a
diagnostic for =op.

OTOH, j = -1 has *always* been unambiguous, because white space acts as
token separator in C.

Agreed, but just to be picky ...

VAXC does interpret j=-1 as equivalent to j -= 1, but it does print
an informational message (at least in the version I just tried):

%CC-I-ANACHRONISM, The "=-" operator is an obsolete form,
and may not be portable.

And of coure VAXC also reports syntax errors on the "//" comments.

 

[CBFalconer]

.... snip much to get at the 2 deep quote ...

for(i=0;i<fam_size;i++)
printf("%d %d\n",i,a);
printf("counter= %d\n",counter);
notdone1=0;
//end outer while
}
return 0;
}

Just in this little portion, there are a herd of criticisms.
First, there are no prizes for eliding blanks. Almost every token,
including identifiers, should be blank surrounded. An opening '('
should have a preceding blank, unless actually denoting function
parameters. This distinguishes its use from that in for, while,
etc. loops. Every line should be indented from the controlling
line, or be part of that line for simple constructs. // comments
are not portable to the still prevalent C90 compilers, and should
be totally eschewed in newsgroups. A one space indentation is
insufficient. Applying just these to the small piece above, we
get:

for (i = 0; i < fam_size; i++)
printf("%d %d\n", i, a);
printf("counter= %d\n", counter);
notdone1 = 0;
} /* end outer while */
return 0;
}

 

[Dan Pop]

Agreed, but just to be picky ...

VAXC does interpret j=-1 as equivalent to j -= 1, but it does print
an informational message (at least in the version I just tried):

%CC-I-ANACHRONISM, The "=-" operator is an obsolete form,
and may not be portable.

Not in the (admittedly much older) version I did use as a C newbie, when
I got *silently* bitten by this very expression. I could read VAX
assembly and it was obvious that the compiler was generating code to
decrement the variable and it was something far too simple to be a
compiler bug. After 10 minutes or so, I remembered what I had read in
the last section of Appendix A of K&R1 (Anachronisms) and everything was
clear. Yet, I didn't expect VAX C to support features that were declared
anachronic by the time the first VAX machine was made by DEC....

Anyway, I learned my lesson then and started to use white space between
almost all tokens.

I guess many other people have been bitten by that and bitterly complained
until DEC introduced this *badly* needed warning in VAX C, otherwise the
nicest pre-ANSI C compiler I have ever used.

Dan

 

[Merrill & Michele]

[lots of snippage]

Then I also don't need to declare time_t timer, correct? I just need to
include time.h (?).

Make it srand(time(NULL)) as long as you don't need the value returned
by time() for any other purposes.

I don't see how your code divides rand() into equiprobable events modulo
fam_size.

test.c:67: warning: int format, long int arg (arg 2)

This is for the printf( %d, when it should have been printf(%ld correct?

I'm sorry but your actual spacing makes your code *very* difficult to
follow: one space per indentation level is just not enough for my eyes.

I've got to figure something out for future posts. What I see and what I
post are radically different.

Initialise the vector with the implicit
values, then for each element of the vector compute a random replacement
position and swap the two members. If the random replacement is
itself, compute another random replacement. If the swap would result in
any of the two members ending up in its original place (compare the
value and the place), compute another replacement. At the end, no one
should be in its original position:

I think that design is correct. It is slightly different from Mr.
Sosman's, but he wrote in haste in a Sox-euphoria cloud.

fangorn:~/tmp 68> cat test.c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define FAMSIZ 20
#define RND (rand() % FAMSIZ)
#define SWAP(i, j) \
(tmp = members, members = members[j], members[j] = tmp)

int main(void)
{
int i, j, tmp, members[FAMSIZ];

for (i = 0; i < FAMSIZ; i++) members = i;
srand(time(NULL));

for (i = 0; i < FAMSIZ; i++) {
while (1) {
j = RND;
if (j == i) continue;
if (members == j || members[j] == i) continue;
break;
}
SWAP(i, j);
printf("%3d", i);
}
putchar('\n');
for (i = 0; i < FAMSIZ; i++) printf("%3d", members);
putchar('\n');
return 0;
}
fangorn:~/tmp 69> gcc -ansi -pedantic -O -Wall test.c
fangorn:~/tmp 70> ./a.out
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
11 13 19 4 8 10 16 1 3 6 14 17 5 9 2 12 15 7 0 18

Of course, there is a much simpler solution, but less random:

Less random than random is a bit of an issue, although we all don't have
alpha particle emitters to settle the question. (Maybe you do at DESY.)

compute

a random shift value in the range 1 .. FAMSIZ-1 and relocate each member

to position (i + shift) % FAMSIZ:

shift = rand() % (FAMSIZ-1) + 1;
for (i = 0; i < FAMSIZ; i++) members = (i + shift) % FAMSIZ;

The derangement is still perfect.

So is members = members[i+1] for the the way we initialized. <<<<<notice
white space by operators: I'm learning. I still have to code this from the
gitgo. MPJ