rookie's question: random permutation generator

[vigo332]

Hi, Initially I wanted to generate a random permutation from 1 to n, and n can be a very big number, say 1M, I tried the following code I wrote, but it has its limit to 25199, the problem is with this line j=d%rand()%(n-t); but I don't know how to fix it. When I wrote a simpler printf("%ld",d%rand()); it has no limit at all.

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

long *perm(long n){
	long *a=malloc(4*n*sizeof(long));
	long k;
	time_t b;
	b=time(NULL);
	long d;
	d=(long)b;
	for(k=0;k<n;k++)a[k]=k+1;			//a[]is from 1 to n;
	long t,q;
	for(q=0;q<1;q++){  //we put q is to do q times random exchange, greater q will decrease the limit.
	      for(t=0;t<n;t++){
		long j;
		j=d%rand()%(n-t);    // the problem is with this line
		long temp;
		temp=a[t];
		a[t]=a[t+j];
		a[t+j]=temp;		
		} 
	}
	return a;
	}

void printarray(long n,long *a)
{
	long k=0;
	for(k=0;k<n;k++){
		if(k%10==0)
	             printf("\n");
	             printf("%d\t",a[k]);}
}

long randperm(long n){
	long *a;
	a=perm(n);
	printarray(n,a);
	}

main(){
long n;
scanf("%ld",&n);
randperm(n);}

[tabstop]

Why do you believe there is a problem with that line, and why do you believe the limit is 25199? (That is, what behavior are you seeing?)

(EDIT to add: Also, make sure you are on a system where RAND_MAX exceeds 32767.)

[anduril462]

Fix your indentation, it makes your code very difficult to follow. Also, put some spaces around identifiers and operators so it's more legible too.

It's int main(void), and return an int at the end, usually 0 for succcess.

long n;
randperm(n);

You're using n uninitialized. n is a stack variable, and it can have any value when you start the main function. That results in undefined behavior, which can be anything or nothing at all, including the problem you described.

[vigo332]

tabstop, I have tried several times that when n is greater than 25199, it can be compiled on GCC successfully but does not run; the max of rand() is 32767, but that is OK, the rand() will repeat when it is called more than 32767 times.

[tabstop]

If your main is as you posted it, then you need to heed anduril's advice.

You still need to actually say what "does not work" could possibly mean.

If rand_max is 32767 your algorithm is broken, because you need to be able to generate numbers as large as n.

[vigo332]

I changed the main to long main(void) or long main(), however neither works; I mean it can be compiled and can allow input the n, but does not print anything more and pops out a window say this .exe has stopped working.
I tried to test rand() in another simple way, to print 1000000 rand() numbers out, and it prints 1000000number within 0-32767 of course they repeat. so the rand() in this code is not supposed to be the problem. thanks

[anduril462]

I changed the main to long main(void) or long main(), however neither works;

Fail! I said "int main(void)". The article I linked to (that red text was a link, you did click it, right?) discussed it in length and told you it should be "int main" too.

I mean it can be compiled and can allow input the n, but does not print anything more and pops out a window say this .exe has stopped working.

It could have said "stopped working" because you declared main wrong and failed to return a valid value. Either you don't have a return, which is bad (read the article), or you declared it to return long, and return 4 bytes of zeros on a system expecting only 2 bytes worth of return value. Either way, it's bad. Try this out for your main:

void printarray(long n,long *a)
{
...
        printf("%ld\t",a[k]);  // printf needs an ell in the format (%ld) to specify a long integer
}

void randperm(long n){  // you don't return anything, so you need void here
    long *a;
    a=perm(n);
    printarray(n,a);
    free(a);  // be a good boy and free the memory when you're done
}

int main(void)
{
    long n = 10;
    randperm(n);

    return 0;
}

Those changes made it work for me.

[iMalc]

A random permutation is otherwise known as a random shuffle.

	b=time(NULL);
	long d;
	d=(long)b;
		j=d%rand()%(n-t);    // the problem is with this line

That's not how you use rand()

You first use srand to seed the generator, once, in main. Then you just use rand() % range. There should be no % before that.

You're over-allocating by a factor of four. Get rid of that 4* in that malloc. *sizeof(long) already takes care of the element size.

[CommonTater]

I changed the main to long main(void) or long main(), however neither works; I mean it can be compiled and can allow input the n, but does not print anything more and pops out a window say this .exe has stopped working.
I tried to test rand() in another simple way, to print 1000000 rand() numbers out, and it prints 1000000number within 0-32767 of course they repeat. so the rand() in this code is not supposed to be the problem. thanks

Your program's main function is required to return an integer... as in int main (void) or int main (int argc, char *argv[])


If you want random numbers bigger than RAND_MAX ... multiply.

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

long long int rndval;  // 64 bit value

srand(time(NULL));  // do this exactly once

// to make a big random number
rndval = rand() * 12345;

// to make a small random number
rndval = rand() % 12345;

Are you by any chance working with Turbo C?