Shuffle two lines

Question

I have two lines str1 and str2 . Is there any algorithm that can be used to print all interlaces of two lines using recursion?

Update:

 public class Interleave { private String resultString[] = new String[10]; private String[] interStr(String str1, String str2){ int n = ((Factorial.factorial(str1.length() + str2.length())) / (Factorial.factorial(str1.length()) * Factorial.factorial(str2.length()))); //n is number of interleavings based on (str1.length()+str2.length())! / (str1.length()! * str2.length()!) if(str1.length() == 0){ resultString[0] = str2; return resultString; } if(str2.length() == 0){ resultString[0] = str1; return resultString; } else{ for(int i = 0; i < n; i++){ resultString[i]= str1.substring(0, 1) + interStr(str1.substring(1), str2.substring(1)); } } return resultString; } public static void main(String[] args) { Interleave obj = new Interleave(); obj.interStr("12", "abc"); for(int i = 0; i < obj.resultString.length; i ++){ System.out.println(obj.resultString[i]); } } } 

Answer 1

The question simply asked if there is a recursive algorithm for the problem, and the answer is yes. To find it, find the base case and then the "step".

The main case is when one of the two lines is empty:

• interleave(s1, "") = {s1}

• interleave("", s2) = {s2}

Note that the order of the arguments does not matter, because

• interleave("ab", "12") = {"ab12", "a1b2", "1ab2", "a12b", "1a2b", "12ab"} = interleave("12", "ab")

So, since the order does not matter, we consider recursion along the length of the first row.

So let's see how one case leads to the next. I just use a specific example, and you can generalize this to real code.

• interleave("", "abc") = {"abc"}
• interleave("1", "abc") = {"1abc", "a1bc", "ab1c", "abc1"}
• interleave("12", "abc") = {"12abc", "1a2bc", "1ab2c", "1abc2", "a12bc", "a1b2c", "a1bc2", "ab12c", "ab1c2" "abc12" }

Therefore, every time we added a character to the first line, we formed a new result set, adding a new character to all possible positions in the old result set. Let's see how exactly we formed the third result above the second. How did each element in the second result turn into elements in the third result when we added “2”?

• "1abc" => "12abc", "1a2bc", "1ab2c", "1abc2"
• "a1bc" => "a12bc", "a1b2c", "a1bc2"
• "ab1c" => "ab12c", "ab1c2"
• "abc1" => "abc12"

Now look at things like this:

• "1abc" => {1 w | w = rotation ("2", "abc")}
• "a1bc" => {a1 w | w = rotation ("2", "bc")}
• "ab1c" => {ab1 w | w = rotation ("2", "c")}
• "abc1" => {abc1 w | w = interleave ("2", "")}

Although one or two examples do not prove the rule at all, in this case you should be able to conclude that such a rule. You will have a loop with recursive calls inside it.

This is actually a little more interesting for pure functional programming, but you noted the Java question.

Hope this is the beginning for you. If you are stuck, you can search the web for "alternating lines" or "alternating lists." There are several solutions.

EDIT:

Ok, I just wrote this stupid thing! It is very interesting to write these things in scripting languages, so I thought it would be great to see how it was in Java. Not as bad as I thought it would be! Here it is packaged as a whole Java application.

 import java.util.ArrayList; import java.util.List; public class Interleaver { /** * Returns a list containing all possible interleavings of two strings. * The order of the characters within the strings is preserved. */ public static List<String> interleave(String s, String t) { List<String> result = new ArrayList<String>(); if (t.isEmpty()) { result.add(s); } else if (s.isEmpty()) { result.add(t); } else { for (int i = 0; i <= s.length(); i++) { char c = t.charAt(0); String left = s.substring(0, i); String right = s.substring(i); for (String u : interleave(right, t.substring(1))) { result.add(left + c + u); } } } return result; } /** * Prints some example interleavings to stdout. */ public static void main(String[] args) { System.out.println(interleave("", "")); System.out.println(interleave("a", "")); System.out.println(interleave("", "1")); System.out.println(interleave("a", "1")); System.out.println(interleave("ab", "1")); System.out.println(interleave("ab", "12")); System.out.println(interleave("abc", "12")); System.out.println(interleave("ab", "1234")); } } 

Answer 2

If I correctly interpreted your question - you need all permutations of all characters in both lines, then the following code will help. You will need to write your own swap function and somehow get an array of all the characters on both lines. This algorithm will be rearranged from the ith element to the nth element of the array. This is in C ++, I would include a link to where this algorithm came from, but I don’t remember.

 void getPermutationsR(char characters[], int n, int i) { if (i == n) { //Output the current permutation } else { for (int j=i; j<n; j++) { swap (characters, i, j); getPermutationsR(characters, n, i+1); swap (characters, i, j); } } } 

Answer 3

You have a good start now. The problem is that it returns only one row, not a list of them.

Modify your function to return a list of strings, and then think about how you could combine multiple lists to get all the result you need.

Answer 4

Here is a solution using a recursive approach that is easy to understand.

 public class Interleave { public static List<String> interleave(String first, String second){ if(first.length() == 0){ List<String> list = new ArrayList<String>(); list.add(second); return list; } else if(second.length() == 0){ List<String> list = new ArrayList<String>(); list.add(first); return list; } else{ char c1 = first.charAt(0); List<String> listA = multiply(c1,interleave(first.substring(1),second)); char c2 = second.charAt(0); List<String> listB = multiply(c2,interleave(first,second.substring(1))); listA.addAll(listB); return listA; } } public static List<String> multiply(char c,List<String> list){ List<String> result = new ArrayList<String>(); for(String str : list){ String res = Character.toString(c) + str; result.add(res); } return result; } public static void main(String[] args){ System.out.println(interleave("ab", "1234")); System.out.println(interleave("a", "b")); System.out.println(interleave("ab", "cd")); } } 

Answer 5

Below is a much better and simpler solution to solve this problem:

 public class Interleaver { /** * Returns a list containing all possible interleavings of two strings. * The order of the characters within the strings is preserved. */ public static String s1 = "abc"; public static String s2 = "12"; public static void interleave(int i, int j, String s) { if (i == s1.length() && j == s2.length()) { System.out.println("" + s); } if (i != s1.length()) { interleave(i + 1, j, s + s1.charAt(i)); } if (j != s2.length()) { interleave(i, j + 1, s + s2.charAt(j)); } }//Method ends here /** * Prints some example interleavings to stdout. */ public static void main(String[] args) { interleave(0, 0, ""); }//Method ends here }//Class ends here 

The program uses only simple recursive calls to find a solution.

Answer 6

Here is another recursive solution:

 public class Interleaving2 { public static void main(String[] args) { String x = "ab"; String y = "CD"; int m = x.length(); int n = y.length(); char[] result = new char[m + n + 1]; interleave(x, y, result, m, n, 0); } public static void interleave(String x, String y, char[] result, int m, int n, int i) { if (m == 0 && n == 0) { System.out.println(String.valueOf(result)); } if (m != 0) { result[i] = x.charAt(0); interleave(x.substring(1), y, result, m - 1, n, i + 1); } if (n != 0) { result[i] = y.charAt(0); interleave(x, y.substring(1), result, m, n - 1, i + 1); } } }