import java.applet.Applet;
import java.awt.*;    
import java.awt.event.*;  
import java.util.Random;
import javax.swing.*;


public class RandomAlgo extends Applet {
	
	static int total;
	static double promedio;
	int minFrec=100;
	int maxFrec=0;
	static int steps;
	static int n=5;
	static double frecuencia[] = new double[100000];
	static int Runs = 5000;
	static Random random = new Random();

	Button ejecutar;
	Label labelN,labelR;
	Panel panel;
	TextField ene,ere;   
	TextArea textarea=new TextArea();
	JCheckBox  NalCubo, swaps, rifSh;
	
	Font font1,font2;
	String outputText,outputText1;
	
public void AlgNcubo(int v[]) {
		
		int k = 0;
		
		for (int b = 1; b < Runs; b++) {
			
			int[] p = new int[v.length];

			Random r = new Random();

			for (int c = 0; c < v.length; c++)
				p[c] = r.nextInt((int)Math.pow(n,3));
			for(int i=0; i < v.length; i++ )
        	{
           	 for(int j = v.length-1; j >= i+1; j--)
           	 	{
                	if(p[j] < p[j-1])
                	{
                 	   swap(v,j,j-1);
                	}
            	}
        	}
			

			
			k = factoradic(v);
			total += k;
			frecuencia[k]++;
		}
	}

public static int factorial(int n)
{
    int res = 1;
    for(int i = n; i > 0; i--)
        res *= i;

    return res;
}

public int factoradic(int v[]) {
	int n=0;
	int[] a = new int[v.length];
	
	for(int i=0; i<a.length;i++)
	{
		a[i]=v[i];
	}
	
	for(int i=0; i<a.length;i++)
	{
		a[i]++;
	}
	
	for(int i=0; i<a.length;i++)
	{
		for(int j=i+1; j<a.length; j++)
		{
			if(a[j]>=a[i])
				a[j]--;
		}
	}
	
	for(int i=0; i<a.length;i++)
	{
		a[i]--;
	}
	
	a[a.length-1] = 0;
	
	for(int i=0; i<a.length;i++)
	{
		n+=a[i]*factorial(a.length-i-1);
	}
	
	return n;
	
}

public void riffleShuffle(int[] v)
{
	int k;
    int permutaciones[] = new int[n];
    Random generador = new Random();
    int cuts = (int)(Math.log(n) / Math.log(2D)) + 1;
	
	for (int b = 1; b < Runs; b++) {
    for(int i = 0; i < cuts; i++)
    {
        int cutpoint = generador.nextInt(n);
        int temp[] = new int[n];
        int j = 0;
        int encima = n - cutpoint;
        int debajo = cutpoint;
        System.out.println("");
        int tope = 0;
        if(encima > debajo)
            tope = encima;
        else
            tope = debajo;
        int unterOderAuf = generador.nextInt(2);
        if(unterOderAuf == 0)
        {
            for(int e = 0; e < tope; e++)
            {
                if(e < debajo)
                {
                    temp[j] = v[e];
                    j++;
                }
                if(e < encima)
                {
                    temp[j] = v[cutpoint + e];
                    j++;
                }
            }

        } else
        {
            for(int e = 0; e < tope; e++)
            {
                if(e < encima)
                {
                    temp[j] = v[cutpoint + e];
                    j++;
                }
                if(e < debajo)
                {
                    temp[j] = v[e];
                    j++;
                }
            }

        }
        for(int e = 0; e < n; e++)            
            v[e] = temp[e];
    
		k = factoradic(v);
		total += k;
		frecuencia[k]++;
            

    }
    }
}

public void SwapsRand(int v[]) {

	int k = 0;

	for (int j = 1; j < Runs; j++) {

		Random r = new Random();

		for (int c = n - 1; c > 0; --c)
			swap(v, r.nextInt(n), c);

		
		k = factoradic(v);
		total += k;
		frecuencia[k]++;
	}

}
public static void swap(int[] v, int i, int j) {

	int t = v[i];
	v[i] = v[j];
	v[j] = t;
}


    

public void init()
   {
	 setLayout(null);
	 resize(650,450);
	 font1 = new Font ( "Arial",Font.BOLD,14);
	 font2 = new Font ( "TimesRoman",Font.BOLD,12);
	 
	
	 labelN = new Label( "n:" );			    
     add( labelN );  
     ene = new TextField( 2 );
     ene.setText(Integer.toString(n)); 
	 add(ene);
	
	
     labelR = new Label( "r:" );
     add( labelR ); 
     ere = new TextField( 5 );
     ere.setText(Integer.toString(Runs));
     add( ere );   
     
     ejecutar =new Button("Ejecutar");
     this.add(ejecutar);
     add(textarea);
     
     panel=new Panel();
     panel.setBackground(new Color(210, 150,225));
     Label Swap=new Label("Swap      ");
     Label N3=new Label("Alg. n^3  ");
     Label Riffle=new Label( "R. shuffle");
     NalCubo =new JCheckBox();
     NalCubo.setSelected(true);
     swaps =new JCheckBox();
     swaps.setSelected(false);
     rifSh =new JCheckBox();
     rifSh.setSelected(false);
     panel.add(N3);
     panel.add(NalCubo);
     panel.add(Swap);
     panel.add(swaps);
     panel.add(Riffle);
     panel.add(rifSh);
     this.add(panel);
 
   
   NalCubo.addItemListener(new ItemListener() {
    	    public void itemStateChanged(ItemEvent e) {
    	    	swaps.setSelected(false);
    	    	rifSh.setSelected(false);
    	    }
    	});

     swaps.addItemListener(new ItemListener() {
 	    public void itemStateChanged(ItemEvent e) {
 	    	NalCubo.setSelected(false);
 	    	rifSh.setSelected(false);
 	    }
 	});	 
     
     rifSh.addItemListener(new ItemListener() {
 	    public void itemStateChanged(ItemEvent e) {
 	    	swaps.setSelected(false);
 	    	NalCubo.setSelected(false);
 	    }
 	});
     panel.reshape(510, 10, 125,85);
     textarea.reshape(510,100,125,325);
     labelN.reshape(50,10,20,20);
     ene.reshape(75,10,30,20);
     labelR.reshape(150,10,20,20);
     ere.reshape(175,10,60,20);
     ejecutar.reshape(300,10,125,20);

     ejecutar.addActionListener(new java.awt.event.ActionListener() {
         public void actionPerformed(ActionEvent e) {    
         	btnSol_actionPerformed(e);
         	 }

		private void btnSol_actionPerformed(ActionEvent e) {
			n = Integer.parseInt( ene.getText() );
	     	ene.setText(Integer.toString(n));  
				     	repaint(); 
								
	      Runs = Integer.parseInt( ere.getText() );
	     	ere.setText(Integer.toString(Runs));  
				     	repaint();	
		}
     });

   }


	public void paint(Graphics g) {
		
		int k,r;
		total = 0;
		minFrec=50;
		maxFrec=0;
		double c[] = new double [5];
		int v[] = new int[n];
		g.setColor(new Color(224, 224,225));
	    g.fillRoundRect(5,35,480,330,10,20);
	    
		setBackground(Color.white);	
		labelR.setBackground(Color.white);
	
		outputText =  "NÚMERO DE PERMUTACIONES =  "+ Runs;
		for (k = 0; k < n; k++) {
			v[k] = k;
		}
		for(k=0; k<1000; k++) frecuencia[k] = 0;
		if(NalCubo.isSelected()== true)AlgNcubo(v);
		if(swaps.isSelected()== true)SwapsRand(v);
		if(rifSh.isSelected()== true)riffleShuffle(v);
		textarea.setText(" ");		
		for(k = 0; k < 1000; k++){
			frecuencia[k] /= (double)Runs;
			if (( frecuencia[k] > 0.0) && (minFrec > k)){
				minFrec = k;
				c[4] = frecuencia[k];
			}
			if (( frecuencia[k] > 0.0) && (maxFrec < k)) maxFrec = k;
			if (( frecuencia[k] >0.0) && (k<999) && c[4]<frecuencia[k]) c[4] = frecuencia[k];
		}
		int i = 0;
		outputText1= "PROMEDIO=    " + +((double) total)/((double)Runs); 	
		for(i=minFrec; i <= maxFrec; i++) {
			textarea.appendText("P("+i+")="+frecuencia[i]+"\n");		
		}
		

		g.setColor(Color.black);
		g.drawLine(50,50,50,320);
		g.drawLine(50,320,480,320);	
		g.setColor(Color.black);
		
		for (k=0; k<5; k++){
			c[k]=c[4]*0.2*(k+1);
			c[k]=(double)(Math.floor(c[k]*1000))/1000;
			g.drawString(""+(double)c[k], 10, 270-(k*50));
			
		}
		g.drawString("0.0", 10, 320);
		
		
		int yf;
		int shift = (int) (450.0/(double)(maxFrec-minFrec+1));
		int ishift = (int) (100.0/(double)(maxFrec-minFrec+1));
		
		for (i=minFrec; i< (maxFrec+1); i=i+1){
		  yf = (int) (frecuencia[i]*(250.0/c[4])) ;
		  
		  g.setColor(new Color(aleatorio(256),aleatorio(256) ,aleatorio(256)));
		  g.fillRect(50+((i-minFrec)*shift),320-yf, shift, yf);
		  
		  g.setColor(Color.black);
		  g.drawString(""+i,50+ishift+((i-minFrec)*shift) , 330);
			}
		
		g.setFont(font2);
		g.setColor(Color.MAGENTA);
		g.drawString("Prob.",10,50);
		g.drawString("Steps",450,340);
		g.drawString("HISTOGRAMA DEL Nº COMPARACIONES", 150, 50);
		g.setColor(Color.BLUE);
		g.setFont(font1);
		g.drawString(outputText1,50,420);
		g.drawString(outputText,50,400);
	}		
	
	
	public int aleatorio (int rango){ return (( int ) (Math.random()*rango));}
	
	
}