//RPermutations.java
// each n choose r combination then all permutations of it
// combos: using all n-bit patterns with r 1's

import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import java.util.*;


public class RPermutations extends JApplet {

    JTextField inputNField;
    JTextField inputRField;
    JTextField outputRPermsField;
    JTextArea listArea;
    JLabel errorLabel;

    TreeSet combosSet;
    java.util.List  permsList;
    char A[]="abcdefghijklmnopqrstuvwxyzABCDEF".toCharArray();    //32 chars


    public void init() {
	Container container = getContentPane();
	int panelRowsSize = 2;
	container.setLayout( new GridLayout( 1, panelRowsSize) );

	JPanel [] panelRows = new JPanel[panelRowsSize];

	//left side panel
	panelRows[0] = new JPanel();
	container.add( panelRows[0] );
	panelRows[0].setLayout( new FlowLayout() );

	//right side panel
	panelRows[1] = new JPanel();
	panelRows[1].setLayout( new FlowLayout() );
	container.add( panelRows[1] );

	combosSet = new TreeSet();
	permsList = new ArrayList();

	Font bigFont = new Font( "Monospaced", Font.BOLD, 16 );
	TextFieldHandler handleTextField = new TextFieldHandler();

	JLabel inputNLabel = new JLabel( "N" );
	inputNLabel.setFont( bigFont );
	panelRows[0].add( inputNLabel );

	inputNField = new JTextField( 3 );
	inputNField.setFont( bigFont );
	panelRows[0].add( inputNField );
	inputNField.addActionListener( handleTextField );

	JLabel inputRLabel = new JLabel( "R" );
	inputRLabel.setFont( bigFont );
	panelRows[0].add( inputRLabel );

	inputRField = new JTextField( 3 );
	inputRField.setFont( bigFont );
	panelRows[0].add( inputRField );
	inputRField.addActionListener( handleTextField );

	outputRPermsField = new JTextField( 6 );
	outputRPermsField.setFont( bigFont );
	outputRPermsField.setEditable( false );
	panelRows[0].add( outputRPermsField );


	errorLabel = new JLabel( "" );
	panelRows[0].add( errorLabel );


	listArea = new JTextArea( 16, 30 );
        Font smallFont = new Font( "Monospaced", Font.BOLD, 12 );
        listArea.setFont( smallFont );
        JScrollPane listScroll = new JScrollPane( listArea );
        panelRows[1].add( listScroll );
                                                                           
    }


    public void start() {
	inputNField.requestFocusInWindow();
    }


    private class TextFieldHandler implements ActionListener {
        public void actionPerformed( ActionEvent event ) {

	    listArea.setText( "" );		    
	    errorLabel.setText( "" );
	    outputRPermsField.setText( "" );	    

            int n=0;
            try {
                n = Integer.parseInt( inputNField.getText() );
            }
            catch (NumberFormatException e) {
                errorLabel.setText( "integer please" );
                return;
            }
            if ( n <= 0 ) {
                errorLabel.setText( "positive integer please" );
                return;
            }
	    if ( n > 14 ) {
		errorLabel.setText( "up to 14 chars only" );
		return;
	    }
                                                          
	    int r=0;
            try {
                r = Integer.parseInt( inputRField.getText() );
            }
            catch (NumberFormatException e) {
                errorLabel.setText( "integer please" );
                return;
            }
            if ( r <= 0 ) {
                errorLabel.setText( "positive integer please" );
                return;
            }
	    if ( r > n ) {
                errorLabel.setText( "1 <= R <= N" );
                return;
            }





	    combosSet.clear();

            BitSet bits = new BitSet( n );  //n bits, all false
	    //all n-bit patterns with r 1's.  add to Set
	    comboBits( bits, n, r, combosSet );  //all N choose r combos

	    
	    int numPerms = 0;
	    Iterator it = combosSet.iterator();
	    //for each combo
	    while ( it.hasNext() ) {
		//StringBuffer L= new StringBuffer(" abcdefghijklmn");  //14 chars
		StringBuffer L= new StringBuffer( " " + (String)it.next() + " ");   
		//needs leading and trailing blank...

		permsList.clear();
		
		perms ( L, 1, r, permsList );   //r not n!! bug
		
		numPerms += permsList.size();
		
		Iterator it2 = permsList.iterator();
		while ( it2.hasNext() )
		    listArea.append( (String)it2.next() + "\n" );
		
	    }
	    
	    outputRPermsField.setText( "" + numPerms );
		
	}
    }
    

    //generate all n-bit BitSets with exactly r 1's
    //add to Set
    int comboBits ( BitSet bits, int n, int r, Set combosSet ) {
	

	if (r == 1) {
	    for (int i=n-1; i>=0; i--) {  //each bit from n-1 downto 0
		bits.set( i );         //turn it on
		//System.out.println( "1: " + bits.toString() + toInt( bits ) );
		combosSet.add( toAString( bits ) );
		bits.set( i, false );  //turn it off
	    }

	    return n;
	}
	else if (r == n) {
	    for (int i=n-1; i>=0; i--)  //fill in all r=n bits downto 0
		bits.set( i );

	    //System.out.println( "N: " + bits.toString()  + toInt( bits ) );
	    
	    combosSet.add( toAString( bits ) );
	    return 1;
	}
	else {
	    BitSet copyBitsR1 = (BitSet)bits.clone();
	    copyBitsR1.set( n-1 );    //Nth position is used by a 1

	    return comboBits( copyBitsR1, n-1, r-1, combosSet ) + 
		comboBits( bits, n-1, r, combosSet );
	}
    }


    String toAString ( BitSet bits ) {
	String combo="";

	for (int i=0; i<bits.size(); i++)
	    if( bits.get( i ) )
		combo += A[i];

	return combo;
    }

    /*
    int toInt ( BitSet bits ) {
	int num = 0;
	for (int i=0; i<bits.size(); i++)
	    num += bits.get( i ) ? (1<<i) : 0;
	return num;
    }
    */



    //permutations from k to N
    void perms ( StringBuffer L, int k, int n, java.util.List permsList ) {
    //void perms ( StringBuffer L, int k, int n ) {
 
        char temp;
 
        if (k == n)    //N to N
            permsList.add( L.substring( 1, n+1 ) );
 
        else
            for (int i=k; i<=n; i++) {  //for each I from k to N
                temp = L.charAt(i);        //swap with Kth
                L.setCharAt( i, L.charAt(k) );
                L.setCharAt( k, temp );
                //recurse to find permutations from K+1 to N in copy of String
                perms( new StringBuffer( L.toString() ), k+1, n, permsList );
                //perms( new StringBuffer( L.toString() ), k+1, n );
            }
    }
                                                                                            
}