String Letter Combinations Using "N choose K" using Java

Question

So I have run into a problem where I have an ArrayList where the List is comprised of one letter strings. In this case (A,B,C,D,F,J,N) where the size of the list is 7.

Now I am trying to write code making all combinations of lettering that can be made where the order does not matter i.e. (I know it will be involving "n choose k") up to 5 letters long.

So for 7 choose 1 will be A,B,C,D,F,J,N ... 7 choose 2 ... etc. ... 7 choose 3 ... etc. ... etc.

I am then looking to store these string combinations into another list/hashmap (haven't decided on yet).

But my main focus is on the code that would generate such strings. If anyone can help that would be greatly appreciated. I also want to make it modular just in case i want to eventually form other combinations of 6,7 length. (Which is why I am not just doing it with 5 loops and incrementing for different indices).

What I have so far...

public class ReadFile {

    public static void main(String[] args) throws IOException {

        String file_name = "C:/Users/Shane/Documents/College/Classes/PurchaseTable.txt";

        extract(file_name, 50);


    }

        private String path;

        public ReadFile(String file_path) {
            path= file_path;
        }

        public String[] OpenFile() throws IOException {
            FileReader fr = new FileReader(path);
            BufferedReader textReader = new BufferedReader(fr);

            int numberOfLines = readLines();
            String[] textData = new String[numberOfLines];

            int i;

            for(i=0; i < numberOfLines; i++) {
                textData[i] = textReader.readLine();
            }

            textReader.close();
            return textData;
        }

        int readLines() throws IOException {

            FileReader file_to_read = new FileReader(path);
            BufferedReader bf = new BufferedReader(file_to_read);

            String aLine;
            int numberOfLines = 0;

            while(( aLine = bf.readLine()) != null) {
                numberOfLines++;
            }
            bf.close();

            return numberOfLines;
        }

    public static void extract(String filename, int threshold) {

        String file_name = filename;
        ArrayList<String> temp = new ArrayList<String>();
        ArrayList<String> products = new ArrayList<String>();
        HashMap<Integer, String> productsPerDate = new HashMap<Integer, String>();
        //HashMap<Integer, String> allCombinations = new HashMap<Integer, String>();

        try {
            ReadFile file = new ReadFile(file_name);
            String[] aryLines = file.OpenFile();
            int i;
            for (i=1; i < aryLines.length; i++) { //excludes header section of any table as shown in assignment
                temp.add(aryLines[i]);              
            }
        }
        catch (IOException e) {
            System.out.println( e.getMessage() );
        }

        System.out.println(temp);
        System.out.println(temp.get(0));
        System.out.println(temp.size());

        int i; int j; int l;
        for (i=0; i<temp.size(); i++) {
            String str = temp.get(i);
            StringBuilder sb = new StringBuilder(str);
            int k =0;
            for (j=0; j<=sb.length(); j++) {
                if(sb.charAt(j) == '\"' && k==0) {
                    sb.delete(0, j+1);
                    k++;
                }
                if(sb.charAt(j) == '\"' && k!=0) {
                    sb.delete(j, sb.length());
                    String line = null;
                    System.out.println(sb);
                    for( l=0; l<sb.length(); l++) {
                         String string = Character.toString(sb.charAt(l));
                         if(string.equals(",")) {

                         }
                         else if (l ==0) {
                             products.add(string);
                             line = string;
                         }
                         else {
                             products.add(string);
                             line = line + string;
                         }
                    }
                    productsPerDate.put(i, line);
                    //System.out.println(products);
                    break;
                }
            }
        }

        System.out.println(products);
        System.out.println(productsPerDate.entrySet()); //Hashmap set to string of 1 letter characters for products per date

        Set<String> removeDup = new HashSet<>();
        removeDup.addAll(products);
        products.clear();
        products.addAll(removeDup);

        System.out.println(products);

        int maxLength = productsPerDate.get(0).length();
        for(int m = 0; m < productsPerDate.size(); m++) { //determine max length of string in hashmap
            if(maxLength < productsPerDate.get(m).length()) {
                maxLength = productsPerDate.get(m).length();
            }
        }

This probably isn't the most efficient way to do this but please bear with me and help in any way you can.

The output is shown below of what has been created in the above code:

1,"A,B,C,N",1/3/2013
4
A,B,C,N
B,C,D,A,F
A,C,V,N,J
A,C,J,D
[A, B, C, N, B, C, D, A, F, A, C, V, N, J, A, C, J, D]
[0=ABCN, 1=BCDAF, 2=ACVNJ, 3=ACJD]
[A, B, C, D, F, V, J, N]

So essentially I am trying to write the code to make all the possible combinations of length 5 string using the letter strings contained in the array list shown in last output.

Answer 1

Brute force, without recursion, with generics, not optimized, didactic.

If you want arrangements rather than combinaisons, just comment one line.

// COMBINAISONS
/**
 * Return combinaisons of input
 * @param _input 
 * @param _n how many to pick
 * @return
 */
public static <T> Vector<Vector<T>> combinaisons (Vector<T> _input, int _n)
{
Vector<Vector<T>> output=new Vector<Vector<T>> ();

int size=_input.size();

// Current result
Object current[]=new Object[_n];
Arrays.fill(current,"");

// which element we take at each box  (between 0 and size-1)
int current_indices[]=new int[_n];
Arrays.fill(current_indices,-1);

// inputs used
boolean used[]=new boolean [size];
Arrays.fill(used, false);

// Which box are we processing
int current_box=0;

// Next value for next position
int next_pos_value=0;

// ALGORITHM

while (true)
{
// Finished ?
if (current_box<0)
    break;

// Last element ? 
if (current_box>=_n)
    {
    // => save group
    output.add(new Vector<T>((List<T>) Arrays.asList(current)));

    current_box--;
    continue;
    }

// filling Current box > 0 && < _n

// next value available
int last_value=current_indices[current_box];
int next_value=-1;

// Where do we begin
int begin_test=0;
if (last_value>=0)
    begin_test=last_value+1;

// bigger
// comment this for arrangement rather than combinaisons
if (begin_test<next_pos_value) begin_test=next_pos_value;

for (int test_value=begin_test; test_value < size; test_value++)
        if (!used[test_value])
            {
            next_value=test_value;
            break;
            }

// VALUE AVAILABLE
if (next_value!=-1)
    // valid value ?
    {
    // release
    if (last_value!=-1)
        used[last_value]=false;

        used[next_value]=true;
        current_indices[current_box]=next_value;
        current[current_box]=_input.get(next_value);

        // next position
        current_box++;

        // like arrangements, but next value always more
        next_pos_value=next_value+1;

        continue;
    }       

else
    // invalid value (too big) ?
    {
    // release
    if (last_value!=-1)
    used[last_value]=false;
    current_indices[current_box]=-1;

    // back position
    current_box--;

    // like arrangements, but reset this
    next_pos_value=-1;

    continue;
    }       
}

return output;
}
//  public static Vector<Vector<T>> combinaisons (Vector<T> _input)

Answer 2

Here is a little method that returns a list of all letter combinations of length k (order doesn't matter), given an input String of length n:

public static ArrayList<String> combinations(String nChars, int k) {
    int n = nChars.length();
    ArrayList<String> combos = new ArrayList<String>();
    if (k == 0) {
        combos.add("");
        return combos;
    }
    if (n < k || n == 0)
        return combos;
    String last = nChars.substring(n-1);
    combos.addAll(combinations(nChars.substring(0, n-1), k));
    for (String subCombo : combinations(nChars.substring(0, n-1), k-1)) 
        combos.add(subCombo + last);

    return combos;
}

public static void main(String[] args) {
    String nChars = "ABCDE";
    System.out.println(combinations(nChars, 2));
}

output: [AB, AC, BC, AD, BD, CD, AE, BE, CE, DE]

I used Strings as input and output, since they are immutable and more well-behaved with regard to slicing than Lists. But if your List contains only 1-letter Strings, it should be easy to convert.

I don't know if this recursive implementation is performant, but it reflects nicely the mathematical property of the Pascal triangle: (n choose k) = (n-1 choose k-1) + (n-1 choose k)