By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
440,262 Members | 1,161 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 440,262 IT Pros & Developers. It's quick & easy.

derangement: code review request

P: n/a
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[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_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[i]=b[i]=0;
}
notdone2=0;
j=-1;
}
//end notdone2 while
}
//end j loop
}

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;
}

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 #1
Share this Question
Share on Google+
136 Replies


P: n/a
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.

[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[i] == j means that person `i'
buys for person `j'; you seek a permuation such
that buys_for[i] != i for all relevant `i'.

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

- For each array position, if buys_for[i] == i then
generate a random j != i and exchange buys_for[i]
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?

--
Er*********@sun.com

Nov 14 '05 #2

P: n/a
[newbie -- just one answer]

Merrill & Michele wrote:
<snip>
#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; ^^^^

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

--
USENET would be a better place if everybody read:
http://www.expita.com/nomime.html
http://www.netmeister.org/news/learn2quote2.html
http://www.catb.org/~esr/faqs/smart-questions.html
Nov 14 '05 #3

P: n/a
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] "Eric Sosman" wrote:
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[i] == j means that person `i'
buys for person `j'; you seek a permuation such
that buys_for[i] != i for all relevant `i'.

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

- For each array position, if buys_for[i] == i then
generate a random j != i and exchange buys_for[i]
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
Nov 14 '05 #4

P: n/a
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; ^^^^

<snip>
printf("counter= %d\n",counter); "Pedro Graca" wrote:
counter is a long, it needs %ld in the format for printf()

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


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
Nov 14 '05 #5

P: n/a
"Merrill & Michele" <be********@comcast.net> writes:
[...]>
"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.

--
Keith Thompson (The_Other_Keith) 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.
Nov 14 '05 #6

P: n/a
Merrill & Michele wrote:
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' :-)
--
USENET would be a better place if everybody read:
http://www.expita.com/nomime.html
http://www.netmeister.org/news/learn2quote2.html
http://www.catb.org/~esr/faqs/smart-questions.html
Nov 14 '05 #7

P: n/a
In <xo********************@comcast.com> "Merrill & Michele" <be********@comcast.net> writes:
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
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de
Currently looking for a job in the European Union
Nov 14 '05 #8

P: n/a
"Merrill & Michele" <be********@comcast.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,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[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_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[i]=b[i]=0;
}
notdone2=0;
j=-1;
}
//end notdone2 while
}
//end j loop
}

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;
}

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] = 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.
Nov 14 '05 #9

P: n/a

In <6v********************@comcast.com> "Merrill & Michele" <be********@comcast.net> writes:
#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[i]=b[i]=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[i]=b[i]=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[i]);
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[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: 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.

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de
Currently looking for a job in the European Union
Nov 14 '05 #10

P: n/a

wrote in message news:kf*************@alumnus.caltech.edu...
"Merrill & Michele" <be********@comcast.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,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" <tx*@alumnus.caltech.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
Nov 14 '05 #11

P: n/a
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
Nov 14 '05 #12

P: n/a
On 22 Oct 2004 07:39:27 -0700, Tim Rentsch <tx*@alumnus.caltech.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
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.
Nov 14 '05 #13

P: n/a
In <Rs********************@comcast.com> "Merrill & Michele" <be********@comcast.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
Nov 14 '05 #14

P: n/a
cr*@tiac.net (Richard Harter) writes:
On 22 Oct 2004 Tim Rentsch <tx*@alumnus.caltech.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
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.


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."
Nov 14 '05 #15

P: n/a
Tim Rentsch <tx*@alumnus.caltech.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_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 (The_Other_Keith) 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.
Nov 14 '05 #16

P: n/a
Da*****@cern.ch (Dan Pop) writes:
In <6v********************@comcast.com> "Merrill & Michele"
<be********@comcast.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_Keith) 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.
Nov 14 '05 #17

P: n/a
Tim Rentsch wrote:
"Merrill & Michele" <be********@comcast.net> writes:

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

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;
}


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"
Nov 14 '05 #18

P: n/a
In <ln************@nuthaus.mib.org> Keith Thompson <ks***@mib.org> writes:
Da*****@cern.ch (Dan Pop) writes:
In <6v********************@comcast.com> "Merrill & Michele"
<be********@comcast.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
Nov 14 '05 #19

P: n/a
[lots of snippage]
//determine good random numbers
srand(time(&timer));
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_MAX-(RAND_MAX%fam_size)-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
Nov 14 '05 #20

P: n/a
On Fri, 22 Oct 2004 16:25:44 -0500, in comp.lang.c , "Merrill & Michele"
<be********@comcast.net> wrote:
I've got to figure something out for future posts. What I see and what I
post are radically different.


Your news software is converting tabs into spaces. Don't use tabs in posts
to usenet.

--
Mark McIntyre
CLC FAQ <http://www.eskimo.com/~scs/C-faq/top.html>
CLC readme: <http://www.ungerhu.com/jxh/clc.welcome.txt>
Nov 14 '05 #21

P: n/a
Keith Thompson <ks***@mib.org> writes:
Tim Rentsch <tx*@alumnus.caltech.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_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.


Sorry, I should have made this more clear in my original writing. I
distinguish between using "abbreviations", by which I mean a
shortening of a word, and using "acronyms", by which I mean a "word"
formed out of initial letters of a longer phrase. So using "tbl" for
"table" would be an abbreviation, whereas "IO" and "PCMCIA" (and
probably GPT and GSI if I knew what they stood for) would be acronyms.
Lots of acronyms are "words" for most practical purposes, and of
course some have even made their way into standard dictionaries -
sonar, radar, and now even DSL (if I'm not mistaken). Standard
acronyms often are acceptable as "words", abbreviations almost always
not. In any case the rules for how to treat abbreviations and how
to treat acronyms should treat the two cases distinctly.

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

HTH, HAND, YMMV.


Humorous footnote - I've seen the acronym HTH at the end of countless
articles by now, but I still don't know what it means. :)

(And yes, I'm sure I could find a meaning online if I needed to, but
somehow it just hasn't seemed important enough yet...)
Nov 14 '05 #22

P: n/a

[...] >Time Rentsch:
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. Keith Thompson <ks***@mib.org> writes:
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.

"Tim Rentsch wrote:
Sorry, I should have made this more clear in my original writing. I
distinguish between using "abbreviations", by which I mean a
shortening of a word, and using "acronyms", by which I mean a "word"
formed out of initial letters of a longer phrase. So using "tbl" for
"table" would be an abbreviation, whereas "IO" and "PCMCIA" (and
probably GPT and GSI if I knew what they stood for) would be acronyms.
Lots of acronyms are "words" for most practical purposes, and of
course some have even made their way into standard dictionaries -
sonar, radar, and now even DSL (if I'm not mistaken). Standard
acronyms often are acceptable as "words", abbreviations almost always
not. In any case the rules for how to treat abbreviations and how
to treat acronyms should treat the two cases distinctly.

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

HTH, HAND, YMMV.


Humorous footnote - I've seen the acronym HTH at the end of countless
articles by now, but I still don't know what it means. :)

(And yes, I'm sure I could find a meaning online if I needed to, but
somehow it just hasn't seemed important enough yet...)


I have been trying for a month now to figure out what OP means, and for the
sake of language clarity, I would like to know whether it is the Original
Post or the Original Poster. The former is an 'it' while the latter has the
attribute of sex (and therefore gender). If I were not substituting a
question for an answer, I would say "Happy To Help." MPJ
Nov 14 '05 #23

P: n/a
"Merrill & Michele" <be********@comcast.net> writes:

I have been trying for a month now to figure out what OP means, and for the
sake of language clarity, I would like to know whether it is the Original
Post or the Original Poster. The former is an 'it' while the latter has the
attribute of sex (and therefore gender). If I were not substituting a
question for an answer, I would say "Happy To Help." MPJ


OP Original Poster
HTH Hope this helps
HAND Have a nice day

For more info see
http://www.utdallas.edu/ir/tcs/techsupp/acronyms.htm
Nov 14 '05 #24

P: n/a
Edmund Bacon <eb****@no.where> writes:
OP Original Poster
HTH Hope this helps
HAND Have a nice day

For more info see
http://www.utdallas.edu/ir/tcs/techsupp/acronyms.htm ^^^^^^^^
Right! Acronyms!

"Tim Rentsch wrote:
Sorry, I should have made this more clear in my original writing. I
distinguish between using "abbreviations", by which I mean a
shortening of a word, and using "acronyms", by which I mean a "word"
formed out of initial letters of a longer phrase. So using "tbl" for
"table" would be an abbreviation, whereas "IO" and "PCMCIA" (and
probably GPT and GSI if I knew what they stood for) would be acronyms.

Nov 14 '05 #25

P: n/a
Da*****@cern.ch (Dan Pop) writes:
In <ln************@nuthaus.mib.org> Keith Thompson <ks***@mib.org> writes: [...]
%CC-I-ANACHRONISM, The "=-" operator is an obsolete form,
and may not be portable.

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


Probably so.

Strictly speaking it's an informational message ("-I-"), which is
weaker than a warning ("-W-"), which I think makes it easier to
suppress, but that shouldn't matter unless you're foolish enough to
turn off diagnostics.

The best solution for anyone still programming on VMS^H^H^H OpenVMS is
probably to use the newer DECC rather than VAXC.

--
Keith Thompson (The_Other_Keith) 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.
Nov 14 '05 #26

P: n/a
Da*****@cern.ch (Dan Pop) writes:
In <Rs********************@comcast.com> "Merrill & Michele"
<be********@comcast.net> writes: [...] 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.
Agreed, with emphasis on "among other criteria". (Solaris has 32-bit
ints, but RAND_MAX==32767.)
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).


I suppose an implementation could define RAND_MAX with a type other
than int, but I can't think of any reason to do so other than sheer
perversity. I would expect it to be an integer-constant or some
simple expression, and it has to be within the range of type int.

--
Keith Thompson (The_Other_Keith) 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.
Nov 14 '05 #27

P: n/a
Tim Rentsch <tx*@alumnus.caltech.edu> writes:
[...]
Sorry, I should have made this more clear in my original writing. I
distinguish between using "abbreviations", by which I mean a
shortening of a word, and using "acronyms", by which I mean a "word"
formed out of initial letters of a longer phrase. So using "tbl" for
"table" would be an abbreviation, whereas "IO" and "PCMCIA" (and
probably GPT and GSI if I knew what they stood for) would be acronyms.


There are two competing definitions for the word "acronym". One
(which I prefer and consider to be more correct) says that an acronym
is an abbreviation formed from the initial letter or letters of
several words *that is pronounced as a word*. The other doesn't
require that it be pronounced as a word. (I suppose "IO" is an
ambiguous case.)

None of which affects the main point, of course.

--
Keith Thompson (The_Other_Keith) 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.
Nov 14 '05 #28

P: n/a

"Merrill & Michele"
[...] 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.

"Keith Thompson"
Agreed, with emphasis on "among other criteria". (Solaris has 32-bit
ints, but RAND_MAX==32767.)
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).


I suppose an implementation could define RAND_MAX with a type other
than int, but I can't think of any reason to do so other than sheer
perversity. I would expect it to be an integer-constant or some
simple expression, and it has to be within the range of type int.


It's generally not wise to snip the question and then beg it. MPJ
Nov 14 '05 #29

P: n/a
Keith Thompson <ks***@mib.org> writes:
Tim Rentsch <tx*@alumnus.caltech.edu> writes:
[...]
Sorry, I should have made this more clear in my original writing. I
distinguish between using "abbreviations", by which I mean a
shortening of a word, and using "acronyms", by which I mean a "word"
formed out of initial letters of a longer phrase. So using "tbl" for
"table" would be an abbreviation, whereas "IO" and "PCMCIA" (and
probably GPT and GSI if I knew what they stood for) would be acronyms.
There are two competing definitions for the word "acronym". One
(which I prefer and consider to be more correct) says that an acronym
is an abbreviation formed from the initial letter or letters of
several words *that is pronounced as a word*. The other doesn't
require that it be pronounced as a word. (I suppose "IO" is an
ambiguous case.)


Right. Historically I think the "pronounceable" definition came
first. These days I think more people are used to acronym meaning any
string of initial letters that is used as a word (i.e., without regard
to whether the word is pronounceable or not); for example, I think
most people would say TLA is itself a three letter acronym. Acronyms
that are pronounced/used as regular words eventually become just
regular words and we tend to forget their acroynm-ness. "Laser" is an
example of that, or "spool" (and in fact I used the word spool for
quite a while before finding out that it is an acronym). So being an
acronym in that earlier sense eventually becomes more of an
etymological footnote than anything else.

None of which affects the main point, of course.


Roger that.
Nov 14 '05 #30

P: n/a
"Merrill & Michele" <be********@comcast.net> writes:
"Merrill & Michele"
> > [...]
> 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.

"Keith Thompson"
Agreed, with emphasis on "among other criteria". (Solaris has 32-bit
ints, but RAND_MAX==32767.)
> 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).


I suppose an implementation could define RAND_MAX with a type other
than int, but I can't think of any reason to do so other than sheer
perversity. I would expect it to be an integer-constant or some
simple expression, and it has to be within the range of type int.


It's generally not wise to snip the question and then beg it. MPJ


Um, what question did I beg?

I wasn't actually trying to answer the original question; I was
elaborating on a couple of points that Dan Pop had made.

If the question you're referring to is:

] 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

I thought Dan already answered that. rand() returns a result in the
range 0 to RAND_MAX. Since the return type of rand() is int, RAND_MAX
must be representable as an int (at least 32767, and at most INT_MAX).

--
Keith Thompson (The_Other_Keith) 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.
Nov 14 '05 #31

P: n/a

"Keith Thompson" <ks***@mib.org> wrote in message
news:ln************@nuthaus.mib.org...
"Merrill & Michele" <be********@comcast.net> writes:
"Merrill & Michele"
> > [...]
> 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.

"Keith Thompson"
Agreed, with emphasis on "among other criteria". (Solaris has 32-bit
ints, but RAND_MAX==32767.)

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

I suppose an implementation could define RAND_MAX with a type other
than int, but I can't think of any reason to do so other than sheer
perversity. I would expect it to be an integer-constant or some
simple expression, and it has to be within the range of type int.


It's generally not wise to snip the question and then beg it. MPJ


Um, what question did I beg?

I wasn't actually trying to answer the original question; I was
elaborating on a couple of points that Dan Pop had made.

If the question you're referring to is:

] 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

I thought Dan already answered that. rand() returns a result in the
range 0 to RAND_MAX. Since the return type of rand() is int, RAND_MAX
must be representable as an int (at least 32767, and at most INT_MAX).

--
Keith Thompson (The_Other_Keith) 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.

Nov 14 '05 #32

P: n/a
"Merrill & Michele" wrote: you begged the question
Keith Thompson wrote: what question did I beg?


There isn't a 'what" when you beg the question. I claim that you assumed
your result in order to prove it. To schloppen. MPJ
Nov 14 '05 #33

P: n/a
"Merrill & Michele" <be********@comcast.net> writes:
"Merrill & Michele" wrote: you begged the question

Keith Thompson wrote: what question did I beg?


There isn't a 'what" when you beg the question. I claim that you assumed
your result in order to prove it. To schloppen. MPJ


Ok, what result did I assume? (I don't believe I assumed anything.)

--
Keith Thompson (The_Other_Keith) 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.
Nov 14 '05 #34

P: n/a
> >>>"Merrill & Michele" wrote: you begged the question
Keith Thompson wrote: what question did I beg?


There isn't a 'what" when you beg the question. I claim that you assumed your result in order to prove it. To schloppen. MPJ


Ok, what result did I assume? (I don't believe I assumed anything.)


As usual, I must admit to having trouble reading my screen. Mr. Pop's
declaration that RAND_MAX must be within the int range was what was to be
shown. Begging the question is when A is to be shown, and the proof goes:
if A, then A, a tautology. Upon further review, the flag has been picked
up. San Diego will not be charged a time out. MPJ
Nov 14 '05 #35

P: n/a
Tim Rentsch <tx*@alumnus.caltech.edu> wrote:
Keith Thompson <ks***@mib.org> writes:
Unfortunately, most people tend to err in the direction of
abbreviating too much.

HTH, HAND, YMMV.


Humorous footnote - I've seen the acronym HTH at the end of countless
articles by now, but I still don't know what it means. :)


Hail To Hastur - His Arrival Nears Daily.

HTH; HAND.

Richard
Nov 14 '05 #36

P: n/a
Richard Bos wrote:
Tim Rentsch <tx*@alumnus.caltech.edu> wrote:
Keith Thompson <ks***@mib.org> writes:
Unfortunately, most people tend to err in the direction of
abbreviating too much.

HTH, HAND, YMMV.


Humorous footnote - I've seen the acronym HTH at the end of
countless articles by now, but I still don't know what it means. :)


Hail To Hastur - His Arrival Nears Daily.

HTH; HAND.


Young Maidens Manipulate Violet.

--
Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!

Nov 14 '05 #37

P: n/a
In <ln************@nuthaus.mib.org> Keith Thompson <ks***@mib.org> writes:
Da*****@cern.ch (Dan Pop) writes:
In <ln************@nuthaus.mib.org> Keith Thompson <ks***@mib.org> writes:[...]
%CC-I-ANACHRONISM, The "=-" operator is an obsolete form,
and may not be portable.

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


Probably so.

Strictly speaking it's an informational message ("-I-"), which is
weaker than a warning ("-W-"), which I think makes it easier to
suppress, but that shouldn't matter unless you're foolish enough to
turn off diagnostics.


The distinction between warnings and informational messages is something
specific to VMS and the only difference is that you get another warning
(or is it informational message?) when you link an object file that
generated warnings when compiled.

To my, any compiler-generated message is a diagnostic and I deliberately
ignore any difference between errors and warnings. OTOH, I have the
luxury to use a compiler that can be tuned to generate only those
diagnostics that I consider as deserving my attention (gcc -Wall -O).
The best solution for anyone still programming on VMS^H^H^H OpenVMS is
probably to use the newer DECC rather than VAXC.


I was not even aware that VAX C still exists as a supported HP product.

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de
Currently looking for a job in the European Union
Nov 14 '05 #38

P: n/a
In <Av********************@comcast.com> "Merrill & Michele" <be********@comcast.net> writes:
[lots of snippage]
> //determine good random numbers
> srand(time(&timer));
Then I also don't need to declare time_t timer, correct? I just need to
include time.h (?).
Right. No point in declaring a variable you never use.
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;
I don't see how your code divides rand() into equiprobable events modulo
fam_size.


The non-equiprobability of rand() % FAMSIZ is so insignificant that it is
not worth worrying about, especially considering that it is not central
to the algorithm. No reasonable family size is going to get within one
order of magnitude of the smallest allowed value for RAND_MAX. What
really matters is that rand() % FAMSIZ generates a reasonably random
value in the 0 .. FAMSIZ-1 range.

If that is not good enough for you, use your own random generator (the
rand() coming with most implementations doesn't have a particularly
good reputation) and use the algorithm described in the FAQ for
mapping it into the integer interval of your choice.
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?


Right. Even if it works on your system, your printf call is not correct
and need not work on other systems. In the C jargon, it invokes undefined
behaviour.
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.


1. Convince your editor not to use TABs for indentation purposes.

2. If the above is not possible, write your own program to replace each
TAB character by as many spaces as needed to implement TAB stops every
N characters. It is an excellent exercise for you, at your current
level.
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.


True, but the results are predictible, while my method picks one of
the FAMSIZ-1 trivial derangements at random.

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de
Currently looking for a job in the European Union
Nov 14 '05 #39

P: n/a
> >> > top_num=RAND_MAX-(RAND_MAX%fam_size)-1;

I don't see how your code divides rand() into equiprobable events modulo
fam_size.
The non-equiprobability of rand() % FAMSIZ is so insignificant that it is
not worth worrying about, especially considering that it is not central
to the algorithm. No reasonable family size is going to get within one
order of magnitude of the smallest allowed value for RAND_MAX. What
really matters is that rand() % FAMSIZ generates a reasonably random
value in the 0 .. FAMSIZ-1 range.

If that is not good enough for you, use your own random generator (the
rand() coming with most implementations doesn't have a particularly
good reputation) and use the algorithm described in the FAQ for
mapping it into the integer interval of your choice.
You're amputating something that requires a band-aid. By throwing out rand
calls that exceed top_num above, the events mod FAMSIZ are equiprobable.
Period. I'll add white-spacing so as to make that statement clearer.
2. If the above is not possible, write your own program to replace each
TAB character by as many spaces as needed to implement TAB stops every
N characters. It is an excellent exercise for you, at your current
level.
Following one of your earlier posts, I determined that I can direct the
input on the command line of this platform which will not be named, and thus
get text in and out of these progs in a sensible manner. The conversion
might be six lines of code and is behind me in K&R.
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.


True, but the results are predictible, while my method picks one of
the FAMSIZ-1 trivial derangements at random.


This statement contradicts a previous of yours. I'll test it to see which
Dan Pop is correct. MPJ
Nov 14 '05 #40

P: n/a
Tim Rentsch <tx*@alumnus.caltech.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
abbreviations.
I disagree. Even for normal abbreviations, not just for acronyms,
industry-standard abbrevs are probably more legible than the whole word.

I mean, my main program deals with entering data for advertisement. Can
you imagine how much larger and less legible my code would've been if
I'd used advertisement_width_in_columns everywhere I know have adv_cols?
void
Ew, ganoo style.
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;


Ew ew ew! You just proved that whitespace isn't _always_ good (and
whitespace on the _inside_ or parens rarely is). How about this more
moderate version:

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

In fact, I'd prefer

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

But double spaces? Yuck.

Richard
Nov 14 '05 #41

P: n/a
I think there exists enough information in this thread in order to take a
swipe at coding this.

I have 3 libraries to include, all of which are 1989-, 1999- and
2004-compliant. I have two macros. Mr. Pop's RND was not even close to
right. His SWAP I will lift from him wholesale. Persons like me who have,
at other times and places, used a swap command will see that this macro not
only does this but will squack (<<can't spell; rhymes with talk) if the
types aren't right. fam_size becomes FAMSIZ. I reject strongly the notion
that FAMILYSIZE would be a better option here. I guess I would add on to
the style comments above that one uses no macro name, which, parsed, yields
a keyword in most every language. Furthermore, seven letters is plenty for
my prog.variable.names . Let's give this a whirl, Earl:

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

#define FAMSIZ 15 /*between 2 and RAND_MAX*/
#define SWAP danscode

int main(){

printf("tja\n");
return 0;
}
Nov 14 '05 #42

P: n/a
In <T9********************@comcast.com> "Merrill & Michele" <be********@comcast.net> writes:
>> > top_num=RAND_MAX-(RAND_MAX%fam_size)-1;
>
>I don't see how your code divides rand() into equiprobable events modulo
>fam_size.


The non-equiprobability of rand() % FAMSIZ is so insignificant that it is
not worth worrying about, especially considering that it is not central
to the algorithm. No reasonable family size is going to get within one
order of magnitude of the smallest allowed value for RAND_MAX. What
really matters is that rand() % FAMSIZ generates a reasonably random
value in the 0 .. FAMSIZ-1 range.

If that is not good enough for you, use your own random generator (the
rand() coming with most implementations doesn't have a particularly
good reputation) and use the algorithm described in the FAQ for
mapping it into the integer interval of your choice.


You're amputating something that requires a band-aid. By throwing out rand
calls that exceed top_num above, the events mod FAMSIZ are equiprobable.
Period. I'll add white-spacing so as to make that statement clearer.


White space or not, I don't understand what you're trying to say. Try
something better than adding white space. Also make sure that what you're
actually trying to say is true.
2. If the above is not possible, write your own program to replace each
TAB character by as many spaces as needed to implement TAB stops every
N characters. It is an excellent exercise for you, at your current
level.


Following one of your earlier posts, I determined that I can direct the
input on the command line of this platform which will not be named, and thus
get text in and out of these progs in a sensible manner. The conversion
might be six lines of code and is behind me in K&R.
>> 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.


True, but the results are predictible, while my method picks one of
the FAMSIZ-1 trivial derangements at random.


This statement contradicts a previous of yours.


It always helps if you point out the contradicted statement. AFAICT,
it doesn't contradict any of my previous statements.

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de
Currently looking for a job in the European Union
Nov 14 '05 #43

P: n/a
> I think there exists enough information in this thread in order to take a
swipe at coding this.

I have 3 libraries to include, all of which are 1989-, 1999- and
2004-compliant. I have two macros. Mr. Pop's RND was not even close to
right. His SWAP I will lift from him wholesale. Persons like me who have, at other times and places, used a swap command will see that this macro not only does this but will squack (<<can't spell; rhymes with talk) if the
types aren't right. fam_size becomes FAMSIZ. I reject strongly the notion that FAMILYSIZE would be a better option here. I guess I would add on to
the style comments above that one uses no macro name, which, parsed, yields a keyword in most every language. Furthermore, seven letters is plenty for my prog.variable.names . Let's give this a whirl, Earl:

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

#define FAMSIZ 15 /*between 2 and RAND_MAX*/
#define SWAP danscode

int main(){

printf("tja\n");
return 0;
}


This compiles and links, not surprising to most. But what differs is that I
copypasted this off the net. Output:
http://home.comcast.net/~beckjensen/derange.htm

Next, I add the SWAP and do declarations. MPJ
Nov 14 '05 #44

P: n/a
_leroy
I think there exists enough information in this thread in order to take a
swipe at coding this.

I have 3 libraries to include, all of which are 1989-, 1999- and
2004-compliant. I have two macros. Mr. Pop's RND was not even close to
right. His SWAP I will lift from him wholesale. Persons like me who have, at other times and places, used a swap command will see that this macro not only does this but will squack (<<can't spell; rhymes with talk) if the
types aren't right. fam_size becomes FAMSIZ. I reject strongly the notion that FAMILYSIZE would be a better option here. I guess I would add on to
the style comments above that one uses no macro name, which, parsed, yields a keyword in most every language. Furthermore, seven letters is plenty for my prog.variable.names . Let's give this a whirl, Earl:

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

#define FAMSIZ 15 /*between 2 and RAND_MAX*/
#define SWAP \ (tmp=buys_for[m],buys_for[m]=buys_for[n],buys_for[n]=tmp)
#define > ' '
int main(){
int i;
int m,n,tmp;
int buys_for[FAMSIZ];
printf("tja\n");
return 0;
}

Nov 14 '05 #45

P: n/a
> > I think there exists enough information in this thread in order to take
a
swipe at coding this.

I have 3 libraries to include, all of which are 1989-, 1999- and
2004-compliant. I have two macros. Mr. Pop's RND was not even close to
right. His SWAP I will lift from him wholesale. Persons like me who

have,
at other times and places, used a swap command will see that this macro

not
only does this but will squack (<<can't spell; rhymes with talk) if the
types aren't right. fam_size becomes FAMSIZ. I reject strongly the

notion
that FAMILYSIZE would be a better option here. I guess I would add on to the style comments above that one uses no macro name, which, parsed,

yields
a keyword in most every language. Furthermore, seven letters is plenty

for
my prog.variable.names . Let's give this a whirl, Earl:
/* Ever C program that I will consider begins with a hash
and ends with a close brace */ #include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define FAMSIZ 15 /*between 2 and RAND_MAX*/
#define SWAP \

(tmp=buys_for[m],buys_for[m]=buys_for[n],buys_for[n]=tmp)
#define > ' ' /*use max for greater than,*/

int main(){


int i;
int m,n,tmp,t,top_num;
int buys_for[FAMSIZ];
/*i is always available for dummy*/
top_num=RAND_MAX - ( RAND_MAX % FAMSIZ) - 1;
srand(time(NULL));

/*initialize*/
for (i=0;i<FAMSIZ;i++) buys_for[i]=i;

/*main control*/
printf("%d number=", t);
return 0;
}


Nov 14 '05 #46

P: n/a
/* Every C program that I will consider begins with a hash
and ends with a close brace */
#include <stdio.h@
#include <stdlib.h@
#include <time.h@

#define FAMSIZ 15 /*between 2 and RAND_MAX*/
#define SWAP \

(tmp=buys_for[m],buys_for[m]=buys_for[n],buys_for[n]=tmp)
#define > ' ' /*use max for greater than,*/ #define @ 076 /*encoding specific*/
/*would I be surprised if this worked*/

int main(){


int i;
int m,n,tmp,t,top_num;
int buys_for[FAMSIZ];
/*i is always available for dummy*/
top_num=RAND_MAX - ( RAND_MAX % FAMSIZ) - 1;
srand(time(NULL));

/*initialize*/
for (i=0;i<FAMSIZ;i++) buys_for[i]=i;

/*main control*/
printf("%d number=", t);
return 0;
}



Nov 14 '05 #47

P: n/a
#define '.h>' @
#define > ' '
#define @ >
/* Every C program that I will consider begins with a hash
and ends with a close brace */
> #include <stdio.h>
> #include <stdlib.h>
> #include <time.h> >
> #define FAMSIZ 15 /*between 2 and RAND_MAX*/
> #define SWAP \
(tmp=buys_for[m],buys_for[m]=buys_for[n],buys_for[n]=tmp) /*would I be surprised if this worked*/ >
> int main(){

int i;
int m,n,tmp,t,top_num;
int buys_for[FAMSIZ];
>

/*i is always available for dummy*/
top_num=RAND_MAX - ( RAND_MAX % FAMSIZ) - 1;
srand(time(NULL));

/*initialize*/
for (i=0;i<FAMSIZ;i++) buys_for[i]=i;

/*main control*/
> printf("%d number=", t);
> return 0;
> }
>
>



Nov 14 '05 #48

P: n/a
#define '.h>' @
#define > ' '
#define @ '.h>'
/* Every C program that I will consider begins with a hash
and ends with a close brace */
> > #include <stdio.h>
> > #include <stdlib.h>
> > #include <time.h> >
> > #define FAMSIZ 15 /*between 2 and RAND_MAX*/
> > #define SWAP \
> (tmp=buys_for[m],buys_for[m]=buys_for[n],buys_for[n]=tmp)

/*would I be surprised if this worked*/
> >
> > int main(){
>
> int i;
> int m,n,tmp,t,top_num;
> int buys_for[FAMSIZ];
> >
/*i is always available for dummy*/
top_num=RAND_MAX - ( RAND_MAX % FAMSIZ) - 1;
srand(time(NULL));

/*initialize*/
for (i=0;i<FAMSIZ;i++) buys_for[i]=i;

/*main control*/

> > printf("%d number=", t);
> > return 0;
> > }
> >
> >
>
>



Nov 14 '05 #49

P: n/a
> #define '.h>' @
#define > ' '
#define @ '.h>'
> /* Every C program that I will consider begins with a hash
> and ends with a close brace */
> > > #include <stdio.h>
> > > #include <stdlib.h>
> > > #include <time.h>

> > >
> > > #define FAMSIZ 15 /*between 2 and RAND_MAX*/
> > > #define SWAP \
> > (tmp=buys_for[m],buys_for[m]=buys_for[n],buys_for[n]=tmp)
/*would I be surprised if this worked*/
> > >
> > > int main(){
> >
> > int i;
> > int m,n,tmp,t,top_num;
> > int buys_for[FAMSIZ];
> > >
> /*i is always available for dummy*/
> top_num=RAND_MAX - ( RAND_MAX % FAMSIZ) - 1;
> srand(time(NULL));
>
> /*initialize*/
> for (i=0;i<FAMSIZ;i++) buys_for[i]=i;
>
> /*main control*/
>
> > > printf("%d number=", t);
> > > return 0;
> > > }
> > >
> > >
> >
> >
>
>



Eight strikes, I'm out. Please don't tell me you read all this way because
I was OT. That would just make you dumb. MPJ
Nov 14 '05 #50

136 Replies

This discussion thread is closed

Replies have been disabled for this discussion.