排列组合与回溯算法

相关问题

UVA 524 Prime Ring Problem

可重排列：就是从任意n个元素中，取r个可重复的元素的排列。例如，对于集合OR={1,1,2,2}, n = |OR| = 4, r = 2,那么排列如下：

{1,1}; {1,2}; {1,2}; {1,1}; {1,2}; {1,2}; {2,1}; {2,1}; {2,2}; {2,1}; {2,1}; {2,2}

则可重排列是：

{1,1}; {1,2}; {2,1}; {2,2}.

算法如下：

#define FREE -1int n, r;/*使元素有序*/int E[MaxN] = {0,0,1,1,1}; int P[MaxN];char used[MaxN]; void permute(int pos){int i;/*如果已选了r个元素了，则打印它们*/    if (pos==r)  {        for (i=0; i<r; i++)            cout << P[i];        cout << endl;        return;    }/*标记下我们排列中的以前的元素表明是不存在的*/    P[pos] = FREE;    for (i=0; i<n; i++)/*如果第I个元素没有用过，并且与先前的不同*/        if (!used[i] && E[i]!=P[pos]) {/*使用这个元素*/            used[i]++;/*选择现在元素的位置*/            P[pos] = E[i];/*递归搜索*/            permute(pos+1);/*恢复递归前的值*/            used[i]--;        }}

相关习题

UVA 10098 Generating Fast, Sorted Permutations

组合：从n个不同元素中取r个不重复的元素组成一个子集，而不考虑其元素的顺序，称为从n个中取r个的无重组合，例如OR = {1,2,3,4}, n = 4, r = 3则无重组合为：

{1,2,3}; {1,2,4}; {1,3,4}; {2,3,4}.

算法如下：

int n, r;int C[5];char used[5]; void combine(int pos, int h){int i;/*如果已选了r个元素了，则打印它们*/    if (pos==r) {        for (i=0; i<r; i++)            cout<< C[i];        cout<< endl;        return;    }    for (i=h; i<=n-r+pos; i++) /*对于所有未用的元素*/        if (!used[i]) {/*把它放置在组合中*/            C[pos] = i;/*使用该元素*/ used[i]++;/*搜索第i+1个元素*/     combine(pos+1,i+1);/*恢复递归前的值*/ used[i]--;        }}

相关问题：

Ural 1034 Queens in peaceful position

可重组合：类似于可重排列。

[例] 给出空间中给定n(n<10)个点，画一条简单路径，包括所有的点，使得路径最短。

解:这是一个旅行售货员问题TSP。这是一个NP问题，其实就是一个排列选取问题。

算法如下：

int  n, r;char used[MaxN];int  p[MaxN];double min; void permute(int pos, double dist){int i;    if (pos==n) {        if (dist < min) min = dist;        return;    }    for (i=0; i<n; i++)        if (!used[i]) {            used[i]++;            p[pos] = i;           if (dist + cost(point[p[pos-1]], point[p[pos]]) < min)                permute(pos+1, dist + cost(point[p[pos-1]], point[p[pos]])); used[i]--;        }}

[例]对于0和1的所有排列，从中同时选取r个元素使得0和1的数量不同。

解 这道题很简单，其实就是从0到2^r的二元表示。

算法如下：

void dfs(int pos){   if (pos == r)   {       for (i=0; i<r; i++) cout<<p[i];       cout<<endl;       return;   }   p[pos] = 0;   dfs(pos+1);   p[pos] = 1;   dfs(pos+1);}

相关问题：

Ural

1005 Stone pile

1060 Flip Game

1152 The False Mirrors

[例]找最大团问题。

一个图的团，就是包括了图的所有点的子图，并且是连通的。也就是说，一个子图包含了n个顶点和n*(n-1)/2条边，找最大团问题是一个NP问题。算法如下：

#define MaxN 50 int  n, max;int  path[MaxN][MaxN];int  inClique[MaxN]; void dfs(int inGraph[]){int i, j;int Graph[MaxN]; if ( inClique[0]+inGraph[0]<=max ) return;if ( inClique[0]>max ) max=inClique[0]; /*对于图中的所有点*/    for (i=1; i<=inGraph[0]; i++)    {/*把节点放置到团中*/        ++inClique[0]; inClique[inClique[0]]=inGraph[i];/*生成一个新的子图*/ Graph[0]=0; for (j=i+1; j<=inGraph[0]; j++)     if (path[inGraph[i]][inGraph[j]] )          Graph[++Graph[0]]=inGraph[j];     dfs(Graph);/*从团中删除节点*/        --inClique[0];}}int main(){int inGraph[MaxN];int i, j;  cin >>n;  while (n > 0)  {        for (i=0; i<n; i++) for (j=0; j<n; j++)     cin >>path[i][j];        max = 1;/*初始化*/        inClique[0]= 0;        inGraph[0] = n; for (i=0; i<n; i++) inGraph[i+1]=i;        dfs(inGraph);        cout<<max<<endl;        cin >>n;  }  return 0;}