//Combinations.java
// n choose r
// all n-bit patterns with r 1's

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


public class Combinations extends JApplet {

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

    TreeSet combosSet;
    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();

	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 );

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


	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( "" );
	    inputCNRField.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 > 31 ) {
		errorLabel.setText( "up to 31 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( "0 <= R <= N" );
                return;
            }


	    /*  //inefficient: 2^N powerset, select r-sized subsets:          
            int two_n = 1 << n;
	    char A[]="abcdefghijklmnopqrstuvwxyzABCDEF".toCharArray();    //32 chars
 
	    combosSet.clear();
            //generate in binary number order
            for (int i=0; i<=two_n-1; i++) {
                String subset = "";
		
                for (int j=0; j<n; j++)
                    if (((i>>j) & 1) == 1)
                        subset += "" + A[j];     
		
		if ( subset.length() == r )
		    combosSet.add( subset );
	    }
	    */	    



	    combosSet.clear();

            BitSet bits = new BitSet( n );
	    comboBits( bits, n, r );

	    Iterator it = combosSet.iterator();
	    while ( it.hasNext() )
		listArea.append( (String)it.next() + "\n" );

	    inputCNRField.setText( "" + combosSet.size() );	    
	}
    }
    

    
    int comboBits ( BitSet bits, int n, int r ) {
	

	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 copyBitsR = (BitSet)bits.clone();
	    BitSet copyBitsR1 = (BitSet)bits.clone();
	    copyBitsR1.set( n-1 );    //Nth position is used by a 1
	    //return comboBits( copyBitsR1, n-1, r-1) + comboBits( copyBitsR, n-1, r );
	    return comboBits( copyBitsR1, n-1, r-1) + comboBits( bits, n-1, r );
	}
    }


    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;
    }
    */
}