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.

Improve this question
5
  • No wonder it doesn't work. What's pointX? Commented Aug 2, 2017 at 2: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 Commented Aug 2, 2017 at 2:28
  • Its already answered, better to consider it for further logics stackoverflow.com/questions/4240080/… Commented Aug 2, 2017 at 2:37
  • Your example seems inconsistent. Why is AA in the output, but not BB or CC? Commented Aug 2, 2017 at 4:35
  • @Tavo Sorry, forgot to explain that, post edited Commented Aug 2, 2017 at 17:53

3 Answers 3

Reset to default
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;               
        }
    }
}
Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

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

Improve this answer

2 Comments

It should be just int n = set.length;
@SirRaffleBuffle You didn't even give me time to edit it :D
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
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.