用重複的數字打印所有排列的算法

我成功地設計了算法來打印所有具有重複的數字的排列。但是我設計的算法存在缺陷。它只有在字符串的字符是唯一的時才起作用。用重複的數字打印所有排列的算法

有人可以幫助我在這裏字符串的字符可能不是唯一的情況下延長了算法.. 到目前爲止我的代碼：

#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

用重複的數字打印所有排列的算法

回答

相關問題