Алгоритм для печати всех перестановок с повторением чисел

Question

Я успешно разработал алгоритм для печати всех перестановок с повторением чисел. Но алгоритм, который я разработал, имеет недостаток. Он работает только в том случае, если символы строки уникальны.

Может кто-то помочь мне в расширении алгоритма для случая, когда символы из строки не могут быть уникальными .. Моим код до сих пор:

#include<cstdio> 
#include<cstdlib> 
#include<cstring> 
#include<climits> 
#include<iostream> 

using namespace std; 

void _perm(char *arr, char*result, int index) 
{ 
    static int count = 1; 
    if (index == strlen(arr)) 
    { 
     cout << count++ << ". " << result << endl; 
     return; 
    } 
    for (int i = 0; i < strlen(arr); i++) 
    { 
     result[index] = arr[i]; 
     _perm(arr, result, index + 1); 
    } 
} 

int compare(const void *a, const void *b) 
{ 
    return (*(char*)a - *(char*)b); 
} 



void perm(char *arr) 
{ 
    int n = strlen(arr); 
    if (n == 0) 
     return; 
    qsort(arr, n, sizeof(char), compare); 
    char *data = new char[n]; 
    _perm(arr, data, 0); 
    free(data); 
    return; 
} 



int main() 
{ 
    char arr[] = "BACD"; 
    perm(arr); 
    return 0; 
} 

Я печать выходных строк в лексикографическом отсортированном пути ,

Я имею в виду пример.3 с этой страницы.

http://www.vitutor.com/statistics/combinatorics/permutations_repetition.html

Спасибо.

Answer 1

Ваш код не печатает перестановки, но четыре ничьи из пула строк с повторением. Он будет производить комбинации 4^4 == 256, один из которых «AAAA».

Код Karnuakar, связанный с этим, даст вам перестановки строки, но без различия между множественными вхождениями определенных букв. Вам нужно некоторое средство, чтобы предотвратить повторение с той же буквой на каждом этапе рекурсии. В C++ это можно сделать с помощью набора.

В приведенном ниже примере кода используется типичная строка C, но для определения конца используется завершающий '\0'. Функции C-строки от <cstring> не нужны. Выход не сортируется, если исходная строка не была отсортирована.

#include <iostream> 
#include <algorithm> 
#include <set> 

using namespace std; 

void perm(char *str, int index = 0) 
{ 
    std::set<char> used; 

    char *p = str + index; 
    char *q = p; 

    if (*p == '\0') { 
     std::cout << str << std::endl; 
     return; 
    } 

    while (*q) { 
     if (used.find(*q) == used.end()) { 
      std::swap(*p, *q); 
      perm(str, index + 1); 
      std::swap(*p, *q); 

      used.insert(*q); 
     } 
     q++; 
    } 
} 

int main() 
{ 
    char arr[] = "AAABB"; 
    perm(arr); 

    return 0; 
} 

Это произведет 5! == 120 перестановки для "ABCDE", но только 5!/(2! 3!) == 10 уникальные перестановки для "AAABB". Он также будет создавать переходы 1260 из связанного упражнения.