Print out all the possible combinations of a string

Question

public static void combinations(String s) {
    char[] original = s.toCharArray();
    int original_size = s.length();

    String temp = new String();
    for (int i = 0; i < original_size; i++) {// add the first element
        String sb = "";
        temp = "";
        sb = "" + original[i];
        temp = sb.toString();

        System.out.println(sb);
        for (int j = i + 1; j < original_size; j++) {// add the other
                                                        // element in the
                                                        // array
            if (i == j)
                continue;
            sb = temp + "" + original[j];
            System.out.println(sb);
        }
        // sb = "";
    }
}

public static void main(String[] args) {
    combinations("abc");
}

The results should be: a, ab, ac, abc, b, bc, c

But my program is: a, ab, ac, b, bc, c. I can't print out abc

The output you describe is not "all possible combinations" but "all possible substrings" which is totally different thing (character-order is kept). — Nir Alfasi, Jan 02 '13 at 01:29
Suggestion: Since you have an expected output, and the program is not returning the expected output, put a breakpoint at an appropriate point in the code (such as at the start of the second for loop) and see for yourself why abc is never going to be generated by stepping through the program line-by-line. — NYCdotNet, Jan 02 '13 at 01:32
if `j = i + 1` is the starting condition of the second for-loop, how is it possible that `i == j` will happen ? — Nir Alfasi, Jan 02 '13 at 01:33
You are doing it wrong way, this sort of problem should be handled recursively. It is basically "all subsets of a set excluding empty set" problem. It is explained here:http://stackoverflow.com/questions/728972/finding-all-the-subsets-of-a-set — specialscope, Jan 02 '13 at 01:35

Shivam · Answer 1 · 2013-01-02T02:06:02.480

1

If your output should be a, ab, ac, abc, b, bc, c then its not really a combinations of all the letters as it must also include ca, cb etc. I think you are trying to find the combinations but in given order of a string. Approach below will be able to find what you are trying to do. Just call orderedCombinations("abc").

public static void orderedCombinations(String s) {
    for(int i = 0; i < s.length(); i++) {
        for(String s1 : subStrings(s.substring(i + 1))) {
            System.out.println(s.charAt(i) + s1);
        }
    }
}

public static String[] subStrings(String s) {
    ArrayList<String> strs = new ArrayList<String>();
    strs.add("");
    for(int i = 0; i < s.length(); i++) {
        for(int j = i + 1; j < s.length() + 1; j++)
            strs.add(s.substring(i, j));
    }

    return strs.toArray(new String[0]);
}

edited Jan 02 '13 at 02:06

answered Jan 02 '13 at 01:47

Shivam

2,134
1
18
28

@alfasin Sorry, since it was not really a combinations I though he was trying to find all possible sub-strings. Any ways, thanks for letting me know, I've corrected by method. – Shivam Jan 02 '13 at 02:00
+1 good answer! now there's another question: does it matter in which order you print ? he originally provided: `a, ab, ac, abc, b, bc, c` while you print `a, ab, abc, ac, b, bc, c` – Nir Alfasi Jan 02 '13 at 02:12

score 0 · Answer 2 · answered Jan 02 '13 at 02:04

noticed you have two for-loops, but only one is needed really needed to go all possible combinations from A-Z. But the combinations you have listed is not all possible combinations of the string.

Such possibilities would be a , ab , ac, abc , acb, b, ba, bc , bac , bca , c, ca , cb , cba, cab

Since you decided to structure your program around for-loops the answer lies somewhere in the fact that you need a third loop for three-characters rather than just two, but without a clear objective for what your program's goal is, I can't re-write an example.

I recommend you start over, and while playing with code to get the feel of syntax is fine, try to write more efficiently in your examples. original_size is a useless variable for example, you could just use s.length.

Print out all the possible combinations of a string

2 Answers2