0

I need to build each combination of length L from an String Array/ArrayList, where L is greater than the Array length

I currently have a recursive method (not of my own creation) that will generate each combination of a String[], as long as the combinations are shorter than the Array.

example/psudoCode: 

input (2, {A,B,C}) 
returns {AA, AB, AC, BA, BC, CB, CA}

As of now, if the requested combination length (2 in the example) is greater than the Array length (4,5,6... instead of 2), the recursive method shoots out that sweet sweet ArrayIndexOutOfBounds error.


What I need is a method (recursive or not) that will return every combination of the array, regardless of whether the combinations are longer than the Array itself. Would this be done better by adding more letters to the Array and crossing my fingers or is there a legitimate way to accomplish this? Thank you!

Here is the method I have been using. If u know where the credit lies please say so, this is not of my own creation.

public class bizzBam
{
    // Driver method to test below methods
    public static void main(String[] args) {
        System.out.println("First Test");
        String set1[] = {"a", "b","c"};
        printAllKLength(set1, pointX);
    }

    // The method that prints all possible strings of length k.  It is
    //  mainly a wrapper over recursive function printAllKLengthRec()
    static void printAllKLength(String set[], int k) {
        int n = set.length+2;
        printAllKLengthRec(set, "", n, k);
    }

    // The main recursive method to print all possible strings of length k
    static void printAllKLengthRec(String set[], String prefix, int n, int length) {

        // Base case: k is 0, print prefix
        if (length == 0) {
            System.out.println(prefix);
            return;
        }

        // One by one add all characters from set and recursively
        // call for k equals to k-1
        for (int i = 0; i < n; ++i) {

            // Next character of input added
            String newPrefix = prefix + set[i];

            // k is decreased, because we have added a new character
            printAllKLengthRec(set, newPrefix, n, length - 1);
        }
    }
}

(Edit forgot to say:) For this algorithim at least, if "PointX" is greater than the input array's length, it will return the indexoutofbounds.

I. Glenius A.
  • 1
  • 1
  • No wonder it doesn't work. What's `pointX`? – Tavo Aug 02 '17 at 02:26
  • 1
    pointX is the length of the combinations you want to generate, yes? If so, change `int n = set.length+2;` to `int n = set.length;` and you should be good setting pointX to values > 3 – RaffleBuffle Aug 02 '17 at 02:28
  • Its already answered, better to consider it for further logics https://stackoverflow.com/questions/4240080/generating-all-permutations-of-a-given-string – Tehmina Aug 02 '17 at 02:37
  • Your example seems inconsistent. Why is AA in the output, but not BB or CC? – Gene Aug 02 '17 at 04:35
  • @Tavo Sorry, forgot to explain that, post edited – I. Glenius A. Aug 02 '17 at 17:53

3 Answers3

3

Strictly speaking these are permutations rather than combinations. You're generating all permutations of k elements selected from a set of n candidates, with replacement (or repitition). There will be n^k such permutations.

Here's a non-recursive solution.

public class Permutations
{
    public static void main(String[] args)
    {
        permutationsKN(new String[]{"a",  "b",  "c"}, 4);
    }

    static void permutationsKN(String[] arr, int k)
    {
        int n = arr.length;

        int[] idx = new int[k];
        String[] perm = new String[k];

        while (true)
        {
            for(int i=0; i<k; i++) perm[i] = arr[idx[i]];           
            System.out.println(String.join("", perm));

            // generate the next permutation
            int i = idx.length - 1;
            for (; i >= 0; i--)
            {
                idx[i]++;
                if (idx[i] < n) break;                  
                idx[i] = 0;
            }

            // if the first index wrapped around then we're done
            if (i < 0) break;               
        }
    }
}
RaffleBuffle
  • 5,396
  • 1
  • 9
  • 16
1

You have two problems here:

int n = set.length+2; -> This is giving you your "sweet sweet" IndexArrayOutOfBoundsException. Change it to set.length-1. I am not sure why you decided to randomnly put +2 there.

for (int i = 0; i < n; ++i) -> You will be looping from 0 to n. You need to loop from 0 to n-1.

Edit: Or as @SirRaffleBuffle suggested, just do set.length. Total credits to him

Tavo
  • 3,087
  • 5
  • 29
  • 44
0

Assuming your example is missing "BB" and "CC" because it includes "AA", it looks like what you want is just like the odometer of a car except that instead of ten digits, you want a choice of letters. It's not hard to model an odometer:

class Odo {
  private final char [] chars;
  private final int [] positions;
  private boolean hasNext;

  Oddo(String chars, int nPositions) {
    this.chars = chars.toCharArray();
    this.positions = new int [nPositions];
    this.hasNext = true;
  }

  boolean hasNext() {
    return hasNext;
  }

  String emitNext() {
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < positions.length; ++i) sb.append(chars[positions[i]]);
    for (int i = 0; i < positions.length; ++i) {
      if (++positions[i] < chars.length) {
        hasNext = true;
        return sb.toString();
      }
      positions[i] = 0;
    }
    hasNext = false;
    return sb.toString();
  }
}

Calling like so:

Odo odo = new Odo("AB", 3);
while (odo.hasNext()) {
  System.out.println(odo.emitNext());
}

Produces

AAA
BAA
ABA
BBA
AAB
BAB
ABB
BBB
Gene
  • 46,253
  • 4
  • 58
  • 96