Как я могу получить все анаграммы строки

Я пытаюсь найти все возможные анаграммы строки и сохранить их в массиве, используя только рекурсию.

Я застрял, и это все, что у меня есть.

int main()
{
    const int MAX = 10;
    string a = "ABCD";
    string arr[10];

    permute(arr, a, 0, a.size(), 0);

    return 0;
}

void permute(string arr[], string wrd, int firstLetter, int lastLetter, int it)
{
    if (firstLetter == lastLetter)
        *arr = wrd;
    else
    {
            swap(wrd[firstLetter], wrd[it]);
            permute(arr, wrd, firstLetter + 1, lastLetter, it++);
    }
}

Порядок не имеет значения. Пример: строка «abc»; массив должен иметь: abc, acb, bca, bac, cab, cba

Изменить: я пытаюсь найти все перестановки слова и вставить их в массив без использования циклов.


c++ recursion anagram
person Tester643    schedule 03.12.2017    source источник
comment
Ну, для начала, будет 24 различных анаграммы четырехбуквенного слова. Попытка записать их в string arr[10] приведет к ужасным результатам.   -  person Sam Varshavchik    schedule 03.12.2017
comment
Анаграммы - это слова. Это перестановки, и так уж получилось, что C++ имеет стандартные алгоритмы для перестановок.   -  person chris    schedule 03.12.2017
comment
en.cppreference.com/w/cpp/algorithm/next_permutation   -  person Jesper Juhl    schedule 04.12.2017
comment
@chris, использующий STD, отнимает все удовольствие от его кодирования.   -  person Jake Freeman    schedule 04.12.2017
comment
Могут ли быть повторяющиеся буквы?   -  person stark    schedule 04.12.2017

Ответы (3)


arrow_upward
1
arrow_downward

Вы должны использовать string& для параметра, так как это будет более эффективно. Вы должны перебирать символы.

#include <iostream>
#include <string>
using namespace std;

void permute(string* arr, int& ind, string& wrd, int it) {
    if (it == wrd.length()) {
        arr[ind++] = wrd;
    } else {
        for (int i = it; i < wrd.length(); ++i) {
            swap(wrd[i], wrd[it]);
            permute(arr, ind, wrd, it + 1);
            swap(wrd[i], wrd[it]);
        }
    }
}

int main() {
    string a = "ABCD";
    string arr[100]; // enough size to store all permutations
    int ind = 0;
    permute(arr,ind, a, 0);
    for (int i = 0; i < ind; ++i) {
        cout << arr[i] << endl;
    }
    return 0;
}
person abdullah    schedule 03.12.2017
comment
Можно ли это сделать без цикла for? - person Tester643; 04.12.2017
comment
Насколько я понимаю, это должно требовать такого типа итерации. - person abdullah; 04.12.2017

arrow_upward
0
arrow_downward

Вам нужно сохранить текущее значение, прежде чем permute() снова вызовет permute(). Здесь вы теряете некоторые из своих ценностей.

person EpicVoyage    schedule 03.12.2017

arrow_upward
0
arrow_downward

Самый простой способ сделать это будет примерно так:

// Precondition locs size is the same x length and arr is the right size to handle all the permutations
void permute(string arr[], string x, int locs[], int size, int & index)
{
    for(int i = 0; i<size; i++)
    {
        if(locs[i] < size) locs[i]++;
        else locs[i] = 0;
    }
    arr[index] = "";
    for(int i = 0; i<size; i++)
    {
        arr[index] += x[locs[i]];
    }
    index++;
}

Надеюсь, это действительно поможет.

person Jake Freeman    schedule 03.12.2017