Перестановка 2 строк в C++

Question

Я хочу написать программу, которая дает 2 строки (тип char) и объединить их по-разному. например, если 2 строки являются «abc» и «mn», программа должна печатать: abcmn abmnc amnbc mnabc mabcn mannbc mabnc ambnc ambcn abmcn. Как вы видите, они должны быть в упорядоченной форме в каждой строке. Я имею в виду, что, например, «c» не может быть раньше, чем «a» или «n» не может быть до «m». что я могу сделать?

Answer 1

Как я не знаю много о c++, я не могу написать полный код этой проблемы, но я опишу идею и алгоритм, как показано ниже.

Поскольку мы должны сохранить порядок символов в каждой строке, мы можем думать, процесс построения комбинаций, как это (используя пример abc и mn):

---

• давайте рассмотрим последний элемент сначала в каждой возможной комбинации: это либо c, либо n. Таким образом, мы можем создать список с двумя элементами: список: [['c'];['n']].

• Тогда давайте посмотрим на второй последний элемент:

  Если c является последним элементом, то возможные вторые последние элементы являются b и n, верно?

  Если n последний элемент, то возможные вторые последние элементы являются c и m, верно?

  Так давайте расширим предыдущего списка [['b';'c'];['n';'c'];['c';'n'];['m';'n']]

• Если продолжать третий последний элемент таким же образом, мы будем иметь

  [['a';'b';'c'];['n';'b';'c'];['b';'n';'c'];['m';'n';'c'];['b';'c';'n'];['m';'c';'n'];['c';'m';'n']]

• Продолжить вверх вы получите полный список.

---

Вот код OCaml только в случае, если вы знаете, функциональное программирование

let rec comb_2 l1 l2 = 
    let insert x = List.map (fun y -> x::y) in 
    match l1, l2 with 
    | [], [] -> [[]] 
    | hd::tl, [] | [], hd::tl -> comb_2 tl [] |> insert hd 
    | hd1::tl1, hd2::tl2 -> 
     (comb_2 tl1 l2 |> insert hd1) @ (comb_2 l1 tl2 |> insert hd2)