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);           
        }    
    }
}

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);           
    }    
}
}

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

Answer 2

В C ++ для генерации перестановки используйте std :: next_permutation

Он отлично справится с дублирующимися записями и сделает все правильно

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;     
        ...

Я не уверен, что это изменение полностью исправит ваш код, но оно ближе, чем вы в данный момент. edit: это, плюс сортировка ввода в main (), будет работать

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);
            }
        }
    }

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