用于字符串的C++递归排列算法 -> 不跳过重复项

Question

我在这个递归排列代码中找不到一个简单的语句来跳过重复项。我已经到处查找，似乎只能找到使用swap或java的示例。根据我的理解，我认为我需要在for循环后面加一行代码。

谢谢！

#include "genlib.h"
#include "simpio.h"
#include <string>
#include <iostream>

void ListPermutations(string prefix, string rest);


int main() {

    cout << "Enter some letters to list permutations: ";
    string str = GetLine();
    cout << endl << "The permutations are: " << endl;
    ListPermutations("", str);

    return 0;
}

void ListPermutations(string prefix, string rest)
{
    if (rest == "") 
    {
        cout << prefix << endl;
    } 
    else 
    {   
        for (int i = 0; i < rest.length(); i++) 
        {
            if (prefix != "" && !prefix[i]) continue; // <--- I tried adding this, but it doesn't work
            cout << endl<< "prefix: " << prefix << " | rest: " << rest << endl;     
            string newPrefix = prefix + rest[i];
            string newRest = rest.substr(0, i) + rest.substr(i+1);  
            ListPermutations(newPrefix, newRest);           
        }    
    }
}

- OverAir

---

我强烈感觉你可以以某种方式生成它们，这样重复项就不会首先被发出。然而，我的大脑现在出现故障，我似乎无法正确地想象它。 - sehe

@sehe - 请看下面我的答案 - 在开始之前，您只需要对字符串进行排序，并且仅对rest中的每个唯一字符递归一次。排序可能甚至不是必要的...但我现在无法理解它是否可以在没有排序的情况下工作 - je4d

Answer 1

这应该可以工作： 你的算法很好，我只是添加了一个测试：如果一个唯一字符已经在一个位置被使用，那么不会再进行更多的排列，因为所有包含该字符在该位置的排列都已经完成。

void ListPermutations(string prefix, string rest)
{
if (rest == "") 
{
    cout << prefix << endl;
} 
else 
{   
    for (int i = 0; i < rest.length(); i++) 
    {


        //test if rest[i] is unique.
        bool found = false;
        for (int j = 0; j < i; j++) 
        {
            if (rest[j] == rest[i])
                found = true;
        }
        if(found)
            continue;
        string newPrefix = prefix + rest[i];
        string newRest = rest.substr(0, i) + rest.substr(i+1);  
        ListPermutations(newPrefix, newRest);           
    }    
}
}

你可以在生成全排列之前对字符串进行排序，结果仍然相同。

- Hicham

---

非常感谢，太棒了，我从未想过要添加另一个for循环...！ - OverAir

Answer 2

要在C++中生成排列，可以使用std::next_permutation

它可以很好地处理重复条目，并做正确的事情。

- parapura rajkumar

---

谢谢您，但是否有其他使用布尔逻辑或其他方式的方法？谢谢您，抱歉之前没有说明这是作业。 - OverAir

为了跳过重复项，您可能需要修改代码以维护每个字符及其当前计数。递归函数将使用一个字符并降低其计数，然后调用自身。 - parapura rajkumar

Answer 3

忽略std::next_permutation的可用性，因为您对上一个答案的评论...

如果您想生成所有唯一的排列，您将需要在某个时刻将它们按顺序排序。最简单的方法是把它们都放在向量中，排序后在打印输出时抑制重复相邻条目。但这比必要的慢得多。

您需要先对字符串进行排序，以便生成相同的全排列会在彼此之后生成。然后在for循环中，请确保跳过'rest'中任何重复的字母。类似于：

    char lastAdditionToPrefix = '\0';
    for (int i = 0; i < rest.length(); i++) 
    {
        if (rest[i] == lastAdditionToPrefix) continue;
        lastAdditionToPrefix = rest[i];
        cout << endl<< "prefix: " << prefix << " | rest: " << rest << endl;     
        ...

我并不确定这个更改会完全修复你的代码，但它比你目前的代码更接近了。编辑：这个更改加上在主函数中排序输入，应该可以解决问题。

- je4d

---

谢谢，使用向量确实会更慢。我感觉这与比较前缀和剩余部分有关，然后跳过下一个递归或增加i？当我尝试解决它时，我的大脑简直要爆炸了... - OverAir

我认为你根本不需要将前缀与剩下的部分进行比较，你只需要确保你的函数对'rest'中的每个唯一字符只调用自己一次即可。我的答案中的代码应该会做到这一点，因为如果初始字符串已经排序（在你的示例中不是这样，因此你需要在main函数中调用std::sort对str进行排序），那么'rest'将始终被排序。 - je4d

Answer 4

有重复和无重复算法的区别在于，当你交换它时，确保要交换的字符之前没有被交换过。使用哈希映射来跟踪您以前交换过的内容。

请参见下面的C#代码。

    private void PermuteUniqueHelper(int[] nums, int index, List<IList<int>> res)
    {
        var used = new Dictionary<int, bool>();
        if (index == nums.Length)
        {
            res.Add(new List<int>(nums));
            return;
        }

        for (int i = index; i < nums.Length; i++)
        {
            if (!used.ContainsKey(nums[i]))
            {
                swap(nums[i], nums[index]);

                this.PermuteUniqueHelper(nums, index + 1, res);

                swap(nums[i], nums[index]);

                used.Add(nums[i], true);
            }
        }
    }

- Will Yu

Answer 5

测试过并且正常运行。思路是在每个堆栈层级的第i个位置上，记住该位置是否已经存在一个字符。

using namespace std;

void doPermutation(vector<char> &input, int index) {
    bool used[26] = {false};

    if(index == input.size()) {
        copy(input.begin(), input.end(), ostream_iterator<char>(cout, "") );
        cout << endl;

    } else {
      int i, j;
      for(i =index; i < input.size(); i++ ) {
        if(used[ input[i]-'a'] == false) {
           swap(input[i], input[index]);
           doPermutation(input, index+1);
           swap(input[i], input[index]);
           used[input[i]-'a'] = true;
       } 
      }
    }
}

  void permutation(vector<char>& input) {
      doPermutation(input, 0);
  }


int main()
{
   cout << "Hello World" << endl; 
   const char* inp = "alla";
   vector<char> input(inp, inp + 4 );

   permutation(input);

   return 0;
}

- Haoru HE