递归求全排列

num: 需要排列的数组

res: 排列得出的结果

used: 记录是否选过

#include <iostream>
#define MAXN 100
using namespace std;

int n,k;//从n个数里面选择k个进行全排列
int num[MAXN];
int res[MAXN];
bool used[MAXN];

void permutation(int cur)
{
   if(cur > k)
  {
       for(int i = 1; i <= k; i++)
           cout << res[i];
       cout << endl;
  }
   else
       for(int i = 1; i <= n; i++)
      {
           if(!used[i])
          {
               res[cur] = num[i];
               used[i] = true;
               permutation(cur + 1);
               used[i] = false;
          }
      }
}

int main()
{
   cin >> n >> k;
   for(int i = 1; i <= n; i++)
       cin >> num[i];
   permutation(1);
   return 0;
}

递归求全组合

num: 需要排列的数组

res: 排列得出的结果

lastPosition: 记录这一次选择的数排在第几号位置,下一次从这个位置的下一个位置开始选择

#include <iostream>
#define MAXN 100
using namespace std;

int n,k;
int num[MAXN];
int res[MAXN];
int lastPosition[MAXN];

void combination(int cur)
{
   if(cur > k)
  {
       for(int i = 1; i <= k; i++)
           cout << res[i];
       cout << endl;
  }
   else
       for(int i = lastPosition[cur - 1] + 1; i <= n; i++)
      {
           res[cur] = num[i];
           lastPosition[cur] = i;
           combination(cur + 1);
      }
}

int main()
{
   cin >> n >> k;
   for(int i = 1; i <= n; i++)
       cin >> num[i];
   combination(1);
   return 0;
}

next_permutation 与 pre_permutation

下一个全排列 与 上一个全排列

#include <iostream>
#include <algorithm>
#define MAXN 100
using namespace std;

int n;
int num[MAXN];

int cmp(int a, int b)
{
   return a > b;
}

int main()
{
   cin >> n;
   for(int i = 1; i <= n; i++)
       cin >> num[i];
   sort(num + 1, num + n + 1);
   while(next_permutation(num + 1, num + 1 + n))
  {
       for(int i = 1; i <= n; i++)
           cout << num[i];
       cout << endl;
  }
   sort(num + 1, num + n + 1, cmp);
   while(prev_permutation(num + 1, num + 1 + n))
  {
       for(int i = 1; i <= n; i++)
           cout << num[i];
       cout << endl;
  }
   return 0;
}
分类: c/c++

发表评论

电子邮件地址不会被公开。 必填项已用*标注