/* Random generation of permutations

Maurice.Clerc@WriteMe.com
Last update 2005-03-27
*/


/***************************************************************************
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 ***************************************************************************/

#include <stdio.h>
#include <math.h>
#include <cstdlib>

#define N_max 30	// Max. length of the permutation

// Structure(s)
struct int_list	{int size;int l[N_max];};

// Subprograms
int		alea();
struct int_list gener_permut(int N);

// File(s)
FILE *f;

void main()
{
	int j,m,M,N;
struct int_list permut;

f=fopen("f_result.txt","w");

//for(j=0;j<3000;j++) fprintf(f,"%i\n",alea(1,5)); goto end; // Random generator test


printf("\nN? (0 = END): "); scanf("%i",&N);
if(N<=0) goto end;
printf("\nHow many permutations? (0 = END): "); scanf("%i",&M);
if(M<=0) goto end;

for(m=0;m<M;m++)
{
	permut=gener_permut(N);
	printf("\n");
	for(j=0;j<N;j++) printf("%i ",permut.l[j]);

	for(j=0;j<N;j++) fprintf(f,"%i ",permut.l[j]);
	fprintf(f,"\n");


}

	printf("\n");

end:;
}

//=============================================== ALEA
int alea(n1,n2)
{	// Pseudo-random integer in [n1, n2]
	// Note the "n2+1" ...
	
	int n;
	double x,x1,x2;
	n=(int)(n1+(n2+1-n1)*(double)rand()/(double)RAND_MAX);

	return n;
}

//=============================================== GENER_PERMUT
struct int_list gener_permut(int N)
{
	int i,j,n,Nt;
	int r;

	struct int_list permut;
	int used[N_max];
	
for(j=0;j<N;j++) used[j]=0;
n=0;

/*
next_n:
i=alea(0,N-1);
sign=1-2*alea(0,1);

//printf("\n i %i",i);

j=i;
next_j:
if(used[j]==0) 
{
	permut.l[n]=j+1; n=n+1;
	used[j]=1;
	if(n<N) goto next_n;
}
else
{
	j=j+sign; if(j==N) j=0; if(j==-1) j=N-1;
	goto next_j;
}
*/
Nt=N;

next_n:
i=alea(1,Nt);
//printf("\n Nt %i, i %i",Nt,i);
//printf("\n used: ");
//for(j=0;j<N;j++) printf("%i ",used[j]);
r=0;
for(j=0;j<N;j++)
{
	if(used[j]>0) continue;
		r=r+1;
		if(r<i) continue;
			permut.l[n]=j+1;n=n+1;
			used[j]=1;
			if(n<N) {Nt=Nt-1;goto next_n;}
}

permut.size=N;	
return permut;
}