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
136  5321 
Merrill & Michele wrote: MPJ:
"Dan Pop" writes:
"Merrill & Michele
[undeclared function]
void swap(int *px, int *py){
doesn't compile Are you surprised?
No, I just couldn't figure out what the errors that the compiler was spewing
out meant. I forgot to declare the function.
Er... No. You tried to define a function within another function.
Read the stuff about function definitions and declarations/prototypes
once more with special emphasis on where to put them.
That I posted what I had was
a filibuster of sorts with regards to my newsreader. I'm going to get this
code right and stylistically acceptable.
Yep, and we are ready to help you do that.
I really do not appreciate
disparagement when I'm working my ass off (elsethread directed).
The code you posted was so obviously not valid C code that Dan
and I assumed you are aware of that. Had you asked why it does
not compile, we would have pointed out your mistakes.
Apart from that: I was not disparaging you but your mode of
using this newsgroup.
Last
night, I asked my uncle why he didn't use K&R to teach. I thought his
answer was interesting, but I wouldn't want to trouble this forum with my 2
decades of meta-ideas.
*g* That really rankled, did it? SCNR
Apart from that, you would trouble us with your uncle's reasons.
Personally, I do not use K&R to teach, either, due to the circumstances.
Cheers
Michael
--
E-Mail: Mine is an /at/ gmx /dot/ de address.
"Michael Mair" <Mi**********@invalid.invalid> wrote in message
news:2v*************@uni-berlin.de... Merrill & Michele wrote:
MPJ:
"Dan Pop" writes:
"Merrill & Michele
[undeclared function]
void swap(int *px, int *py){
doesn't compile
Are you surprised?
No, I just couldn't figure out what the errors that the compiler was
spewing out meant. I forgot to declare the function.
Er... No. You tried to define a function within another function.
Read the stuff about function definitions and declarations/prototypes
once more with special emphasis on where to put them.
That I posted what I had was
a filibuster of sorts with regards to my newsreader. I'm going to get
this code right and stylistically acceptable.
Yep, and we are ready to help you do that.
I really do not appreciate
disparagement when I'm working my ass off (elsethread directed).
The code you posted was so obviously not valid C code that Dan
and I assumed you are aware of that. Had you asked why it does
not compile, we would have pointed out your mistakes.
Apart from that: I was not disparaging you but your mode of
using this newsgroup.
Last
night, I asked my uncle why he didn't use K&R to teach. I thought his
answer was interesting, but I wouldn't want to trouble this forum with
my 2 decades of meta-ideas.
*g* That really rankled, did it? SCNR
Apart from that, you would trouble us with your uncle's reasons.
Personally, I do not use K&R to teach, either, due to the circumstances.
Did you see the final code posting? I think I got it. What does SCNR mean?
That didn't rankle. It was the "annoying, inane white noise" that go my
dander up. MPJ
Merrill & Michele wrote:
Did you see the final code posting? I think I got it. What does SCNR mean?
That didn't rankle. It was the "annoying, inane white noise" that go my
dander up. MPJ
Well, it is not exactly the most clever idea to put the
prototype of swap() _inside_ another function. This makes it
possible to miss a few prototypes at changes and makes you type these
prototypes again and again as soon as you get to use more functions
and write complex code coming in several files.
Prototypes and typedefs usually (there are exceptions) should be
found at file scope or in header files, prior to your function
definitions.
Apart from that, it should work fine.
SCNR=Sorry, could not resist.
About the other: I really did not understand that you had a problem
and thought that you abused c.l.c as scratch for ideas not very
well thought out. As the stuff you posted obviously (for me) would
never ever compile, it seemed more like a collection of not so
well-ordered thoughts. Thus "white noise" and "inane".
Cheers,
Michael
--
E-Mail: Mine is a gmx dot de address.
"Michael Mair" <Mi**********@invalid.invalid> wrote in message
news:2v*************@uni-berlin.de...
Merrill & Michele wrote: >
Did you see the final code posting? I think I got it. What does SCNR
mean? That didn't rankle. It was the "annoying, inane white noise" that go my
dander up. MPJ
Well, it is not exactly the most clever idea to put the
prototype of swap() _inside_ another function. This makes it
possible to miss a few prototypes at changes and makes you type these
prototypes again and again as soon as you get to use more functions
and write complex code coming in several files.
Prototypes and typedefs usually (there are exceptions) should be
found at file scope or in header files, prior to your function
definitions.
Apart from that, it should work fine.
SCNR=Sorry, could not resist.
About the other: I really did not understand that you had a problem
and thought that you abused c.l.c as scratch for ideas not very
well thought out. As the stuff you posted obviously (for me) would
never ever compile, it seemed more like a collection of not so
well-ordered thoughts. Thus "white noise" and "inane".
You asked earlier about why my uncle didn't go with K&R. It would be a very
bad idea for me to reveal the contents of such calls. Let me instead claim
that my uncle doesn't exist, and that my keystrokes are a collection of less
than well ordered thoughts. With that premise and caveat, I offer the
following criticism of K&R:
Q1) Is paper so precious that they couldn't include the swap function in its
full, isolated glory:
#include <stdio.h>
void swap(int *coconut, int *banana);
int main(void){
int a = 3;
int b = 5;
swap(&a, &b);
printf ("a equals %d\n", a);
printf ("b equals %d\n", b);
return 0;
}
void swap(int *px, int *py){
int tmp = *px;
*px = *py;
*py = tmp;
}
You err when you say that it was not the most clever idea for me to put the
function prototype within main. It wasn't an idea at all! I was just
trying to get something to work, and all my compiler was telling me was that
I was missing a semicolon. Further questions:
Q2) The following builds and behaves for me fine. Why do you make the
arguments in the prototype look like they matter?
#include <stdio.h>
void swap(int, int);
int main(void){
int a = 3;
int b = 5;
swap(&a, &b);
printf ("a equals %d\n", a);
printf ("b equals %d\n", b);
return 0;
}
void swap(int *px, int *py){
int tmp = *px;
*px = *py;
*py = tmp;
}
The election was a hard time for this native and politically-active Ohioan.
For thoughtful interaction at clc during this period I am grateful. MPJ
On Thu, 11 Nov 2004 19:35:27 -0600, in comp.lang.c , "Merrill & Michele"
<be********@comcast.net> wrote: Q2) The following builds and behaves for me fine. Why do you make the
arguments in the prototype look like they matter?
The declaration or prototype tells the compiler what type of arguments to
expect. If you then pass the wrong types, it has to convert them. This may
be impossible. Or it may convert it to some garbage value. For example,
passing 1 to a function expecting a pointer might cause it to create a
pointer to memory address 1, which is often inside hardware memory. This is
very likely to crash your computer.
Some computers even use different memory locations for different types of
object - 680x0 chips spring to mind - and so telling a function to expect
an int then feeding it a pointer will cause it to fetch an int from the
garbage heap.
#include <stdio.h>
void swap(int, int);
void swap(int *px, int *py){
If your compiler doesn't complain about this, you need to turn up
warninglevels, or get a better compiler. Your example is undefined
behaviour. Not only that, but despite appearances its not working - its
merely pretending to work ,and later on ,say when you demonstrate some code
to a customer, it will crash spectacularly, probably setting fire to his
club tie and pouring brake fluid on his porsche.
--
Mark McIntyre
CLC FAQ <http://www.eskimo.com/~scs/C-faq/top.html>
CLC readme: <http://www.ungerhu.com/jxh/clc.welcome.txt>
----== Posted via Newsfeeds.Com - Unlimited-Uncensored-Secure Usenet News==---- http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----
"Mark McIntyre" <ma**********@spamcop.net> wrote in message
news:hb********************************@4ax.com... On Thu, 11 Nov 2004 19:35:27 -0600, in comp.lang.c , "Merrill & Michele"
<be********@comcast.net> wrote:
Q2) The following builds and behaves for me fine. Why do you make the
arguments in the prototype look like they matter?
The declaration or prototype tells the compiler what type of arguments to
expect. If you then pass the wrong types, it has to convert them. This
may be impossible. Or it may convert it to some garbage value. For example,
passing 1 to a function expecting a pointer might cause it to create a
pointer to memory address 1, which is often inside hardware memory. This
is very likely to crash your computer.
Some computers even use different memory locations for different types of
object - 680x0 chips spring to mind - and so telling a function to expect
an int then feeding it a pointer will cause it to fetch an int from the
garbage heap.
#include <stdio.h>
void swap(int, int);void swap(int *px, int *py){
If your compiler doesn't complain about this, you need to turn up
warninglevels, or get a better compiler. Your example is undefined
behaviour. Not only that, but despite appearances its not working - its
merely pretending to work ,and later on ,say when you demonstrate some
code to a customer, it will crash spectacularly, probably setting fire to his
club tie and pouring brake fluid on his porsche.
My compiler doesn't complain if smoke's coming out of it. That's within my
thousand most important problems. You err to think that I would talk to a
customer who drives a Porsche. WTF is the point of having a porsche in
Minneslowta except to show that you're type A. To the topic though, would I
not be fine calling those prototypes *coconuts or *Krijn OR indeed would
void swap(int *a, int *a);
work swell? MPJ
On Sat, 13 Nov 2004 00:21:44 -0600, in comp.lang.c , "Merrill & Michele"
<be********@comcast.net> wrote: To the topic though, would I
not be fine calling those prototypes *coconuts or *Krijn
Anything is ok as long as the prototype matches the definition, and the
function call matches the prototype. This generally restricts how you do it
to sensible forms.
OR indeed would void swap(int *a, int *a);
work swell? MPJ
A function can't have two parameters with the same name, because its a
redefinition of the parameter.
Do you actually have a book about C?
--
Mark McIntyre
CLC FAQ <http://www.eskimo.com/~scs/C-faq/top.html>
CLC readme: <http://www.ungerhu.com/jxh/clc.welcome.txt>
----== Posted via Newsfeeds.Com - Unlimited-Uncensored-Secure Usenet News==---- http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =---- MPJ:
To the topic though, would I
not be fine calling those prototypes *coconuts or *Krijn
"Mark McIntyre:
Anything is ok as long as the prototype matches the definition, and the
function call matches the prototype. This generally restricts how you do
it to sensible forms.
OR indeed would void swap(int *a, int *a);
work swell? MPJ
A function can't have two parameters with the same name, because its a
redefinition of the parameter.
Do you actually have a book about C?
As a strict Copenhagener, right now I possess exactly one book on c. K&R2
§5.2 looks at the swap function and §5.11 looks at prototypes. Frankly, it
makes my head spin.
Q) Good form has prototypes before the main call. These prototypes take
arguments. MUST EVERY keystroke (excepting white space) match the arguments
of the ultimate function call in order to have defined behavior? MPJ
Merrill & Michele wrote: MPJ:
To the topic though, would I
not be fine calling those prototypes *coconuts or *Krijn
"Mark McIntyre:
Anything is ok as long as the prototype matches the definition, and the
function call matches the prototype. This generally restricts how you do
it
to sensible forms.
OR indeed would void swap(int *a, int *a);
work swell? MPJ
A function can't have two parameters with the same name, because its a
redefinition of the parameter.
Do you actually have a book about C?
As a strict Copenhagener, right now I possess exactly one book on c. K&R2
§5.2 looks at the swap function and §5.11 looks at prototypes. Frankly, it
makes my head spin.
Q) Good form has prototypes before the main call. These prototypes take
arguments. MUST EVERY keystroke (excepting white space) match the arguments
of the ultimate function call in order to have defined behavior? MPJ
Not every keystroke.
The purpose of the prototype is to clue the compiler as to how to
call the library function. This clue allows the compiler to perform
permitted type conversions as needed.
The compiler is interested in the 'name' of the function and its
type and the type and number of its arguments.
Naming the arguments is optional and only to to make the prototype
more 'expressive' to the human reader. The compiler doesn't care
whether you name them or not.
--
Joe Wright mailto:jo********@comcast.net
"Everything should be made as simple as possible, but not simpler."
--- Albert Einstein ---
In article <news:Lo********************@comcast.com>
Merrill & Michele <be********@comcast.net> wrote: Q) Good form has prototypes before the main call.
(I would take out the word "main" here: I have no idea what it is
doing in this sentence. I would say that "good form has prototypes
for functions before calls to those functions." It is also
generally wise to have those same prototypes appear before the
definition of the function as well, in more complicated situations
involving header files and separate compilation.)
These prototypes take arguments.
Yes. Note in particular that even a function that has no arguments
at all -- such as:
void print_header(void) {
puts("==== header ====");
}
for instance -- needs to have the "void" keyword in a prototype:
void print_header(void); /* prototype */
because writing this:
void print_header(); /* not a prototype! */
gives you a declaration, but not a prototype. (This is a historical
oddity having to do with adding prototypes in 1989, where C had
none before that. The ANSI committee folks decided not to change
the meaning of "old style" declarations, so they had to invent new
syntax: "the absence of arguments here means nothing about the
arguments; the presence of a `void' keyword means there are no
arguments".)
MUST EVERY keystroke (excepting white space) match the arguments
of the ultimate function call in order to have defined behavior? MPJ
No -- but it is often a good idea to have them match, even to the
very whitespace.
The part(s) of the prototype arguments that matter *to the compiler*
are the number and type of arguments:
void fA(void); /* zero arguments */
void fB(int, char *); /* two arguments: int, pointer-to-char */
void fC(double); /* one argument: double */
but the rest is useful to humans:
void do_some_operation(char *output, char *input, int operation);
void do_other_operation(char *input, int operation, char *output);
Here the compiler cares only that there are three arguments, two
of type "pointer to char" and one of type "int", but a person
writing code probably wants to know which "char *" is the "output"
and which one is the "input". We could leave out the name "operation",
because there is only one "int", and if an operation has to be an
int, it is immediately obvious which of the one (count them 1)
"int" parameters is the "int" parameter. :-)
Of course, "good design" would also suggest that all of the
various "do an operation" functions take their input, output,
and operation parameters in the same places -- but having the
names, too, is a good thing.
Note that those who intentionally obfuscate their code (perhaps
in an attempt to obtain job security) might name their parameters
in a deliberately-confusing way:
void do_third_operation(char *kumquat, int output, char *lemon);
While the computer does not care, I will say that *I* care, and
would complain quite a bit about such code.
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
email: forget about it http://web.torek.net/torek/index.html
Reading email is like searching for food in the garbage, thanks to spammers.
Chris Torek wrote:
In article <news:Lo********************@comcast.com>
Merrill & Michele <be********@comcast.net> wrote:Q) Good form has prototypes before the main call.
(I would take out the word "main" here: I have no idea what it is
doing in this sentence. I would say that "good form has prototypes
for functions before calls to those functions." It is also
generally wise to have those same prototypes appear before the
definition of the function as well, in more complicated situations
involving header files and separate compilation.)
These prototypes take arguments.
Yes. Note in particular that even a function that has no arguments
at all -- such as:
void print_header(void) {
puts("==== header ====");
}
for instance -- needs to have the "void" keyword in a prototype:
void print_header(void); /* prototype */
because writing this:
void print_header(); /* not a prototype! */
gives you a declaration, but not a prototype. (This is a historical
oddity having to do with adding prototypes in 1989, where C had
none before that. The ANSI committee folks decided not to change
the meaning of "old style" declarations, so they had to invent new
syntax: "the absence of arguments here means nothing about the
arguments; the presence of a `void' keyword means there are no
arguments".)
MUST EVERY keystroke (excepting white space) match the arguments
of the ultimate function call in order to have defined behavior? MPJ
No -- but it is often a good idea to have them match, even to the
very whitespace.
The part(s) of the prototype arguments that matter *to the compiler*
are the number and type of arguments:
void fA(void); /* zero arguments */
void fB(int, char *); /* two arguments: int, pointer-to-char */
void fC(double); /* one argument: double */
but the rest is useful to humans:
void do_some_operation(char *output, char *input, int operation);
void do_other_operation(char *input, int operation, char *output);
Here the compiler cares only that there are three arguments, two
of type "pointer to char" and one of type "int", but a person
writing code probably wants to know which "char *" is the "output"
and which one is the "input".
We could leave out the name "operation",
because there is only one "int", and if an operation has to be an
int, it is immediately obvious which of the one (count them 1)
"int" parameters is the "int" parameter. :-)
Of course, "good design" would also suggest that all of the
various "do an operation" functions take their input, output,
and operation parameters in the same places -- but having the
names, too, is a good thing.
Note that those who intentionally obfuscate their code (perhaps
in an attempt to obtain job security) might name their parameters
in a deliberately-confusing way:
void do_third_operation(char *kumquat, int output, char *lemon);
While the computer does not care, I will say that *I* care, and
would complain quite a bit about such code.
A reason I don't like parameter names in prototypes is because they
can be more subtly misleading without being noticed by the compiler.
void do_other_operation(char *input, int operation, char *output);
vs.
void do_other_operation(char *output, int operation, char *input);
I think looking at the prototype is the wrong place
to see how to call the function.
--
pete
On Sun, 14 Nov 2004 00:31:33 UTC, pete <pf*****@mindspring.com> wrote: Chris Torek wrote:
In article <news:Lo********************@comcast.com>
Merrill & Michele <be********@comcast.net> wrote:Q) Good form has prototypes before the main call.
(I would take out the word "main" here: I have no idea what it is
doing in this sentence. I would say that "good form has prototypes
for functions before calls to those functions." It is also
generally wise to have those same prototypes appear before the
definition of the function as well, in more complicated situations
involving header files and separate compilation.)
These prototypes take arguments.
Yes. Note in particular that even a function that has no arguments
at all -- such as:
void print_header(void) {
puts("==== header ====");
}
for instance -- needs to have the "void" keyword in a prototype:
void print_header(void); /* prototype */
because writing this:
void print_header(); /* not a prototype! */
gives you a declaration, but not a prototype. (This is a historical
oddity having to do with adding prototypes in 1989, where C had
none before that. The ANSI committee folks decided not to change
the meaning of "old style" declarations, so they had to invent new
syntax: "the absence of arguments here means nothing about the
arguments; the presence of a `void' keyword means there are no
arguments".)
MUST EVERY keystroke (excepting white space) match the arguments
of the ultimate function call in order to have defined behavior? MPJ
No -- but it is often a good idea to have them match, even to the
very whitespace.
The part(s) of the prototype arguments that matter *to the compiler*
are the number and type of arguments:
void fA(void); /* zero arguments */
void fB(int, char *); /* two arguments: int, pointer-to-char */
void fC(double); /* one argument: double */
but the rest is useful to humans:
void do_some_operation(char *output, char *input, int operation);
void do_other_operation(char *input, int operation, char *output);
Here the compiler cares only that there are three arguments, two
of type "pointer to char" and one of type "int", but a person
writing code probably wants to know which "char *" is the "output"
and which one is the "input".
We could leave out the name "operation",
because there is only one "int", and if an operation has to be an
int, it is immediately obvious which of the one (count them 1)
"int" parameters is the "int" parameter. :-)
Of course, "good design" would also suggest that all of the
various "do an operation" functions take their input, output,
and operation parameters in the same places -- but having the
names, too, is a good thing.
Note that those who intentionally obfuscate their code (perhaps
in an attempt to obtain job security) might name their parameters
in a deliberately-confusing way:
void do_third_operation(char *kumquat, int output, char *lemon);
While the computer does not care, I will say that *I* care, and
would complain quite a bit about such code.
A reason I don't like parameter names in prototypes is because they
can be more subtly misleading without being noticed by the compiler.
void do_other_operation(char *input, int operation, char *output);
vs.
void do_other_operation(char *output, int operation, char *input);
I think looking at the prototype is the wrong place
to see how to call the function.
No, its not. It is on YOU to document anything. A well documented
interface as a prototype is makes the usage of the fuction much
easier. Use simply exactly the same letters and numbers in both, the
prototype and definition and anything wents well.
When you have learned to design your programs instead of blindly
hacking around you would start with defining the interfaces, giving
the parameters selfspeaking names. In later stage you would copy the
prototypes to build the implementation of the function - having the
names of the formal parameters already ready.
At least when your editor knows what syntax expansion is you would
build the key files for that based on the prototype too - so you can
use abbrevations to expand them to full flagged parameter list,
helping you to remember what parameter is on which position, e.g.
Type waa+Alt+h would expand to
WinAddAtom(HATOMTBL hAtomTbl, PSZ pszAtomName);
and remember you that the first parameter needs to be a handle of an
atom table and the second to be the string to be converted to an atom.
Having good names selected for the parameter will save yopu often the
time to type them too.
So, even as the compiler ignores the names of the parameters YOU would
need them more often. That is why you needs self speaking names in
parameter lists. It is YOU who will save lots of typing and time when
using full flagged prototypes not only for system fuctions but for
functions used in your project only too.
--
Tschau/Bye
Herbert
Visit http://www.ecomstation.de the home of german eComStation
On Sun, 14 Nov 2004 00:31:33 GMT, in comp.lang.c , pete
<pf*****@mindspring.com> wrote:
A reason I don't like parameter names in prototypes is because they
can be more subtly misleading without being noticed by the compiler.
void do_other_operation(char *input, int operation, char *output);
vs.
void do_other_operation(char *output, int operation, char *input);
In my book, thats a bug. Inconsistency and documentation failures are just
as much bugs as coding errors.
I think looking at the prototype is the wrong place
to see how to call the function.
Since its where the compiler looks, its the most important place !
And often its the only place, other than the printed manual. Think "library
function".
--
Mark McIntyre
CLC FAQ <http://www.eskimo.com/~scs/C-faq/top.html>
CLC readme: <http://www.ungerhu.com/jxh/clc.welcome.txt>
----== Posted via Newsfeeds.Com - Unlimited-Uncensored-Secure Usenet News==---- http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----
Mark McIntyre wrote:
On Sun, 14 Nov 2004 00:31:33 GMT, in comp.lang.c , pete
<pf*****@mindspring.com> wrote:
A reason I don't like parameter names in prototypes is because they
can be more subtly misleading without being noticed by the compiler.
void do_other_operation(char *input, int operation, char *output);
vs.
void do_other_operation(char *output, int operation, char *input);
In my book, thats a bug. Inconsistency and documentation failures are just
as much bugs as coding errors.
I think looking at the prototype is the wrong place
to see how to call the function.
Since its where the compiler looks, its the most important place !
And often its the only place, other than the printed manual.
Think "library function".
OK. I'll think about it harder.
--
pete
At the risk of developing a larger reputation as a dullard, I would like to
continue this discussion at a level that I can understand. The following
code, I believe, produces exactly the behavior--with good style--that we're
looking for from K&R2 §5.
#include <stdio.h>
void swap(int *px, int *py);
int main(void){
int a = 3;
int b = 5;
swap(&a, &b);
printf ("a equals %d\n", a);
printf ("b equals %d\n", b);
return 0;
}
void swap(int *px, int *py){
int tmp = *px;
*px = *py;
*py = tmp;
}
Q1) Does anyone think that this is lacking in any fashion?
Q2) If prototype and declaration are not the same thing, then which line
number is which?
MPJ
P.S. I've read this thread, but I simply need to back up a bit.
Merrill & Michele wrote:
At the risk of developing a larger reputation as a dullard, I would like to
continue this discussion at a level that I can understand. The following
code, I believe, produces exactly the behavior--with good style--that we're
looking for from K&R2 §5.
#include <stdio.h>
void swap(int *px, int *py);
int main(void){
int a = 3;
int b = 5;
swap(&a, &b);
printf ("a equals %d\n", a);
printf ("b equals %d\n", b);
return 0;
}
void swap(int *px, int *py){
int tmp = *px;
*px = *py;
*py = tmp;
}
Q1) Does anyone think that this is lacking in any fashion?
Could use some indentation and maybe some blank lines.
#include <stdio.h>
void swap(int *px, int *py);
int main(void)
{
int a = 3;
int b = 5;
swap(&a, &b);
printf ("a equals %d\n", a);
printf ("b equals %d\n", b);
return 0;
}
void swap(int *px, int *py)
{
int tmp = *px;
*px = *py;
*py = tmp;
}
Q2) If prototype and declaration are not the same thing,
then which line number is which?
A prototype is one kind of declaration.
--
pete
pete <pf*****@mindspring.com> wrote: Merrill & Michele wrote:
At the risk of developing a larger reputation as a dullard, I would like to
continue this discussion at a level that I can understand. The following
code, I believe, produces exactly the behavior--with good style--that we're
looking for from K&R2 §5.
#include <stdio.h>
void swap(int *px, int *py);
int main(void){
int a = 3;
int b = 5;
swap(&a, &b);
printf ("a equals %d\n", a);
printf ("b equals %d\n", b);
return 0;
}
void swap(int *px, int *py){
int tmp = *px;
*px = *py;
*py = tmp;
}
Q1) Does anyone think that this is lacking in any fashion?
Could use some indentation and maybe some blank lines.
True, but this could be M$OE's fault rather than MPJ's. In any case,
there's nothing wrong with the code as such. Q2) If prototype and declaration are not the same thing,
then which line number is which?
A prototype is one kind of declaration.
And in this case, all declarations are also prototypes. The first is a
prototype and a declaration, but not a definition; the other two are all
three.
Richard
Merrill & Michele wrote: At the risk of developing a larger reputation as a dullard, I would like to
continue this discussion at a level that I can understand. The following
code, I believe, produces exactly the behavior--with good style--that we're
looking for from K&R2 §5.
#include <stdio.h>
void swap(int *px, int *py);
int main(void){
int a = 3;
int b = 5;
swap(&a, &b);
printf ("a equals %d\n", a);
printf ("b equals %d\n", b);
return 0;
}
void swap(int *px, int *py){
int tmp = *px;
*px = *py;
*py = tmp;
}
Q1) Does anyone think that this is lacking in any fashion?
Q2) If prototype and declaration are not the same thing, then which line
number is which?
MPJ
P.S. I've read this thread, but I simply need to back up a bit.
#include <stdio.h>
void swap(int*, int*); /* This is a prototype and declaration */
int main(void) {
int a = 3;
int b = 5;
swap(&a, &b);
printf("a equals %d\n", a);
printf("b equals %d\n", b);
return 0;
}
void swap(int *px, int *py) { /* This is the definition */
int tmp = *px;
*px = *py;
*py = tmp;
}
--
Joe Wright mailto:jo********@comcast.net
"Everything should be made as simple as possible, but not simpler."
--- Albert Einstein ---
In <H5********************@comcast.com> Joe Wright <jo********@comcast.net> writes: void swap(int*, int*); /* This is a prototype and declaration */
Incorrect: prototype is not a standalone concept in C. The correct
comment is: "This is a prototype declaration".
You can have prototype declarations and prototype definitions, but you
can't have standalone prototypes.
Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de
Currently looking for a job in the European Union
In <F7********************@comcast.com> "Merrill & Michele" <be********@comcast.net> writes: Minneslowta except to show that you're type A. To the topic though, would I
not be fine calling those prototypes *coconuts or *Krijn OR indeed would
void swap(int *a, int *a);
^ ^work swell? MPJ
It wouldn't. Even if the identifiers used in a function prototype
declaration are otherwise ignored, you're still not allowed to redeclare
an identifier at function prototype scope. Unless their names are
supposed to convey some useful information to the reader, you can simply
omit them in a function declaration:
void swap(int *, int *);
is just fine. If you insist on using identifiers, just use different
identifiers:
void swap(int *coconuts, int *Krijn);
These identifiers don't have to match the ones used in the function
definition, but it is considered good programming practice to have the
same identifiers in the declaration and in the definition (if you choose
to use identifiers in the declaration).
In programs where you need to swap variables of more than one type,
using functions, this function should be named int_swap() or iswap().
And, since you're relatively new here: arguing with Mark McIntyre is
generally neither fun nor instructive; he's our resident idiot.
Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de
Currently looking for a job in the European Union
"Dan Pop" <Da*****@cern.ch> wrote in message
news:cn**********@sunnews.cern.ch... In <F7********************@comcast.com> "Merrill & Michele"
<be********@comcast.net> writes:
Minneslowta except to show that you're type A. To the topic though,
would Inot be fine calling those prototypes *coconuts or *Krijn OR indeed would
void swap(int *a, int *a); ^ ^work swell? MPJ
It wouldn't. Even if the identifiers used in a function prototype
declaration are otherwise ignored, you're still not allowed to redeclare
an identifier at function prototype scope. Unless their names are
supposed to convey some useful information to the reader, you can simply
omit them in a function declaration:
void swap(int *, int *);
is just fine. If you insist on using identifiers, just use different
identifiers:
void swap(int *coconuts, int *Krijn);
These identifiers don't have to match the ones used in the function
definition, but it is considered good programming practice to have the
same identifiers in the declaration and in the definition (if you choose
to use identifiers in the declaration).
It is not considered the best of style by me. It makes code 'overcody' to
repeat identifiers. When I see a bunch of fruit-flying Dutchmen, then I
know that this is where I was telling my self something.
In programs where you need to swap variables of more than one type,
using functions, this function should be named int_swap() or iswap().
That's still down the road a bit, but this puts you in the fairway.
And, since you're relatively new here: arguing with Mark McIntyre is
generally neither fun nor instructive; he's our resident idiot.
Well then he's closer to my abilities than I thought. MPJ Da*****@cern.ch (Dan Pop) writes: In <H5********************@comcast.com> Joe Wright
<jo********@comcast.net> writes:
void swap(int*, int*); /* This is a prototype and declaration */
Incorrect: prototype is not a standalone concept in C. The correct
comment is: "This is a prototype declaration".
You can have prototype declarations and prototype definitions, but you
can't have standalone prototypes.
C99 6.2.1p2 says:
A _function prototype_ is a declaration of a function that
declares the types of its parameters.
Since "function prototype" is in italics, this is the definition of
the term. We can assume, I think, that "prototype" is equivalent to
"function prototype"; the standard uses the term "prototype" by itself
in this sense in a number of places. A prototype is a kind of
declaration.
So Joe Wright is quite correct. This:
void swap(int*, int*);
is a declaration; it's also a prototype.
It would also be correct to say that it's a "prototype declaration";
the standard uses that phrase in an example in 6.9.1p14.
(Interestingly, it uses the term to refer to a function definition
that includes a prototype.)
--
Keith Thompson (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. Da*****@cern.ch (Dan Pop) writes:
[...] And, since you're relatively new here: arguing with Mark McIntyre is
generally neither fun nor instructive; he's our resident idiot.
Dan Pop is our resident curmudgeon. He seems to enjoy insulting
people for some reason. I suggest you ignore his abuse and decide for
yourself who's an idiot and who isn't.
--
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.
"Keith Thompson" <ks***@mib.org> wrote in message
news:ln************@nuthaus.mib.org... Da*****@cern.ch (Dan Pop) writes:
[...] And, since you're relatively new here: arguing with Mark McIntyre is
generally neither fun nor instructive; he's our resident idiot.
Dan Pop is our resident curmudgeon. He seems to enjoy insulting
people for some reason. I suggest you ignore his abuse and decide for
yourself who's an idiot and who isn't.
Mr. Pop's brilliant and passionate to a fault. Let's not hold it against
him. MPJ
Dan Pop wrote: In <H5********************@comcast.com> Joe Wright <jo********@comcast.net> writes:
void swap(int*, int*); /* This is a prototype and declaration */
Incorrect: prototype is not a standalone concept in C. The correct
comment is: "This is a prototype declaration".
You can have prototype declarations and prototype definitions, but you
can't have standalone prototypes.
Dan
You're a tough judge my friend. I wonder, may I ask you for Chapter
and Verse with any reference to 'standalone prototypes' or any
indication that the word 'prototype' is not a noun (English: the
name of a thing.) in its own right?
In N869 every reference to 'prototype' has it a noun. The word
'standalone' does not occur even once.
--
Joe Wright mailto:jo********@comcast.net
"Everything should be made as simple as possible, but not simpler."
--- Albert Einstein ---
In <LZ********************@comcast.com> Joe Wright <jo********@comcast.net> writes: Dan Pop wrote: In <H5********************@comcast.com> Joe Wright <jo********@comcast.net> writes:
void swap(int*, int*); /* This is a prototype and declaration */
Incorrect: prototype is not a standalone concept in C. The correct
comment is: "This is a prototype declaration".
You can have prototype declarations and prototype definitions, but you
can't have standalone prototypes.
Dan
You're a tough judge my friend. I wonder, may I ask you for Chapter
and Verse with any reference to 'standalone prototypes' or any
indication that the word 'prototype' is not a noun (English: the
name of a thing.) in its own right?
In N869 every reference to 'prototype' has it a noun. The word
'standalone' does not occur even once.
Now, check the *definition* of "prototype" in the C standard and you
might get the point.
Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de
Currently looking for a job in the European Union
In <ln************@nuthaus.mib.org> Keith Thompson <ks***@mib.org> writes: Da*****@cern.ch (Dan Pop) writes: In <H5********************@comcast.com> Joe Wright
<jo********@comcast.net> writes:
void swap(int*, int*); /* This is a prototype and declaration */
Incorrect: prototype is not a standalone concept in C. The correct
comment is: "This is a prototype declaration".
You can have prototype declarations and prototype definitions, but you
can't have standalone prototypes.
C99 6.2.1p2 says:
A _function prototype_ is a declaration of a function that
declares the types of its parameters.
Since "function prototype" is in italics, this is the definition of
the term. We can assume, I think, that "prototype" is equivalent to
"function prototype"; the standard uses the term "prototype" by itself
in this sense in a number of places. A prototype is a kind of
declaration. ^^^^^^^^^^^^^^^^^^^^^^^^
^^^^^^^^^^^
Precisely my point.
So Joe Wright is quite correct. This:
void swap(int*, int*);
is a declaration; it's also a prototype.
It is a prototype declaration. If saying "this is a declaration and a
declaration" makes sense in English, then Joe Wright is quite correct.
Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de
Currently looking for a job in the European Union
In <ln************@nuthaus.mib.org> Keith Thompson <ks***@mib.org> writes: Da*****@cern.ch (Dan Pop) writes:
[...] And, since you're relatively new here: arguing with Mark McIntyre is
generally neither fun nor instructive; he's our resident idiot.
Dan Pop is our resident curmudgeon. He seems to enjoy insulting
people for some reason. I suggest you ignore his abuse and decide for
yourself who's an idiot and who isn't.
Anyone who attempted to argue with Mark McIntyre on a rational basis
reached the same conclusion, usually expressed under the euphemism
"you cannot read". The last one I remember was P.J. Plauger.
Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de
Currently looking for a job in the European Union
"Dan Pop" <Da*****@cern.ch> wrote in message
news:cn**********@sunnews.cern.ch... In <ln************@nuthaus.mib.org> Keith Thompson <ks***@mib.org> writes:
Da*****@cern.ch (Dan Pop) writes:
[...] And, since you're relatively new here: arguing with Mark McIntyre is
generally neither fun nor instructive; he's our resident idiot.
Dan Pop is our resident curmudgeon. He seems to enjoy insulting
people for some reason. I suggest you ignore his abuse and decide for
yourself who's an idiot and who isn't.
Anyone who attempted to argue with Mark McIntyre on a rational basis
reached the same conclusion, usually expressed under the euphemism
"you cannot read". The last one I remember was P.J. Plauger.
True or not, at least your insults are straightforward, unlike the
henpecking that some equate to criticism.
I'm going to shuffle with my derangement code now. The thing I can't figure
out is how to pass the address of buysfor[0] back to the prog that called
it. Pointers have me tied up in knots right now. MPJ
On Wed, 10 Nov 2004 22:37:41 -0600, Merrill & Michele wrote:
.... /* initialize and permute */
for (i = 0; i < FAMSIZ; ++ i) buysfor[i] = i;
m = 0;
while (m < FAMSIZ){
t = rand();
if (t > topnum) continue;
n = t % FAMSIZ;
swap (&buysfor[m] , &buysfor[n]);
++ m;
}
This clearly doesn't guarantee a derangement, but with a small
modification it can. This is very similar to a naive shuffle
algorithm, and the fix is essentially the same.
/*out to console*/
putchar('\n');
for (i = 0;i < FAMSIZ; i ++) printf("%3d",i);
putchar('\n');
for (i = 0;i < FAMSIZ; i ++) printf("%3d",buysfor[i]);
putchar('\n');
/* remove collisions */
for (m = 0; m < FAMSIZ; ++ m){
while (buysfor[m] == m){
t = rand();
if (t > topnum) continue;
n = t % FAMSIZ;
if ((n == m) || (buysfor[m] == n)) continue;
swap (&buysfor[m] , &buysfor[n]);
}
}
Well I guess that works. But can you be sure that
1. this could generate every possible derangement? Maybe,
but prove it.
2. Every possible derangement is equally likely? Probably not,
even with the work you did with topnum.
....
I think I finally got it. I couldn't get my head around the do-while
control loops. MPJ
Try this:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define FAMSIZ 20 /* between 2 and 2,000 */
static int randrange(int range);
int main(void){
int buysfor[FAMSIZ];
int i;
/* get vanilla rand started well */
srand((unsigned)time(NULL));
for (i = 0; i < 9; ++i) (void)rand();
/* derangement */
buysfor[0] = 0;
for (i = 1; i < FAMSIZ; ++i) {
int t = randrange(i);
buysfor[i] = buysfor[t];
buysfor[t] = i;
}
/* out to console */
putchar('\n');
for (i = 0;i < FAMSIZ; i++) printf("%3d",i);
putchar('\n');
for (i = 0;i < FAMSIZ; i++) printf("%3d",buysfor[i]);
putchar('\n');
return 0;
}
/* Wrapper for rand() which returns a random number
0 <= number < range where each value is equally likely
as long as rand() returns values between 0 and RAND_MAX
with equal probability. range <= RAND_MAX.
*/
static int randrange(int range)
{
int num, high;
high = RAND_MAX - RAND_MAX % range;
while ((num = rand()) >= high)
;
return (num / (RAND_MAX / range));
} Da*****@cern.ch (Dan Pop) writes:
[...] Anyone who attempted to argue with Mark McIntyre on a rational basis
reached the same conclusion, usually expressed under the euphemism
"you cannot read". The last one I remember was P.J. Plauger.
Hmm. I just did a groups.google.com search for Mark's postings to
comp.lang.c and read a more or less random sampling of the recent
ones. Everything I read seemed perfectly sensible.
I'm sure I've read a lot of Mark's articles in the past, but I haven't
kept mental track of who posted what, so I can't really judge him on
that basis.
Perhaps he's improved recently, or perhaps I picked a
non-representative sample. In any case, I'll continue to judge each
article on its own merits and not (except for a few special cases) on
the basis of anyone's opinion of the poster. (The "special cases" do
not include anyone participating in, or mentioned in, this thread.)
--
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.
On Tue, 16 Nov 2004 17:54:02 -0600, in comp.lang.c , "Merrill & Michele"
<be********@comcast.net> wrote:
"Keith Thompson" <ks***@mib.org> wrote in message
news:ln************@nuthaus.mib.org... Da*****@cern.ch (Dan Pop) writes:
[...] > And, since you're relatively new here: arguing with Mark McIntyre is
> generally neither fun nor instructive; he's our resident idiot.
Dan Pop is our resident curmudgeon. He seems to enjoy insulting
people for some reason. I suggest you ignore his abuse and decide for
yourself who's an idiot and who isn't.
Mr. Pop's brilliant and passionate to a fault.
True. I do wish he'd stick to C tho.
Let's not hold it against him.
On the other hand, he's very very egotistical and vindictive. Treat
anything he says about anyone else with a pinch of salt.
--
Mark McIntyre
CLC FAQ <http://www.eskimo.com/~scs/C-faq/top.html>
CLC readme: <http://www.ungerhu.com/jxh/clc.welcome.txt>
----== Posted via Newsfeeds.Com - Unlimited-Uncensored-Secure Usenet News==---- http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----
On Wed, 17 Nov 2004 19:47:06 GMT, in comp.lang.c , Keith Thompson
<ks***@mib.org> wrote: Da*****@cern.ch (Dan Pop) writes:
[...] Anyone who attempted to argue with Mark McIntyre on a rational basis
reached the same conclusion, usually expressed under the euphemism
"you cannot read". The last one I remember was P.J. Plauger.
Hmm. I just did a groups.google.com search for Mark's postings to
comp.lang.c and read a more or less random sampling of the recent
ones. Everything I read seemed perfectly sensible.
I expect he's thinking of the "do we cast malloc" debate that went on 10
months ago, during which many of us got a bit excited at PJ's apparent
position that casting malloc was perfectly alright. I believe at one point
PJ even seemed to be asserting that the cast was *necessary* in case there
were no valid conversion from void* to some other pointer type. Hmm.
T'would be nice tho if other people would stop holding grudges, and grow
up.
--
Mark McIntyre
CLC FAQ <http://www.eskimo.com/~scs/C-faq/top.html>
CLC readme: <http://www.ungerhu.com/jxh/clc.welcome.txt>
----== Posted via Newsfeeds.Com - Unlimited-Uncensored-Secure Usenet News==---- http://www.newsfeeds.com The #1 Newsgroup Service in the World! 120,000+ Newsgroups
----= East and West-Coast Server Farms - Total Privacy via Encryption =----
"Lawrence Kirby" <lk****@netactive.co.uk> wrote in message
news:pa****************************@netactive.co.u k... On Wed, 10 Nov 2004 22:37:41 -0600, Merrill & Michele wrote:
...
/* initialize and permute */
for (i = 0; i < FAMSIZ; ++ i) buysfor[i] = i;
m = 0;
while (m < FAMSIZ){
t = rand();
if (t > topnum) continue;
n = t % FAMSIZ;
swap (&buysfor[m] , &buysfor[n]);
++ m;
}
This clearly doesn't guarantee a derangement, but with a small
modification it can. This is very similar to a naive shuffle
algorithm, and the fix is essentially the same.
/*out to console*/
putchar('\n');
for (i = 0;i < FAMSIZ; i ++) printf("%3d",i);
putchar('\n');
for (i = 0;i < FAMSIZ; i ++) printf("%3d",buysfor[i]);
putchar('\n');
/* remove collisions */
for (m = 0; m < FAMSIZ; ++ m){
while (buysfor[m] == m){
t = rand();
if (t > topnum) continue;
n = t % FAMSIZ;
if ((n == m) || (buysfor[m] == n)) continue;
swap (&buysfor[m] , &buysfor[n]);
}
}
Well I guess that works. But can you be sure that
1. this could generate every possible derangement? Maybe,
but prove it.
2. Every possible derangement is equally likely? Probably not,
even with the work you did with topnum.
...
I think I finally got it. I couldn't get my head around the do-while
control loops. MPJ
Try this:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define FAMSIZ 20 /* between 2 and 2,000 */
static int randrange(int range);
int main(void){
int buysfor[FAMSIZ];
int i;
/* get vanilla rand started well */
srand((unsigned)time(NULL));
for (i = 0; i < 9; ++i) (void)rand();
/* derangement */
buysfor[0] = 0;
for (i = 1; i < FAMSIZ; ++i) {
int t = randrange(i);
buysfor[i] = buysfor[t];
buysfor[t] = i;
}
/* out to console */
putchar('\n');
for (i = 0;i < FAMSIZ; i++) printf("%3d",i);
putchar('\n');
for (i = 0;i < FAMSIZ; i++) printf("%3d",buysfor[i]);
putchar('\n');
return 0;
}
/* Wrapper for rand() which returns a random number
0 <= number < range where each value is equally likely
as long as rand() returns values between 0 and RAND_MAX
with equal probability. range <= RAND_MAX.
*/
static int randrange(int range)
{
int num, high;
high = RAND_MAX - RAND_MAX % range;
while ((num = rand()) >= high)
;
return (num / (RAND_MAX / range));
}
I need a little time to digest this. My claim is that for most values of
FAMSIZ (range), we need to toss out some values for rand. My opinion as to
how many we toss out has differed with others by one. This difference can
be reconciled by comparing with strict inequality, but I see you have a >=.
(I can keep typing til the boy finishes his bottle.) RAND_MAX is usually 0
x 7fff = 32767 and FAMSIZ is usually going to be 52. That would make high =
32767 - 32767 % 52 = 32767 - 7 = 32760 . For kicks and giggles, let's
doublecheck. 32760 % 52 = 0 . I just don't see how it is you don't have
one too many zeros because rand() is fine with returning a zero.
As far as program control goes, I'm completely lost. You pass range, which
is FAMSIZ in my code and rely on the peculiarities of c to have an integer
returned. I'd prattle on about the things I don't get, but .... MPJ
In <va********************************@4ax.com> Mark McIntyre <ma**********@spamcop.net> writes: On Wed, 17 Nov 2004 19:47:06 GMT, in comp.lang.c , Keith Thompson
<ks***@mib.org> wrote:
Da*****@cern.ch (Dan Pop) writes:
[...] Anyone who attempted to argue with Mark McIntyre on a rational basis
reached the same conclusion, usually expressed under the euphemism
"you cannot read". The last one I remember was P.J. Plauger.
Hmm. I just did a groups.google.com search for Mark's postings to
comp.lang.c and read a more or less random sampling of the recent
ones. Everything I read seemed perfectly sensible.
I expect he's thinking of the "do we cast malloc" debate that went on 10
months ago, during which many of us got a bit excited at PJ's apparent
position that casting malloc was perfectly alright.
Nope, I'm thinking of a more recent one, on a different topic.
Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de
Currently looking for a job in the European Union
On Thu, 18 Nov 2004 07:37:51 -0600, Merrill & Michele wrote:
"Lawrence Kirby" <lk****@netactive.co.uk> wrote in message
....
buysfor[0] = 0;
for (i = 1; i < FAMSIZ; ++i) {
int t = randrange(i);
buysfor[i] = buysfor[t];
buysfor[t] = i;
}
This looks like a case of premature publication by me. :-)
I believe this does always produce a derangement, but it
doesn't produce all possible derangements because in some
cases an order N derangement can't be constructed from an
order N-1 derangement in this way (eg. 2 3 0 1 would have
to be constructed from 2 1 0 which isn't a derangement).
So it fails to meet my conditions. Those can be met with
the method of: perform a random shuffle, repeat IN FULL while
the result is not a derangement. The random shuffle needs
to be implemented correctly to make all permutations equally
likely.
An algorithm that meets my conditions though direct
construction of a derangement (as I attempted) looks to be
more "interesting".
....
static int randrange(int range)
{
int num, high;
high = RAND_MAX - RAND_MAX % range;
while ((num = rand()) >= high)
;
return (num / (RAND_MAX / range));
}
I need a little time to digest this. My claim is that for most values of
FAMSIZ (range), we need to toss out some values for rand. My opinion as to
how many we toss out has differed with others by one. This difference can
be reconciled by comparing with strict inequality, but I see you have a >=.
(I can keep typing til the boy finishes his bottle.) RAND_MAX is usually 0
x 7fff = 32767 and FAMSIZ is usually going to be 52. That would make high =
32767 - 32767 % 52 = 32767 - 7 = 32760 . For kicks and giggles, let's
doublecheck. 32760 % 52 = 0 . I just don't see how it is you don't have
one too many zeros because rand() is fine with returning a zero.
After the while loop you will have a value between 0 and 32759 inclusive
i.e. 32760 distinct values. 32767/52 is 630 and 630*52 is 32760. The range
of values after the loop is divided into 52 subranges of 630 values, the
final division by 630 maps 0-629 onto 0, 630-1259 onto 1, ..., 32130-32759
onto 51.
As far as program control goes, I'm completely lost. You pass range,
which is FAMSIZ in my code
It isn't in my code, which is key point to why it generates derangements
directly. randrange(range) is just a drop-in replacement for (rand() %
range), but it is potentially better behaved in the numbers it generates.
and rely on the peculiarities of c to have an
integer returned. I'd prattle on about the things I don't get, but ....
Well it relies on simple C constructs, I'm not sure what peculiarities you
are referring to although the calculation is perhaps non-obvious. It is
perhaps not *quite* as efficient as it could be when mathematically
RAND_MAX+1 is exactly divisible by range, but calculations involving
RAND_MAX+1 can be awkward in C's integer arithmetic so a simplification
has been made.
Lawrence
"Lawrence Kirby" <lk****@netactive.co.uk> wrote in message
news:pa****************************@netactive.co.u k... On Thu, 18 Nov 2004 07:37:51 -0600, Merrill & Michele wrote:
"Lawrence Kirby" <lk****@netactive.co.uk> wrote in message
...
buysfor[0] = 0;
for (i = 1; i < FAMSIZ; ++i) {
int t = randrange(i);
buysfor[i] = buysfor[t];
buysfor[t] = i;
}
This looks like a case of premature publication by me. :-)
I believe this does always produce a derangement, but it
doesn't produce all possible derangements because in some
cases an order N derangement can't be constructed from an
order N-1 derangement in this way (eg. 2 3 0 1 would have
to be constructed from 2 1 0 which isn't a derangement).
So it fails to meet my conditions. Those can be met with
the method of: perform a random shuffle, repeat IN FULL while
the result is not a derangement. The random shuffle needs
to be implemented correctly to make all permutations equally
likely.
An algorithm that meets my conditions though direct
construction of a derangement (as I attempted) looks to be
more "interesting".
The only way I could get it was to start with any map of a set onto itself,
permute randomly and remove collisions in separate steps. static int randrange(int range)
{
int num, high;
high = RAND_MAX - RAND_MAX % range;
while ((num = rand()) >= high)
;
return (num / (RAND_MAX / range));
}
I need a little time to digest this. My claim is that for most values
of FAMSIZ (range), we need to toss out some values for rand. My opinion as
to how many we toss out has differed with others by one. This difference
can be reconciled by comparing with strict inequality, but I see you have a
=. (I can keep typing til the boy finishes his bottle.) RAND_MAX is
usually 0 x 7fff = 32767 and FAMSIZ is usually going to be 52. That would make
high = 32767 - 32767 % 52 = 32767 - 7 = 32760 . For kicks and giggles, let's
doublecheck. 32760 % 52 = 0 . I just don't see how it is you don't
have one too many zeros because rand() is fine with returning a zero.
After the while loop you will have a value between 0 and 32759 inclusive
i.e. 32760 distinct values. 32767/52 is 630 and 630*52 is 32760. The range
of values after the loop is divided into 52 subranges of 630 values, the
final division by 630 maps 0-629 onto 0, 630-1259 onto 1, ..., 32130-32759
onto 51.
If you have 0 through 32759 after the while loop, then you're good to go. I
don't see how that is achieved with while((num = rand()) >= high), but the
operative part of the sentence is "I don't see." As far as program control goes, I'm completely lost. You pass range,
which is FAMSIZ in my code
It isn't in my code, which is key point to why it generates derangements
directly. randrange(range) is just a drop-in replacement for (rand() %
range), but it is potentially better behaved in the numbers it generates.
and rely on the peculiarities of c to have an
integer returned. I'd prattle on about the things I don't get, but ....
Well it relies on simple C constructs, I'm not sure what peculiarities you
are referring to although the calculation is perhaps non-obvious.
Those simple C constructs send me scrambling for a textbook. Off to Ted's
MPJ
It is perhaps not *quite* as efficient as it could be when mathematically
RAND_MAX+1 is exactly divisible by range, but calculations involving
RAND_MAX+1 can be awkward in C's integer arithmetic so a simplification
has been made. This thread has been closed and replies have been disabled. Please start a new discussion. |
