3

I don't know why I can't work this one in my head.

I have an array of characters in my Java code..

private String[] letters = { "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z",
    "0", "1", "2", "3", "4", "5", "6", "7", "8", "9"
};

What I need to do is loop through building strings for every possible configuration.

Example:

a aa ab ac . . . aaa aab aac . . . . aba abc

and so on up to n length.

Can any one point me in the direction with this problem.

Cheers

2
  • @paislee If a finite number n is given for the maximum length then there is not an infinite number of possibilities.
    – Jesper
    Feb 10, 2012 at 19:31
  • This post has an implementation of superset generation in Java. Feb 10, 2012 at 19:38

4 Answers 4

2

Yet another recursive approach. I'm working in the other direction from @liwp. There's a slight advantage that I only allocate one output ArrayList. Also, for simplicity, I just put in the numbers 0...9 in this example

static public void combos(String[] inputs, List<String> outputs, String preface, int maxDepth) {
        if (preface.length() >= maxDepth)
           return;
        for (String s : inputs) {
           // swap the order of these two lines if you want depth first
           outputs.add(preface+s);
           combos(inputs, outputs, preface+s, maxDepth);
        }       
     }


     public static void main(String[] args) {
        String[] numbers = {"0", "1", "2", "3", "4", "5", "6", "7", "8", "9"};
        ArrayList<String> outputs = new ArrayList<String>();
        combos(numbers, outputs, "", 3);
        System.out.println(outputs);

     }

will print out

[0, 00, 000, 001, 002, 003, 004, 005, 006, 007, 008, 009, 01, 010, 011...
5
  • Whoops, I forgot about the strings less that n. That is, my solution produces only permutations of length n.
    – liwp
    Feb 10, 2012 at 20:32
  • Edited it to do the strings of n, thanks for your help. Works great!
    – jlabroy
    Feb 10, 2012 at 20:42
  • I should point out that my solution makes n calls to permutations(), whereas @user949300's solution makes inputs.length^n calls to combos(). OTOH @user949300's solution produces the requested output ordering, whereas my solution interleaves the shorter strings in between the longer strings.
    – liwp
    Feb 10, 2012 at 21:53
  • My version also makes a somewhat non-robust check for the end condition. It works for the example (where all the strings are of length 1) but might need improvement in other cases.
    – user949300
    Feb 10, 2012 at 23:48
  • Great job. Working on this 4 DIN-A4 papers already. I am trying to calculate 0, 1, 2, 3, 4, 00, 01, 02, 03, 04, 10, 11. Hope this will bring the solution. Oct 12, 2015 at 20:47
0

If you don't need very long sequence you can use recursion like this:

for (String letter : letters) {
    String currentSequence = start + letter;
    System.out.println(currentSequence); // do something with your data here
    if (depth > 0) {
        printCombinations(currentSequence, depth - 1);
    }
}
0

This method appears to be able to take a set and create the combinations like you are looking for. You need to add the class to your project to be able to create a CombinationGenerator().

There doesn't appear to be only one way, but at least you would be able to copy in the method they used and call it.

String[] letters;
int[] indices;
CombinationGenerator x = new CombinationGenerator (letters.length, 3);
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 ());
}
0

Recursion to the rescue!

static List<String> permutations(int len, String[] letters) {
    List<String> ret = new ArrayList<String>();

    if (len == 1) {
        ret.addAll(Arrays.asList(letters));
    } else {
        List<String> perms =  permutations(len - 1, letters);
        for (String l : letters) {
            ret.add(l);
            for (String s : perms) {
                ret.add(l + s);
            }
        }
    }

    return ret;
}

Update: I tweaked the code to also produce permutations of 1 to n-1 characters.

Notice that the output isn't ordered the same way as specified the by the OP. I wouldn't expect it to matter, but who knows...

Example output:

[0, 00, 000, 001, 002, 003, 004, 005, 006, 007, 008, 009, 01, 010, 011, ...]

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.