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,notdo ne2;
int m,j;
time_t timer;
long counter, top_num;
//determine good random numbers
srand(time(&tim er));
top_num=RAND_MA X-(RAND_MAX%fam_s ize)-1;
//initialize arrays
for (i=0;i<fam_size ;i++){
a[i]=b[i]=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_s ize;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[i]=b[i]=0;
}
notdone2=0;
j=-1;
}
//end notdone2 while
}
//end j loop
}
for(i=0;i<fam_s ize;i++)
printf("%d %d\n",i,a[i]);
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*
Nov 14 '05
136  5447 
wrote in message news:kf******** *****@alumnus.c altech.edu... "Merrill & Michele" <be********@com cast.net> writes:
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,notdo ne2;
int m,j;
time_t timer;
long counter, top_num;
//determine good random numbers
srand(time(&tim er));
top_num=RAND_MA X-(RAND_MAX%fam_s ize)-1;
"Tim Rentsch" <tx*@alumnus.ca ltech.edu> 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] = i;
for( i = 0; i < n; i++ ){
do {
do r = rand(); while( r >= r_limit );
j = r % n;
if( a[i] != j ){
t = a[i], a[i] = a[j], a[j] = t;
}
} while( a[i] == i );
}
}
The 'a[i] == i' test guarantees that each element has been swapped to
something other than itself, and the 'a[i] != 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[i]=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
On 22 Oct 2004 12:31:00 GMT, Da*****@cern.ch (Dan Pop) wrote: 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.
--
Al Balmer
Balmer Consulting re************* ***********@att .net
On 22 Oct 2004 07:39:27 -0700, Tim Rentsch <tx*@alumnus.ca ltech.edu>
wrote: A couple of the names use abbreviations as part of the name (eg,
'fam_size'). I recommend using the whole word, and always avoiding
abbreviation s. 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.
In <Rs************ ********@comcas t.com> "Merrill & Michele" <be********@com cast.net> writes: 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
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de
Currently looking for a job in the European Union cr*@tiac.net (Richard Harter) writes: On 22 Oct 2004 Tim Rentsch <tx*@alumnus.ca ltech.edu wrote:
A couple of the names use abbreviations as part of the name (eg,
'fam_size'). I recommend using the whole word, and always avoiding
abbreviation s. 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.
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."
Tim Rentsch <tx*@alumnus.ca ltech.edu> writes:
[...] 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_outp ut". (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 (The_Other_Keit h) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this. Da*****@cern.ch (Dan Pop) writes: In <6v************ ********@comcas t.com> "Merrill & Michele"
<be********@com cast.net> writes:
[...] 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.
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.
--
Keith Thompson (The_Other_Keit h) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
Tim Rentsch wrote: "Merrill & Michele" <be********@com cast.net> writes:
.... snip much to get at the 2 deep quote ...
for(i=0;i<fam_s ize;i++)
printf("%d %d\n",i,a[i]);
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[i]);
printf("counter = %d\n", counter);
notdone1 = 0;
} /* end outer while */
return 0;
}
--
"I support the Red Sox and any team that beats the Yankees"
"Any baby snookums can be a Yankee fan, it takes real moral
fiber to be a Red Sox fan" - "I listened to Toronto come back
from 3:0 in '42, I watched Boston come back from 3:0 in '04"
In <ln************ @nuthaus.mib.or g> Keith Thompson <ks***@mib.or g> writes: Da*****@cern.c h (Dan Pop) writes: In <6v************ ********@comcas t.com> "Merrill & Michele"
<be********@com cast.net> writes:
[...] 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.
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
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de
Currently looking for a job in the European Union
[lots of snippage] //determine good random numbers
srand(time(&tim er));
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.
top_num=RAND_MA X-(RAND_MAX%fam_s ize)-1;
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[i], members[i] = members[j], members[j] = tmp)
int main(void)
{
int i, j, tmp, members[FAMSIZ];
for (i = 0; i < FAMSIZ; i++) members[i] = i;
srand(time(NULL ));
for (i = 0; i < FAMSIZ; i++) {
while (1) {
j = RND;
if (j == i) continue;
if (members[i] == j || members[j] == i) continue;
break;
}
SWAP(i, j);
printf("%3d", i);
}
putchar('\n');
for (i = 0; i < FAMSIZ; i++) printf("%3d", members[i]);
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] = (i + shift) % FAMSIZ;
The derangement is still perfect.
So is members[i] = 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 This thread has been closed and replies have been disabled. Please start a new discussion. |
