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

我成功地设计了算法来打印所有具有重复的数字的排列。但是我设计的算法存在缺陷。它只有在字符串的字符是唯一的时才起作用。用重复的数字打印所有排列的算法

有人可以帮助我在这里字符串的字符可能不是唯一的情况下延长了算法.. 到目前为止我的代码：

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

我印刷词典的排序方式输出字符串。

我指的是从这个页面的例子。

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

谢谢。

来源

2014-11-03 starkk92

hi @ stark92 ...检查以下几个方面..http：//www.geeksforgeeks.org/write-ac-program-to-print-all-permutations-of-a-given-string/ – Karunakar 2014-11-03 12:40:26

@Karunakarn纠正我，如果我错了。即使只有当字符串包含唯一的字符..只有当字符串不包含唯一字符时它将打印重复。 – starkk92 2014-11-03 13:18:26

您的代码不打印排列（对于“ABCD”应该有4！== 24），但是从池“ABCD”中抽取四个结果，其中每个字母可能会多次使用。 – 2014-11-03 13:48:03

你的代码不打印排列，但是四个从字符串池中重复绘制。它会产生4^4 == 256组合，其中之一是“AAAA”。

链接的代码Karnuakar会给你一个字符串的排列，但不区分某些字母的多次出现。您需要一些手段来防止在每个递归步骤中使用相同的字母进行递归。在C++中，这可以通过一组来完成。

下面的示例代码使用一个典型的C字符串，但使用终止来检测结束。不需要来自<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个排列。

来源

2014-11-03 14:24:58

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

回答

相关问题