用重复数字打印所有排列的算法 [英] Algorithm to print all permutations with repetition of numbers

问题描述

我已经成功地设计了算法来打印所有带有重复数字的排列.但是我设计的算法有一个缺陷.仅当字符串的字符唯一时才有效.

I have successfully designed the algorithm to print all the permutations with the repetition of numbers. But the algorithm which I have designed has a flaw. It works only if the chars of the string are unique.

如果字符串的字符可能不唯一，有人可以帮我扩展算法吗?到目前为止我的代码:

Can someone help me out in extending the algorithm for the case where chars of the string may not be unique.. My code so far :

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

我正在以字典顺序打印输出字符串.

I am printing the output strings in lexicographically sorted way.

我指的是本页中的 example.3.

I am referring to the example.3 from this page.

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

谢谢.

推荐答案

您的代码不打印排列，而是从字符串池中重复抽取四次.它将产生 4^4 == 256 个组合，其中之一是AAAA".

Your code doesn't print permutations, but four draws from the string pool with repetition. It will produce 4^4 == 256 combinations, one of which is "AAAA".

链接到的代码 Karnuakar 将为您提供字符串的排列，但不区分某些字母的多次出现.您需要一些方法来防止在每个递归步骤中使用相同的字母进行递归.在 C++ 中，这可以通过一个集合来完成.

The code Karnuakar linked to will give you permutations of a string, but without distinguishing between the multiple occurrences of certain letters. You need some means to prevent recursing with the same letter in each recursion step. In C++, this can be done with a set.

下面的示例代码使用典型的 C 字符串，但使用终止 '\0' 来检测结束.不需要 中的 C 字符串函数.除非原始字符串已排序，否则不会对输出进行排序.

The example code below uses a typical C string, but uses the terminating '\0' to detect the end. The C-string functions from <cstring> are not needed. The output will not be sorted unless the original string was sorted.

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

This will produce 5! == 120 permutations for "ABCDE", but only 5! / (2! 3!) == 10 unique permutations for "AAABB". It will also create the 1260 permutations from the linked exercise.

这篇关于用重复数字打印所有排列的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！