Getting every possible permutation of a string or combination including repeated characters in Java

Question

I have been trying to generate a list of every possible 4 character string which could be made up of any given set of characters. I have used a function to generate every 4 character combination from a set of characters but each character is only ever used once. I need every possible combination using a given set of chars for example:

String[] elements = {"a", "b", "c", "1", "2", "3"};
int[] indices;
CombinationGenerator x = new CombinationGenerator (elements.length, 4);
StringBuffer combination;
while (x.hasMore ()) {
  combination = new StringBuffer ();
  indices = x.getNext ();
  for (int i = 0; i < indices.length; i++) {
      combination.append (elements[indices[i]]);
  }
  System.out.println (combination.toString ());
}

Using the CombinationGenerator class from here, this will return every unique 4 character combination such as:

'abcd' , 'abc1', 'acb2', 'acb1'

But, I want every possible string that could be created using the given characters. For example:

'aaaa', 'aaab', 'abc1', 'aac1', '11c2'

I have tried every recursive and permutation method I've been able to find or come up with but I'm stumped on getting any further than generating all the combinations like above, then generating every permutation of each combination, but I can't work out how to create a set of combinations using repeated characters.

Any help, or even just the theory on how it could be done would be helpful.

Answer 1

You're going to have to be more specific on exactly WHAT you want your function to get. There are many different definitions of "combinations" and you haven't specified whether you want ordered or unordered combinations.

Mathematically, if you have n elements and want a LIST of k of them (ordered with repeats), that gives you

n ^ k

combinations. (6 ^ 4 = 1296 combinations in your original example, which is a lot!). However, if you have n elements and want a MULTISET of k of them (unordered with repeats), that gives you

(n + k - 1)! / (k! * (n - 1)!)

combinations and is a much harder enumeration.

If k is small, you can generate the first one with a limited number of for loops but this becomes cumbersome very quickly as k grows. This strongly hints at the need for a RECURSIVE method:

public static String[] getAllLists(String[] elements, int lengthOfList)
{
    //initialize our returned list with the number of elements calculated above
    String[] allLists = new String[(int)Math.pow(elements.length, lengthOfList)];

    //lists of length 1 are just the original elements
    if(lengthOfList == 1) return elements; 
    else
    {
        //the recursion--get all lists of length 3, length 2, all the way up to 1
        String[] allSublists = getAllLists(elements, lengthOfList - 1);

        //append the sublists to each element
        int arrayIndex = 0;

        for(int i = 0; i < elements.length; i++)
        {
            for(int j = 0; j < allSublists.length; j++)
            {
                //add the newly appended combination to the list
                allLists[arrayIndex] = elements[i] + allSublists[j];
                arrayIndex++;
            }
        }

        return allLists;
    }
}

Not only will this method generate all the lists, but it will enumerate them in order. That is, the output will be

aaaa
aaab
aaac
aaa1
aaa2
aaa3
aaba
aabb
aabc
aab1
...
3323
333a
333b
333c
3331
3332
3333

using your original input. It can also generate any length of words (be very careful with this! Just with words of length 8 I wound up with 1,679,616 combinations!).

If the method confuses you (it's a recursive method, so it's a bit hard to follow) or if you want a solution to the second combination problem, feel free to ask. Also, this method is somewhat inefficient because it recalculates the combinations for all the sublists, so it's not viable for really long lists. If you really wanted efficiency you would store the already-calculated tuples in a global list.