finding all permutation of words in a sentence.

Question

how can i get all permutation of words in a sentence.can you give a sample c# code for that? eg: if the sentence is "C# not java", the output should be, 1)c# not java 2)c# java not 3)java not c# 4)java c# not 5)not java c# 6)not c# java etc.

Answer 1

Separate this into two tasks:

1. Split the sentence into words
2. Do the permutations

And, in addition, what about duplicates?
"green green bag" - this sentence has two "permutations" that are considered as one, if you see my point.

Note: It's not pure asp.net, it's more like a permutations question. Once you have the permutations, you can render them into HTML, of course.

Answer 2

Try if this works for you.

public static List<string> PermuteWords(string s)
    {
        string[] ss = s.Split(new string[] {" "}, StringSplitOptions.RemoveEmptyEntries);
        bool[] used = new bool[ss.Length];
        string res = "";
        List<string> list = new List<string>();
        permute(ss, used, res, 0, list);
        return list;
    }

    private static void permute(string[] ss, bool[] 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;
        }
    }

Answer 3

In the example you have 3 words meaning that for the first word there are 3 possibilities for the second word you have 2 possibilities and for the third word you only have 1. The amount of permutations without repetition is 3! (3*2*1) = 6.

first word | second word | third word

(3 cases) | (2 cases) | (1 case)

Another example would be with 4 words. 4! = 24.

(General case: n!)...

Ex. (This same example can be implemented with words).

1 2 3 4

Permutations without repetition.

1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 3 2
1 4 2 3

2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 3 1
2 4 1 3

3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 2 1
3 4 1 2

4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 2 1
4 3 1 2

Answer 4

I just modified the version above:

import java.util.*;

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

Also you can use the following code to test these functions:

List<String> ls=new ArrayList<String>();

ls = PermuteWords(str);
Iterator it=ls.iterator();

int i = 0;
while(it.hasNext())
{
    String value=(String)it.next();
    System.out.println(++i + " " + value);
}