《算法竞赛入门经典》第七章学习笔记

枚举排列

生成1~n的排列

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

void print_permutation(int n, int A[], int cur){ // cur == current 
    if(cur == n) 
    { 
        for(int i=0; i<n; i++) printf("%d ",A[i]); 
        putchar('\n'); 
    } 
    else for(int i=1; i<=n; i++)
    { 
        int ok = 1; 
        for (int j=0; j<cur; j++) 
        if(A[j] == i) {ok = 0; break;} 
        if(ok) 
        { 
            A[cur] = i; 
            print_permutation(n, A, cur+1); 
        } 
    } 
}

int main()
{
    int n, A[50];
    n = 5;
    print_permutation(n, A, 0);
    return 0;
}

生成可重集的排列

void print_permutation(int n, int P[], int A[], int cur)
{ 
    if(cur == n) 
    { 
        for(int i=0; i<n; i++) printf("%d ",A[i]); 
        putchar('\n'); 
    } 
    else for(int i=0; i<n; i++) 
    if(!i || P[i] != P[i-1]) 
    {   //if的意思: 对于重复元素（排序后已经挨在一起），只试它们中的第一个，其余跳过 
        //P[0]是必然要试的：若有多个等于P[0]的值，P[0]必为第一个(0-1=-1不在数组下表 范围内)；
        //若只有一个，更理所当然地要试P[0]。(!i即为i==0) 
        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) 
        { 
            A[cur] = P[i]; 
            print_permutation(n, P, A, cur+1); 
        } 
    } 
}


int main()
{
    int n, A[50],P[50];
    n = 5;
    for(int i=0;i<5;i++) P[i]=i+1;
    print_permutation(n, P, A, 0);
    return 0;
}

利用STL生成排列

#include <algorithm>
#include <cstdio>

using namespace std;
int main()
{
    int n, p[10];
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&p[i]);
    sort(p,p+n);
    do
    {
        for(int i=0;i<n;i++)    printf("%d",p[i]);
        printf("\n");
    }while(next_permutation(p, p+n));
    return 0;
}

子集生成

增量构造法

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

void print_subset(int n, int A[], int cur)
{
    for(int i = 0; i<cur; i++) printf("%d", A[i]);
    printf("\n");
    int s = cur ? A[cur-1]+1 : 0;
    for(int i = s; i<n; i++)
    {
        A[cur] =i;
        print_subset(n, A, cur+1);
    }
}

int main()
{
    int n, A[50];
    n = 5;
    print_subset(n, A, 0);
}

位向量法

#include <cstdio>

using namespace std;

void print_subset(int n, int* B, int cur)
{
    if(cur == n)
    {
        for(int i=0; i<cur; i++)
            if(B[i]) printf("%d", i);
        printf("\n");
        return;
    }
    B[cur] = 1;
    print_subset(n, B, cur+1);
    B[cur] = 0;
    print_subset(n, B, cur+1);
}

int main()
{
    int n, P[50];
    n = 5;
    print_subset(n, P, 0);
}

二进制法

#include <cstdio>
#include <algorithm>

using namespace std;

void print_subset(int n, int s)
{
    for(int i =0; i<n; i++)
        if(s&(1<<i)) printf("%d", i);
    printf("\n");
}

int main()
{
    int n;
    n=5;
    for(int i=0; i< (1<<n); i++)
        print_subset(n, i);
}