遞歸方法求不重復排列

[cpp]
/*******************************************************************\
輸入n個數,輸出由這n個數構成的排列,不允許出現重復的項
輸入:
3
1 1 2
輸出:
1 1 2
1 2 1
2 1 1
思路:
先手工模擬排列的過程,在第三個排列2 1 1中,我們之所以能夠寫出來,是因為
我們能發現1和2是不同的數,而計算不能,因此在存儲數據的時候數組中不能有
重復的數據,因此存儲的數比實際的數據個數要少,因此要用輔助數組記錄每個
元素的個數,這樣就能利用不含重復元素的排列算法求解.
\*******************************************************************/ 
#include<stdio.h>  
#include<string.h>  
#include<assert.h>  
 
const int maxn = 100; 
 
int num[maxn]; 
int used[maxn]; 
int ans[maxn]; 
int n, m; 
 
int readdata() 
{ 
    memset(used, 0, sizeof(used)); 
    memset(num, 0, sizeof(num)); 
    memset(ans, 0, sizeof(ans)); 
    int i = 0, j = 0; 
    if(scanf("%d", &n) == EOF || n <= 0) 
        return false; 
    int val = 0; 
    for(i=0; i<n; i++) 
    { 
        scanf("%d", &val); 
        for(j=0; j<m; j++) 
        { 
            if(num[j] == val) 
            { 
                used[j]++; 
                break; 
            } 
        } 
        if(j == m) 
        { 
            num[m] = val; 
            used[m] = 1; 
            m++; 
        } 
    } 
    return true; 
} 
 
void output() 
{ 
    for(int i=0; i<n; i++) 
    { 
        if(i < n-1) 
            printf("%d ", ans[i]); 
        else 
            printf("%d\n", ans[i]); 
    } 
} 
 
void unrepeatPerm(int dep) 
{ 
    if(dep >= n) 
    { 
        output(); 
        return; 
    } 
    for(int i=0; i<m; i++) 
    { 
        /*最好是手寫模擬遞歸過程,其中num數組中存儲的是不同的元素,這也是關鍵,*/ 
        if(used[i] > 0)/*此處是重點*/ 
        { 
            used[i]--; 
            ans[dep] = num[i];  
            unrepeatPerm(dep+1); 
            used[i]++; 
        } 
    } 
} 
 
int main() 
{ 
    while(readdata()) 
    { 
        unrepeatPerm(0); 
    } 
    return 0; 
} 

/*******************************************************************\
輸入n個數,輸出由這n個數構成的排列,不允許出現重復的項
輸入:
3
1 1 2
輸出:
1 1 2
1 2 1
2 1 1
思路:
先手工模擬排列的過程,在第三個排列2 1 1中,我們之所以能夠寫出來,是因為
我們能發現1和2是不同的數,而計算不能,因此在存儲數據的時候數組中不能有
重復的數據,因此存儲的數比實際的數據個數要少,因此要用輔助數組記錄每個
元素的個數,這樣就能利用不含重復元素的排列算法求解.
\*******************************************************************/
#include<stdio.h>
#include<string.h>
#include<assert.h>

const int maxn = 100;

int num[maxn];
int used[maxn];
int ans[maxn];
int n, m;

int readdata()
{
 memset(used, 0, sizeof(used));
 memset(num, 0, sizeof(num));
 memset(ans, 0, sizeof(ans));
 int i = 0, j = 0;
 if(scanf("%d", &n) == EOF || n <= 0)
  return false;
 int val = 0;
 for(i=0; i<n; i++)
 {
  scanf("%d", &val);
  for(j=0; j<m; j++)
  {
   if(num[j] == val)
   {
    used[j]++;
    break;
   }
  }
  if(j == m)
  {
   num[m] = val;
   used[m] = 1;
   m++;
  }
 }
 return true;
}

void output()
{
 for(int i=0; i<n; i++)
 {
  if(i < n-1)
   printf("%d ", ans[i]);
  else
   printf("%d\n", ans[i]);
 }
}

void unrepeatPerm(int dep)
{
 if(dep >= n)
 {
  output();
  return;
 }
 for(int i=0; i<m; i++)
 {
  /*最好是手寫模擬遞歸過程,其中num數組中存儲的是不同的元素,這也是關鍵,*/
  if(used[i] > 0)/*此處是重點*/
  {
   used[i]--;
   ans[dep] = num[i];
   unrepeatPerm(dep+1);
   used[i]++;
  }
 }
}

int main()
{
 while(readdata())
 {
  unrepeatPerm(0);
 }
 return 0;
}