import java.applet.Applet;
	import java.awt.*;    // import the java.awt package
	import java.awt.event.*;  // import the java.awt.event package
import java.util.*;

import javax.swing.JCheckBox;


	public class Inversions extends Applet implements ActionListener 
	{	
	  	static int max = 10000;
		static long total = 0;
		static long npermut = 0;
		static double prob[] = new double[max+1];
		static int cases [] = new int[max+1];
		static int minCase= max;
		static int maxCase=0;
		static int n=4;
		static int m =100;
		JCheckBox muestreo;
		Label prompt;      // message that prompts user to input
		TextField input;   // input values are entered here
		Label prompt2;
		TextField input2;



	static int inversions(int v[] )
	{
	int cont = 0;
		for(int i =0; i<v.length -1 ; i++ )
		{
			for(int j = i+1 ; j<v.length ; j++)
			{
			if(v[i] < v[j]) cont ++;
			}
	}
	return cont;
	}





		
	static void swap (int v[], int i, int j) {
		int	t;
		t = v[i];
		v[i] = v[j];
		v[j] = t;
	}


		
	static void permASR (int v[], int n , int m)
	{
		Random gen = new Random();
		int k = 0;
		int pos;
		for(int j=0; j<m;j++)
		{
			for(int z=0; z<n;z++)v[z] = z+1;	
			for(int i = 0; i<n-1;i++)
			{		
				pos = gen.nextInt(n-i) + i;
				swap(v,i,pos);
			}
			
			npermut++;
			k = inversions(v);
			total+=k;

			cases[k]++;
		}
	}
		

	static void perm (int v[],int i, int n) {

		/* this function generates the permutations of the array
		 * from element i to element n-1
		 */
		int j = 0;	
		int k = 0;
		
		if (i == n) {
					
				npermut++;
			
		  		k = inversions(v);
				total+=k;
				cases[k]++;
				
	    	
		} else

			for (j=i; j<n; j++) {


				swap (v, i, j);
				perm (v, i+1, n);
				swap (v, i, j);
			}
	}
		


	public void init()
	   {
	      prompt = new Label( "Enter n:" );
	      add( prompt );  // put prompt on applet 

	      input = new TextField( 2 );
	      input.setText(Integer.toString(n));
			add( input );   // put input TextField on applet
			
			muestreo = new JCheckBox("con muestreo");
			add(muestreo);
		  
		prompt2 = new Label( "Tamaņo de la muestra:" );
		  add( prompt2 );
		  input2 = new TextField( 3 );
	      input2.setText(Integer.toString(m));
			add( input2 );  
	      // "this" applet handles action events for TextField input
		  	
		  input2.addActionListener( this );
		  muestreo.addActionListener(this);
	      input.addActionListener( this );
	   }
	   

	   // process user's action in TextField input 
	   public void actionPerformed( ActionEvent e )
	   {
	      // get the number and convert it to an integer
		   
		  m = Integer.parseInt(input2.getText() );
	      n = Integer.parseInt(input.getText() );
	     	input.setText(Integer.toString(n));  
	     	input2.setText(Integer.toString(m));  
	     	repaint(); 
	     	if(muestreo.isSelected())
	     		{
	     		input2.setVisible(true);
	     		prompt2.setVisible(true);
	     		}
	     	else {input2.setVisible(false);
	     	prompt2.setVisible(false);
	     	}
	   }	
		
		public void paint(Graphics g) {
			
			double desviacion = 0;
			double promedio = 0;
					
			int k = 0;
		 	int v[] = new int[n];
			total = 0;
			npermut = 0;
			minCase=max;
			maxCase=0;	
			
			for(k=0; k<max+1; k++) {
				cases[k] = 0;
			}
			if(muestreo.isSelected())
	     	{	
	     		permASR(v,n,m);
	     	}else
	     	{
	     		for(int z=1;z<=v.length ;z++) v[z-1] = z;	
				perm(v,0,n);
	     	}
			
			
			
			
			for(k=0; k<max+1; k++){
						prob[k] = (double)cases[k]/  (double)npermut;
						if (( cases[k] != 0) && (minCase > k)) minCase = k;
						if (( cases[k] != 0) && (maxCase < k)) maxCase = k;			
			}
		
			
			int i = 0;
			g.setColor(Color.black);
			g.drawString("Probability",10,50);
			g.drawString("Steps",350,340);
			g.drawString("n = "+n,155,50);
			g.drawString("Number of permutations = "+ npermut,155,65);
			g.drawString("Average number of steps =  " + +((double) total)/((double)npermut) ,50,380);
			int y = 80;
			promedio =  ((double) total)/((double)npermut);
			for(i=minCase; i <= maxCase; i++) {
				if ( cases[i] != 0){
					y += 15;
					g.drawString("P("+i+")="+prob[i]+" ["+cases[i]+"]",300,y);
					desviacion = desviacion + (cases[i] - promedio)*(cases[i] - promedio);
				}
			}
			desviacion = desviacion/(double)total;
			y += 50;
			g.drawString("DESVIACION"+desviacion,300,y);

			g.setColor(Color.red);
			g.drawLine(50,50,50,320);
			g.drawLine(50,320,350,320);	
			
			g.setColor(Color.black);
			
			g.drawString("1.0", 10, 70);
			g.drawString("0.8", 10, 120);
			g.drawString("0.6", 10, 170);
			g.drawString("0.4", 10, 220);
			g.drawString("0.2", 10, 270);
			g.drawString("0.0", 10, 320);
			
			int yf;
			int shift = (int) (200.0/(double)(maxCase-minCase+1));
			int ishift = (int) (100.0/(double)(maxCase-minCase+1));
			g.setColor(Color.blue);
			for (i=minCase; i< (maxCase+1); i=i+1){
			  yf = (int) (prob[i] *250.0) ;
				g.fillRect(50+((i-minCase)*shift),320-yf, shift, yf);
				g.drawString(""+i,50+ishift+((i-minCase)*shift) , 330);
			
			}
			
			
		}	
		

		
		
	}