打印所有重复数字排列的算法

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'检测结束。来自 <cstring> 的 C 字符串函数不需要。除非对原始字符串进行排序，否则不会对输出进行排序。

#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 个排列。