【csp-3】排列与组合

组合：n个数选m个数，从小到大第k个选择是什么

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<bits/stdc++.h>
using namespace std;
int flag,n,m,a[21],vis[21],k,sum;

void dfs(int now,int last){
    if(flag==1) return ;
    if(now==m+1){
        sum++;
        if(sum==k){
            flag=1; 
            for(int i=1;i<=m;i++)
                printf("%d ",a[i]);
            printf("\n");
            return;
        }
    }
    for(int i=last;i<=n;i++){
        if(vis[i]==1) continue;
        vis[i]=1;
        a[now]=i;
        dfs(now+1,i+1);
        vis[i]=0;
    }
}

int main(){
    //freopen("zuhe.in","r",stdin);
    //freopen("zuhe.out","w",stdout);
    scanf("%d %d %d",&n,&m,&k);
    dfs(1,1); 
    return 0;
}

排列：n个数，第m大个全排列

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<bits/stdc++.h>
using namespace std;
int flag,n,m,k;
int a[1002],vis[1002];
void dfs(int now){
    if(flag==1) return ; 
    if(now==n+1){
        k++;
        if(k==m){
            flag=1;
            for(int i=1;i<=n;i++)
                printf("%d ",a[i]);
            return;
        }
    }
    for(int i=1;i<=n;i++){
        if(vis[i]==1) continue;
        vis[i]=1;
        a[now]=i;
        dfs(now+1);
        vis[i]=0;
    }
}

int main(){
    freopen("pailie.in","r",stdin);
    freopen("pailie.out","w",stdout);
    scanf("%d %d",&n,&m);
    dfs(1);
    return 0;
}

另一种方法求解：

// luogu-judger-enable-o2
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
typedef long long ll;
using namespace std;
int n,a[18];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        { a[i]=i; printf("    %d",i); } 
    while(next_permutation(a+1,a+1+n)){
          printf("\n");
          for(int i=1;i<=n;i++) 
              printf("    %d",a[i]);
    }
    return 0;
}