我怎样才能得到一个字符串的所有字谜

Question

我正在尝试查找字符串的所有可能的字谜并将它们存储在仅使用递归的数组中。

我卡住了，这就是我的全部。

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

编辑：我正在尝试查找单词的所有排列并将它们插入到数组中而不使用循环。

Answer 1

您需要在 permute() 再次调用 permute() 之前存储当前值。这就是你失去一些价值观的地方。

Answer 2

最简单的方法是这样的：

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

希望这真的有帮助。

Answer 3

您应该使用 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;
}

我怎样才能得到一个字符串的所有字谜

How can I get all the anagrams of a string

c++

recursion

anagram