Have Geek Brain

Find all permutations of words in a sentence

how can i get all permutations of words in a sentence. Can you provide some example C # code? for example: if the sentence is "c # not java", the output should be 1) c # not java 2) c # java no 3) java no c # 4) java c # not 5) not java c # 6) not c # java, etc.

+2


a source to share


4 answers


Try it if it 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;
        }
    }
+1


a source


Divide this into two tasks:

  • Divide the sentence into words
  • Rearrange


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

Note. This is not pure asp.net, this is more like a permutation question. If you have permutations, you can do them in HTML, of course.

+1


a source


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 have only 1. The number of permutations without repetition is 3! (3 * 2 * 1) = 6.

first word | second word | third word

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

Another example is 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
0


a source


I just changed 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;
    }
}

You can also 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);
}
0


a source






More articles:


All Articles