#include "stdio.h"
#include "math.h"
#define MAXDOUBLE 100000000000000

int distribute (int, int, int);	// to calculate all possible distribute types
int myoutput (int, double);				// to output each possible distribution to files

int pots[256];			// distribution of balls in a serial of pots, global variable
double typenumber=0;	// how many kind of distribution possibility in total?
int overflow=0;			// "overfloat=0" indicates ok; 
						// "overfloat=1" indicates "typenumber" exceeds the maximum limit of double float

double nx1=0, nx2=0, nd2=0;

FILE *fp1;						// output file=statistics.txt

int main ()
{
	if( (fp1=fopen("statistics.txt", "w+")) == NULL )
	{
		printf("\nERROR: can't create new file\n");
		return(-1);
	}

	int ball=0, pot=0, index=0, i=0;
	double mean=0, div=0;

	printf("please input the total number of balls: ");
	scanf ("%d", &ball);
	printf ("please input the total number of pots: ");
	scanf ("%d", &pot);

	if (ball<=0 || pot<=0)
	{
		printf("\nINPUT ERROR!!!\n");
		return(-2);
	}

	printf ("\nlisting all the possible distribution types. please wait......\n");

	if ( distribute(ball, pot, index) >=0 )		// after a successful distribution calculation
	{
		mean=(nx2/typenumber)/ball;
		div=(sqrt(nd2/typenumber))/ball;

		printf("\n\nmean= %f\n", mean);
		printf("number of all possibilities= %f\n", typenumber);
		printf("standard deviation= %f\n", div);

		fprintf(fp1, "number of balls= %d\n", ball);
		fprintf(fp1, "number of pots= %d\n", pot);

		fprintf(fp1, "mean= %f\n", mean);
		fprintf(fp1, "standard deviation= %f\n", div);

		fclose(fp1);
		printf ("\nEND: SUCCESS!\n");	
		printf("check out \"statistics.txt\" for results\n");
		printf("\nplease press \"enter\" to end this program\n");
		getchar();
		getchar();
		return(0);
	}

	else	// otherwise, if there's an error during calculation
	{
		fclose(fp1);
		printf ("\nEND: AN ERROR OCCURED DURING CALCULATION!\n");	
		getchar();
		getchar();
		return(-3);
	}
}


int distribute (int ball, int pot, int index)
// ball numbers are sorted descendingly
// ball: total ball number left;
// pot: total pot number left;
// index: the starting pot number for distribution.

{
	int i, j, prepot;		// prepot: the ball number of the previous pot;

	if ( pot <= 0 || index<0) return (-1);	// error

	double k=0, average = (double)ball/(double)pot-exp(-30);

	if (index>0) prepot=pots[index-1];	// if it is not a first pot
	else prepot=9999;	// if it's first pot

	if(ball<0) 
	{
		printf("\nERROR!\n");
		return(-1);		// error
	}
	else if(ball==0)	// no ball left
	{
		for (; pot>0; pot--, index++)
			pots[index]=0;		// index will point to a null pot next to the last
				
		k=0;
		for (i=0; i<index; i++)
			for (j=0; j<index; j++)
				k+= abs(pots[i]-pots[j]);
		k*=0.5/(index-1);

		if ( myoutput(index, k) < 0 ) 
			return (-2);	// if an output error
		return(0);
	}
	else
	{
		if((double)prepot<average) // previous pot must have more balls than average (or equal)
		{
			printf("\nERROR!!\n");
			return(-3);		// error if less
		}

		pots[index]= ball; 
		if(prepot<ball) pots[index] = prepot; 
		// ball number of the first pot set to the minimun of total and previous pot

		for (; pots[index] > average && pots[index] > 0; --pots[index])
		{
			if (pot>1)	distribute (ball-pots[index], pot-1, index+1); 
			// if there are still pots left, continue to calculate the remaining

			if (pot==1) // after one successful distribute
			{
				k=0;
				for (i=0; i<index+1; i++)
					for (j=0; j<index+1; j++)
						k+= abs(pots[i]-pots[j]);
				k*=0.5/index;
				if ( myoutput(index+1, k) < 0 ) return (-2);
			}
			// all pots full
		}

		return (0);
	}
}


int myoutput(int index, double k)
{
	// k is discription of the concentration of wealth for each distribution possibility; index is the number of pots;

	nx1=nx2;	// save old mean*n
	nx2=nx1+k;	// new mean*n

	if (typenumber>1e-5)
		nd2+= (k)*(k)+nx1*nx1/typenumber-nx2*nx2/(typenumber+1); //new div*div*n
	else
		nd2=0; // first one;

	printf("\r%d\t%f", pots[0], k);
	
	typenumber+=1;
	if (typenumber>MAXDOUBLE) 
	// double float will provide max of 15-16 bit accuracy, result may not be reliable if over this limit
		if (overflow==0)
		{
			printf("\n!!! WARNING: typenumber (double float) may overflow, be cautious with the results !!!\n");
			overflow=1;
		}

	return(0);
}