7.2 枚举排列

#include<stdio.h>
int A[100];

// 输出1~n的全排列
void print_permutation(int n, int* A, int cur) {
  int i, j;
  if(cur == n) { // 递归边界
    for(i = 0; i < n; i++) printf("%d ", A[i]);
    printf("\n");
  } else for(i = 1; i <= n; i++) { // 尝试在A[cur]中填各种整数i
    int ok = 1;
    for(j = 0; j < cur; j++)
      if(A[j] == i) ok = 0; // 如果i已经在A[0]~A[cur-1]出现过，则不能再选
    if(ok) {
      A[cur] = i;
      print_permutation(n, A, cur+1); // 递归调用
    }
  }
}

int main() {
  print_permutation(4, A, 0);
  return 0;
}

#include<cstdio> 
#include<cstring>
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
        
const int N=20;
int P[N];   
int A[N];   
            
void perm(int n, int *A, int cur)
{   
    if(n==cur)
    {
        for(int i=0;i<n;i++)
            printf("%d ", A[i]);
        printf("\n");
    }
    else for(int i=0;i<n;i++)
    {
        int ok=1;
        for(int j=0;j<cur;j++)
        {
            if(A[j]==P[i])
            {
                ok=0;
                break;
            }
        }
        if(ok)
        {
            A[cur]=P[i];
            perm(n, A, cur+1);
        }
    }
}

//生成可重集的排列（错误的）
void perm2(int n, int *A, int cur)
{
    if(n==cur)
    {
        for(int i=0;i<n;i++)
            printf("%d ", A[i]);
        printf("\n");
    }
    else for(int i=0;i<n;i++)
    {
        int c1=0, c2=0;
        for(int j=0;j<cur;j++) if(A[j]==P[i]) c1++;
        for(int j=0;j<n;j++) if(P[j]==P[i]) c2++;
        if(c1<c2)
        {
            //printf("%d %d\n", c1, c2);
            A[cur]=P[i];
            perm2(n, A, cur+1);
        }
    }
}

//生成可重集的排列（修正后）
// P 需要排序过
// 输出数组P中元素的全排列。数组P中可能有重复元素
void perm3(int n, int *A, int cur)
{
    if(n==cur)
    {
        for(int i=0;i<n;i++)
            printf("%d ", A[i]);
        printf("\n");
    }
    else for(int i=0;i<n;i++)
    if(!i || P[i]!=P[i-1])
    {
        int c1=0, c2=0;
        for(int j=0;j<cur;j++) if(A[j]==P[i]) c1++;
        for(int j=0;j<n;j++) if(P[j]==P[i]) c2++;
        if(c1<c2)
        {
            //printf("%d %d\n", c1, c2);
            A[cur]=P[i];
            perm3(n, A, cur+1);
        }
    }
}
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>P[i];

    printf("perm\n");
    perm(n, A, 0);

    printf("perm2\n");
    perm2(n, A, 0);

    printf("perm3\n");
    perm3(n, A, 0);

    return 0;
}

#include<cstdio>
#include<algorithm>
using namespace std;

/*
 函数实现原理如下：
    在当前序列中，从尾端往前寻找两个相邻元素，前一个记为*i，后一个记为*ii，并且满足*i < *ii。然后再从尾端寻找另一个元素*j，如果满足*i < *j，即将第i个元素与第j个元素对调，并将第ii个元素之后（包括ii）的所有元素颠倒排序，即求出下一个序列了。
 */
bool next_perm(int *first, int *last)
{
    //空区间
    if(first==last) return false;
    int *i=first;
    //只有一个
    if(++i==last) return false;
    i=last; --i;
    while(1) {
        int *ii=i;
        --i;
        //锁定两个相邻元素
        if(*i<*ii) {//如果前一个比后一个小
            int *j=last;
            while(!(*i<*--j));//从尾向前找,直到找到一个比*i大的元素
            printf("swap %d %d\n", *i, *j);
            iter_swap(i, j);//交换i,j
            reverse(ii, last);//将从ii开始之后的元素逆序重排
            return true;
        }
        if(i==first)//到最前面了,没有更大的序列了
        {
            reverse(first, last);//全部逆序排列,变成最小的序列
            return false;
        }
    }
}

int main() {
  int n, p[10];
  scanf("%d", &n);
  for(int i = 0; i < n; i++) scanf("%d", &p[i]);
  sort(p, p+n); // 排序，得到p的最小排列
  do {
    for(int i = 0; i < n; i++) printf("%d ", p[i]); // 输出排列p
    printf("\n");
  //} while(next_permutation(p, p+n)); // 求下一个排列
  } while(next_perm(p, p+n)); // 求下一个排列
//最后会输出最小序列
    for(int i = 0; i < n; i++) printf("%d ", p[i]); // 输出排列p
  return 0;
}