-4

If I have two strings with letters in them, how do I get all the possible combinations of the characters within them?

For example if I have i string "abc" and another "def" how do I get all the combinations like:

ad ae af

bd be bf ...etc.

the first letter of the combo will always be from the first string, and the second letter from the second string.

I want it to be able to work with multiple strings. It is for text prediction. Each string will represent letters on a mobile phone keypad. 

public void getCombos(){

String s1 = "abc"
String s2 = "def"

}
user1835504
  • 149
  • 2
  • 12
  • 2
    I've voted to close. This is just a "give me some code" question, with no apparent effort on the part of the question asker. – Duncan Jones Apr 29 '13 at 19:54
  • @DuncanJones sorry, its part of a much bigger piece of code, just don't know how to approach it. – user1835504 Apr 29 '13 at 19:55
  • No - that's not an excuse for not trying *anything*. Even a broken attempt would get some interest from us. But a statement of requirements and nothing else gets me wondering what hourly rate I should charge. – Duncan Jones Apr 29 '13 at 19:57
  • @DuncanJones fair enough, point noted. Just any attempts I had made were complete rubbish. Didn't see the value in putting it up. – user1835504 Apr 29 '13 at 20:05
  • @user1835504: What is the exact requirement? Any possible combinations (so even 'abcdef' or even 'abcabc' if duplicates are allowed) or a maximum length or ...? – Menno Apr 29 '13 at 20:16

4 Answers4

1

Normally I'd try to avoid nested loops, though I don't see another way in this case (well, not a better way).

char[] s1array = s1.toCharArray();
char[] s2array = s2.toCharArray();
for(char s1char : s1array) {
    for(char s2char : s2array) {
        String value = String.valueOf(s1char) + String.valueOf(s2char);
        System.out.println(value);
    }
}

Edit

In order to get the single characters too:

char[] s1array = s1.toCharArray();
char[] s2array = s2.toCharArray();
for(char s1char : s1array) {
    for(char s2char : s2array) {
        String value = String.valueOf(s1char) + String.valueOf(s2char);
        System.out.println(value);
    }
    System.out.println(String.valueOf(s1char));
}
for(char s2char : s2array) {
    System.out.println(String.valueOf(s2char));
}

Edit 2

In case you want to go for all combinations, there are some very nice answers on Stackoverflow. Like this one.

Community
  • 1
  • 1
Menno
  • 12,175
  • 14
  • 56
  • 88
  • if there is duplicate character, this is gonna fail – smttsp Apr 29 '13 at 19:56
  • As you can read in the post, these are representations of keypads on phones. Would be a nice failure in the code if there are duplicates. – Menno Apr 29 '13 at 19:56
  • @Vulcan: You're right. Have been answering too many PHP questions today. – Menno Apr 29 '13 at 19:57
  • Also, this answer does not handle the non-combination solutions such as `a`, `b`, and so forth. Once these are included, and minor compilation mistakes are fixed, this answer gets my vote. – FThompson Apr 29 '13 at 19:59
  • How do you mean Vulcan? That's the responsibility of providing the right `String`s isn't it? Not sure I fully understand what you mean though. – Menno Apr 29 '13 at 20:04
  • 1
    @Aquillo: this only gives two char-lengthed strings, not all the combinations – smttsp Apr 29 '13 at 20:05
  • Ah didn't read the requirement fully. Will edit it. – Menno Apr 29 '13 at 20:06
  • @Aquillo: you miss 3-4-5-6 characters too – smttsp Apr 29 '13 at 20:09
  • @smttsp: I don't see anything like that specified. If this is the case, OP should specify his question better. – Menno Apr 29 '13 at 20:11
0

Given your description I've created a simple quadratic algorithm:

public static void combine(String s1, String s2) {
    for(int i = 0; i < s1.length(); i++) {
        System.out.println(s1.charAt(i));
        for(int j = 0; j < s2.length(); j++) {
            System.out.println(String.format("%s%s", s1.charAt(i), s2.charAt(j)));
        }
    }
}

If you need to avoid duplicates you could insert the chars into a set (see HashSet) and then use them to generate the strings. You could also keep track of every char used and avoid use them twice...

Anyway, hope my example helps you get started.

vdeantoni
  • 1,948
  • 14
  • 19
  • `"" + ` is a bad habbit of converting objects/primitives IMHO. – Menno Apr 29 '13 at 20:09
  • you right good catch. Regarding the empty concat, one can always use String.format instead (or even String.valueOf), this was just the quickest/simplest way I thought of to just make it work. – vdeantoni Apr 29 '13 at 20:12
  • No problem, for the sake of a short answer. Though this is a way people pick up on bad habbits, that's why I made a note of it ;) – Menno Apr 29 '13 at 20:14
  • Just curious, not to critize either your or my code. What would be quicker? Dissecting a `String` to `char[]` or requesting `charAt()` multiple times? – Menno Apr 29 '13 at 20:15
  • Good question. Apparently it depends on the size of the string, see: http://stackoverflow.com/questions/8894258/fastest-way-to-iterate-over-all-the-chars-in-a-string – vdeantoni Apr 29 '13 at 20:17
  • Nice link! That's one hell of an answer. Thanks :) – Menno Apr 29 '13 at 20:19
0

I have thought of an algorithm but I dont know how to implement it.

It is going to be tree structure, which includes all the characters in the first level except duplicates, and you will go top down and print every leaf.

For example we have S1="abc", S2="ade" we will have something like the following tree:enter image description here

According to that image, we will write "a" "b",..., "e" and "aa(only one time), ca, cb, cd"(two charactered strings) and this will save us from duplicates, and all string are going to be printed out

smttsp
  • 4,011
  • 3
  • 33
  • 62
-1

try a nested for, combined with the String#toCharArray() method

jambriz
  • 1,273
  • 1
  • 10
  • 25