Java increment string through array

Question

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

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

user949300 · Accepted Answer · 2012-02-10 20:25:27Z

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...

answered Feb 10, 2012 at 20:25

user949300

15.7k7 gold badges39 silver badges69 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

liwp Over a year ago

Whoops, I forgot about the strings less that n. That is, my solution produces only permutations of length n.

jlabroy Over a year ago

Edited it to do the strings of n, thanks for your help. Works great!

liwp Over a year ago

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.

user949300 Over a year ago

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.

Matthis Kohli Over a year ago

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.

Ivan Nevostruev · Accepted Answer · 2012-02-10 19:47:37Z

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);
    }
}

answered Feb 10, 2012 at 19:47

Ivan Nevostruev

28.9k8 gold badges69 silver badges82 bronze badges

Comments

Matt Plank · Accepted Answer · 2012-02-10 19:49:45Z

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 ());
}

answered Feb 10, 2012 at 19:49

Matt Plank

3336 silver badges12 bronze badges

Comments

liwp · Accepted Answer · 2012-02-10 21:56:40Z

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, ...]

edited Feb 10, 2012 at 21:56

answered Feb 10, 2012 at 20:14

liwp

6,9562 gold badges30 silver badges41 bronze badges

Collectives™ on Stack Overflow

Java increment string through array

4 Answers 4

5 Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

5 Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related