Чередование двух строк

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

}

}

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

Answer 2

Вот решение с использованием рекурсивного подхода, тоже простое для понимания

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 3

То, что у вас сейчас есть, хорошее начало. Проблема в том, что он возвращает только одну строку, а не их список.

Измените вашу функцию, чтобы она возвращала список строк, а затем подумайте, как можно объединить несколько списков, чтобы получить все выходные данные.

Answer 4

Если я правильно истолковал ваш вопрос - вам нужны все перестановки всех символов в обеих строках, тогда поможет следующий код.Вам нужно будет написать свою собственную функцию подкачки и каким-то образом получить массив всех символов в обеих строках.Этот алгоритм будет переставлять от 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);
        }
    }
}

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

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

Программа использует простые рекурсивные вызовы для поиска решения.