从含有m个元素的集合中任选n个的算法

问题：从含有M个元素的集合中任选n个的排列组合。

思路：利用M进制的数组来表示

源程序如下（在C-Free 3.5中测试）

/*-----------------------------------------------------------------------
                     Author : RainFly(傲月寒星)
                     3-25-05
                    Describe:关于幂集的一个算法，也是从m个元素中任选n个
                             的算法.
                    if you have other ideas,please email me:[email protected]
                     Test in C-Free 3.5
------------------------------------------------------------------------*/

#include <iostream>
#include <vector>
#include <stdlib.h>
#include <string>
using namespace std;
void ssort(int n,int str[],int m,int N);
int main()
{
        int i,N,j=0,m,count,temp,i_begin=1,i_end,M,flag=0;
        vector <string> iInt;
        string ss;
        cout<<"How many elements do you want the set include:";
        cin>>M;

        cout<<"Please input "<<M<<"elements:";
        int * str=new int[M];
        vector <string>::iterator vi;
        for (i = 0; i <M; i++)
       {
           cin>>ss;
           iInt.push_back(ss);
       }

        cout<<endl;
        cout<<"The elments of this set is:";
        for (vi = iInt.begin(); vi != iInt.end(); vi++)
              cout<<*vi<<" ";
        cout<<endl;
 /*
 output n elements
 */
        cout<<"Please input a number(0~"<<M<<"):";
        cin>>N;
    //insure the scope of i
       for(i=0;i<N-2;i++)
        i_begin=i_begin*M;
        i_end=i_begin*M*M;
       if(i_begin==1)
        i_begin=0;
       if(N==1)
        i_end=M;

    for(i=i_begin;i<i_end;i++)
    {
       flag=0;
       ssort(i,str,M,N);
       for(j=0;j<N-1;j++)
       for(m=j+1;m<N;m++)
       if(str[j]>=str[m])
       flag=1;
       if(flag)
       continue;
      cout<<"<";
          for(j=0;j<N;j++)
        {
            if(j!=N-1)
            cout<<iInt[str[j]]<<",";
            else
            cout<<iInt[str[j]];
            }
        cout<<">";

       }

  delete [] str;

 return 0;
}

void ssort(int n,int str[],int m,int N)
{
    int i=0,count=0,temp;
    while(n>=0)
    {
     if(n<m)
     {
        str[i]=n;
        count++;
        break;
     }
     str[i]=n%m;
     n=n/m;
     count++;
     i++;
    }
    //sort this array
    if(N>1&&count<N)
    str[i+1]=0;
    for(i=0;i<N/2;i++)
    {
       temp=str[i];
       str[i]=str[N-i-1];
       str[N-i-1]=temp;
    }
}

Example:

How many elements do you want the set include:5
Please input 5 elements:a1 a2 a3 a4 a5
The elments of this set is:a1 a2 a3 a4 a5
Please input a number(0~5):2
<a1,a2><a1,a3><a1,a4><a1,a5><a2,a3><a2,a4><a2,a5><a3,a4><a3,a5><a4,a5>

本文地址：http://com.8s8s.com/it/it22688.htm