How to concatenate all cases of word presentation in a sentence JAVA

Question

Input: list of n words "word1 word2 word3...wordn"

Output: list of strings in concatenation of all cases of permutation presentation as:

s1: "word1 word2"
s2: "word1 word3"
s3: "word2 word1"
s4: "word2 word3"
s5: "word3 word1"
s6: "word3 word1"
s7: "word1 word2 word3"
s8: "word1 word3 word2"
s9: "word2 word1 word3"
s10: "word2 word3 word1"
s11: "word3 word1 word2"
s12: "word3 word2 word1"
...
sm: "wordn...word3 word 2 word 1"

I try this code:

    public static List<String> PermuteWords(String s){
        String[] ss = s.split(" ");
        boolean[] used = new boolean[ss.length];
        String res = "";
        List<String> list = new ArrayList<String>();
        permute(ss, used, res, 0, list);
        return list;
    }

    private static void permute(String[] ss, boolean[] used, 
        String res, int level, List<String> list) {

        if (level == ss.length && res != ""){
            list.add(res);
            return;
        }

        for (int i = 0; i < ss.length; i++) {
            if (used[i]) {
                continue;
            }
            used[i] = true;
            permute(ss, used, res + " " + ss[i], level + 1, list);
            used[i] = false;
        }
    }

    public static void main(String args[]){

        String inputString="word1 word2 word3";
        List<String> test=PermuteWords(inputString);

        for (int i = 0; i < test.size(); i++) {
            System.out.println(test.get(i));
        }
    }

Output:

 word1 word2 word3
 word1 word3 word2
 word2 word1 word3
 word2 word3 word1
 word3 word1 word2
 word3 word2 word1

However it is missing some cases as:

s1: "word1 word2"
s2: "word1 word3"
s3: "word2 word1"
s4: "word2 word3"
s5: "word3 word1"
s6: "word3 word1"

Does anyone can solve this problem?

Possible duplicate of [Calculating all of the subsets of a set of numbers](http://stackoverflow.com/questions/4640034/calculating-all-of-the-subsets-of-a-set-of-numbers) — PM 77-1, Mar 27 '16 at 22:55
@PM 77-1 it is different, because that did not solve the problem all cases of permutation in words as " word1<->word2" and "word2<->word1". — Nguyen Chi Hieu, Mar 28 '16 at 00:07

score 1 · Accepted Answer · answered Mar 28 '16 at 00:23

How about something like this?

private static void permute(String[] ss, boolean[] used,
                            String res, int level, List<String> list) {

    // End case
    if (level == ss.length && res != ""){
        list.add(res);
        return;
    }

    for (int i = 0; i < ss.length; i++) {
        // Check if the string is currently used
        if (used[i]) {
            continue;
        }
        // Check if res is empty or a single word
        if(level > 1)
            list.add(res);
        used[i] = true;
        permute(ss, used, res + " " + ss[i], level + 1, list);
        used[i] = false;
    }
}

Output:

 word1 word2
 word1 word2 word3
 word1 word3
 word1 word3 word2
 word2 word1
 word2 word1 word3
 word2 word3
 word2 word3 word1
 word3 word1
 word3 word1 word2
 word3 word2
 word3 word2 word1

The problem with the code I believe is that elements were added to the list only when the recursion reached the end, not allowing subelements like you wanted.

Yeah, thanks you. It is good. I ran your code, but It still has duplicate output. e.g., "word1 word2" appears more than 1 time. However it will be easy to fix. — Nguyen Chi Hieu, Mar 28 '16 at 00:40

How to concatenate all cases of word presentation in a sentence JAVA

1 Answers1