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

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

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

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

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

1

Решение

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

#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;
}
0

Другие решения

Вам необходимо сохранить текущее значение до permute() звонки permute() снова. Это где вы теряете некоторые из ваших ценностей.

0

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

// 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++;
}

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

0
По вопросам рекламы ammmcru@yandex.ru
Adblock
detector