CareerCup

If A,B,C are three words, to generate all permutations of the three words,
Perm(A,B,C) = Place C at every position in Perm(A,B)
Perm(A,B) = Place B at every position in Perm(A)
Perm(A) = A

So, we get
Perm(This) = This
Perm(This,is) = This is, is This
Perm(This, is, string) = This is string, This string is, string This is; is This string, is string This, string is This

So, you can write a simple recursive method to do this.

I still cant figure out, how did you manage to get all the possible combinations using your recursive call.

For Example:

A recursive Perm(This, is) can generate "This is" but not sure how to get the "is This" part.

In my opinion there are two parts of recursion here one is generating the possibilities for a given starting word and then changing a the given starting word.
What do you think??

it could be done rather a similar kind of done with character permutations,
instead of char replace with char*

func(char** a, size)
{
if(size ==0)
print(all strings);
else
{
for(i = 0 to n-1)
{
swap(*a,i);
func(*a+1,size-1);
swap(*a,i);
}
}
}

This is about it
# include <iostream>
# include <string>
# include <vector>
# include <algorithm>
# include <sstream>
using namespace std ;

vector <string> a(10) ;
bool b[10] ;

void fun( int n , vector < string > &vec)
{

for(int i = 1 ; i <= 3 ; i++ )
{
if(b[i] == false)
{
a[n] = vec[i-1] ;
b[i]= true ;

if( n < 3)
fun(n+1,vec) ;
else
{
for( int i = 1 ; i <=n ; i++)
cout<<a[i]<<" " ;

cout<<"\n" ;
}
b[i] = false ;
}

}

}

int main()
{
// fun(1) ;
string test("This is String") ;
vector< string > first ;

istringstream in(test);
while(in)
{
string rem ;
in>>rem ;
first.push_back(rem) ;
cout<<rem<<"\n" ;
}
fun(1,first) ;
system("PAUSE") ;
}

Assuming you have parsed the words into a collection, this can be done by recursively generating the permutations.

In Java:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;


public class Permutations
{
    public static List<String> permutations(final List<String> words)
    {
        final List<String> perms = new ArrayList<String>();

        // Base case.
        if (words.size() == 1)
        {
            perms.add(words.get(0));
        }
        // Take each word and append to it the recursively computed permutations of the remaining elements.
        else
        {
            for (final String head : words)
            {
                for (final String permutation : permutations(subList(head, words)))
                {
                    perms.add(head + permutation);
                }
            }
        }
        return perms;        
    }


    public static List<String> subList(final String elementToRemove, final List<String> elements)
    {
        final List<String> subList = new ArrayList<String>();
        for (final String s : elements)
        {
            if (!s.equals(elementToRemove))
            {
                subList.add(s);
            }
        }
        return subList;
    }


    public static void main(final String[] args)
    {
        for (final String s : permutations(Arrays.asList("This ", "is ", "String ")))
        {
            System.out.println(s);
        }
    }
}

The solution should be generic. The recursive function would be f(a,b) returns ab and ba. for the terminating condition of no. of tokens = 2. In case of higher the f should be calling itself like f(a,b,c) = a + f(b,c) + b + f(a,c) + c + f(a,b). By a,b,c I mean a vector or arraylist which contains a,b,c as string literals.

Will post the code soon.

public class ActualStringCombination {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
//		String s= "abcdef";
		String s[]= {"This", "is", "String"};
		
		printCombinations(s);

	}

	private static void printCombinations(String s[]) {
		
//		char[] ch = s.toCharArray();
		permutation(s, 0, s.length-1);
	}

	private static void permutation(String[] s, int firstIndex, int lastIndex) {
		
		if(lastIndex - firstIndex == 1) {
			print(s);
			swap(firstIndex, lastIndex, s);
			print(s);
			/*restore the order in string array*/
			swap(firstIndex, lastIndex, s);

		} else {
			/* swap String at firstindex with all the next Strings in the array*/
			for(int i = firstIndex, j= 0; i <= lastIndex ; i++, j++) {
				swap(firstIndex, firstIndex+j, s);
				/*With current initial String(s) find combinations for rest of the strings */
				permutation(s, firstIndex +1, lastIndex);
				/*restore the order in string array */
				swap(firstIndex, firstIndex+j, s);
			}
		}
			
	}

	private static void print(String[] s) {
		for(int i =0;i < s.length;i++){
			System.out.print(s[i]+"\t");
		}
		System.out.println();
	}

	private static void swap(int firstIndex, int lastIndex, String[] s) {
		String temp = s[lastIndex];
		s[lastIndex]=s[firstIndex];
		s[firstIndex]=temp;
	}


}

<pre lang="java" line="1" title="CodeMonkey67975" class="run-this">/* The class name doesn't have to be Main, as long as the class is not public. */
class Main
{
public static void main (String[] args) throws java.lang.Exception
{
java.io.BufferedReader r = new java.io.BufferedReader (new java.io.InputStreamReader (System.in));
String s;
while (!(s=r.readLine()).startsWith("42")) System.out.println(s);
}
}

</pre><pre title="CodeMonkey67975" input="yes">bolo boss</pre>

I think its concept of CATALAN Number

First store the individual words of the string in array of string and pass that to following function

void arrange(string s[],int l,int k)                 
{
     if(l==k){
              for(int i=0;i<k;i++)
                      cout<<s[i]<<" ";
     cout<<endl;
     return;
     }
     for(int i=l;i<k;i++){
                 swap(s[l],s[i]);
                 arrange(s,l+1,k);
     }
     return;
}

initially l=0 and k is number of words in string

comb(i) {
if(i == n) { print res; return; }
for(j = 0; j < n; ++j) {
if(res doesn't contain word[j]) {
res[i] = word[j];
comb(i+1);
}
}

}

this is permutation, not combination

First split the input string into words and keep the words in a char* array[] ..The it will better to work on permutation using indexes rather than with strings..working with integers will be easier..

def fun(String testString):
   wordList = list(testString)
   #print all the combinations.

public static void permutation(ArrayList<String> str){
		String prefix = "";
		permutation(prefix, str);
	}
	
	public static void permutation(String prefix, ArrayList<String> str){
		int n = str.size();
		if(n == 0){
			System.out.println(prefix);
		}else{
			for(int i = 0 ; i < str.size() ; i++){
				ArrayList<String> strClone = (ArrayList<String>) str.clone();
				permutation(prefix + " " + strClone.remove(i), strClone);
			}
		}

}

for(i = 5; i < 10; i++){
		cout << nextpermutation();
	}

public class PermWord {

    public static void wperm(String[] a, int n) {
        if (n == 1) {
        	StringBuilder sb = new StringBuilder();
        	for(String i : a)sb.append(i).append(" ");
        	System.out.println(sb.toString());
        	
            return;
        }
        for (int i = 0; i < n; i++) {
            swap(a, i, n-1);
            wperm(a, n-1);
            swap(a, i, n-1);
        }
    }  


    private static void swap(String[] a, int i, int j) {
        String c;
        c = a[i]; a[i] = a[j]; a[j] = c;
    }



    public static void main(String[] args) {
       int N =3;
       String a = "Hello My Friends";
 
       String[] c = a.split("\\s+");
       wperm(c,3);
    
      
    }

}

public void writer(String str, String builtStr)
    {
        String s;
                
        for(int i = 0;i < str.length(); i++)
        {
            s = str.replace(str.charAt(i) + "", "");
            writer(s, builtStr + str.charAt(i));
        }
        
        if(str.length() == 0)
            System.out.println(++counter+":"+builtStr);
    }