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.

Answer 2

If you want it in Python, you don't need to know how to program!

import itertools
for p in itertools.permutations('abc123', 4):
    print ''.join(p)

Answer 3

Recursive solutions seems pretty straightforward too:

public class TestCombinations {

public static void main(String[] args) {
    String[] elements = {"a", "b", "c", "1", "2", "3"};
    int maxLength = 4;
    combineStringFromElements(elements, "", maxLength);
}

private static void combineStringFromElements(String[] elements, String currentString, int maxLength) {
    if (currentString.length() == maxLength) {
        System.out.println(currentString);
        return;
    }
    for (String element : elements) {
        combineStringFromElements(elements, currentString + element, maxLength);
    }
}

}

The code is neither clean or efficient, just to demonstrate the logic.

Answer 4

You can treat your elements as digits. Think about how we get every possible combination of "0" - "9" by counting. Start with 0000, 0001, 0002, ..., 0010, 0011, etc. Use the same process, as though you had a base-6 number system (or base-n, where n is the length of your elements array.

aaaa, aaab, aaac, ...,
aaba, aabb, aabc, aab1, aab2, aab3, .....,
aa32, aa33, abaa, etc.

Alternate through every combination in the last digit, then advance the previous digit and repeat. When the second-to-last digit has gone through every element, then advance the third-to-last digit, and so forth. When you have reached "3333" you are finished.

Your code would be something like this:

string comb;
for (int i = 0; i < elements.length; i++)
    for (int j = 0; j < elements.length; j++)
        for (int k = 0; k < elements.length; k++)
            for (int m = 0; m < elements.length; m++) {
                comb = elements[i] + elements[j] + elements[k] + elements[m];
                // do something with the combination
            }

There are other ways to accomplish the same thing that are more efficient, like storing intermediate 1, 2, 3-character strings. There are also recursive solutions. But that is the general idea, and should be fast enough for the data size you are using now (you have a total of 6^4 = 1296 combinations.

Answer 5

Here is some python code that does what you want:

answer = []
def permute(chars, s=''):
    if len(s) == 4:
        answer.append(s)
    else:
        for char in chars:
            permute(chars, s+char)

Hope this helps

This type of algorithm is called recursive descent, in case you hadn't checked that already.