两个字符串的交错排列

Question

我有两个字符串str1和str2。是否有一种算法可以使用递归来打印出这两个字符串的所有交错排列？

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

}

}

- Nath

---

@Mitch Wheat：我尝试了不同的方法，但是为什么不使用更有意义的东西，而要重新发明轮子呢？ - Nath

@Andrew Thompson：请问我的帖子为什么被编辑了？ - Nath

@Mitch Wheat：我不希望任何人替我解决它。 - Nath

你如何定义两个字符串的“交错（interleaving）”？ - Paŭlo Ebermann

@Paulo Ebermann：第一次打印可以只是将两个字符串相加。然后交换此字符串的_n_和_n-1_字符，然后交换_n-1_和_n-2_等。 - Nath

Answer 1

这个问题只是问是否存在递归算法来解决该问题，答案是肯定的。要找到它，需要寻找基本情况和“步骤”。

基本情况是当两个字符串中有一个为空时：

- interleave(s1, "") = {s1} - interleave("", s2) = {s2}

请注意，参数的顺序并不重要，因为

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

所以既然顺序不重要，我们将在第一个字符串的长度上进行递归。

好的，让我们看看一个情况如何导致另一个情况。我将使用一个具体的例子，您可以将其推广到实际代码。

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

每次向第一个字符串添加一个字符时，我们通过将新字符添加到旧结果集中的所有可能位置来形成新的结果集。让我们看看我们如何从第二个结果中形成第三个结果。当我们添加“2”时，第二个结果中的每个元素如何变成第三个结果中的元素？

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

现在这样看：

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

虽然一个或两个例子不能证明一般规律，但在这种情况下，您应该能够推断出规律。您将拥有一个循环，并在其中进行递归调用。

纯函数式编程实际上更有趣，但您标记了Java问题。

希望这对您有所帮助。如果您遇到进一步的困难，可以搜索“交错字符串”或“交错列表”。有一些解决方案。

编辑： 好吧，我刚刚写了这个傻瓜！在脚本语言中编写这些东西非常有趣，所以我想看看它在Java中的样子。并没有像我想象的那样糟糕！这是整个Java应用程序的封装。

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

- Ray Toal

---

提示：符号{x w | w = f(y)}表示将x连接到由调用f(y)返回的每个字符串中所形成的所有字符串集合。这将转化为一个“for”循环。希望这能帮到你。 - Ray Toal

@Nath，很难准确地找出问题所在，但我看到你正在使用数组（大小固定为10，这不是一种通用的解决方案），而不是列表，因为你说你还没有学习它们。对于这个问题来说，使用数组并不是一个好的选择，所以我建议你咬紧牙关学习列表。为此，我已经为你编写了一个完整的Java应用程序。它应该可以直接运行。 - Ray Toal

是的，在 for-i 循环中调用了多次，而且在递归的层级越深时也会调用多次。我只是指在 for-u 循环中没有多次调用。如果你仅看 for (String u : interleave(...) 这个循环，你只调用一次 interleave 然后进行迭代。与经典的 for 语句不同，比如 for (i=0; f(x); i++)，在该循环中每次都会调用 f(x)。希望这回答了你的问题！ - Ray Toal

在for(e1;e2;e3)中，表达式e2会在每次循环时被评估。在for(type x: a)中，其中a是一个数组表达式，表达式a只会被评估一次。 - Ray Toal

这个解决方案看起来非常复杂。请看下面我发布的代码。那是一个简单得多的解决方案。 - Kshitij Jain

Answer 2

如果我正确理解了你的问题 - 你想要两个字符串中所有字符的排列组合，那么以下代码将会有所帮助。你需要编写自己的交换函数，并获得包含两个字符串中所有字符的数组。 该算法将对数组中从第i个元素到第n个元素进行排列组合。这是C++代码，我想引用算法来源，但我记不清了。

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

- user461697

---

这不是OP所要求的。 - Trying

Answer 3

这里有一个使用递归方法的解决方案，而且易于理解

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

 }

- srinet.amit

Answer 4

你现在拥有的是一个很好的开始。问题是它只返回一个字符串，而不是那些字符串的列表。

改变你的函数以返回一个字符串列表，然后考虑如何将几个列表结合起来产生你想要的所有输出。

- Paŭlo Ebermann

---

是的，但是在此之前您需要计算正确的长度。对于列表，您可以逐个添加元素。 - Paŭlo Ebermann

好的，我知道了。我不知道为什么在添加评论时必须输入至少15个字符。 - Nath

他们想要避免像“好的，我明白了”这样的琐碎评论 :-p - Paŭlo Ebermann

我会尝试使用您的建议和Ray Toal的算法。 - Nath

Answer 5

这里是另一种递归解决方案：

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

- BrownRecluse

Answer 6

以下是这个问题更好、更简单易懂的解决方案：

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

该程序使用简单的递归调用来寻找解决方案。

- Kshitij Jain