시퀀스 서브셋 생성하기

6408 단어 生成子序列递归
하위 시퀀스 내보내기

비트 벡터법


비트 벡터 B[1], B[i]=1을 구성하고, i가 서브집합 A에서만 다음과 같이 귀속된다.
#include
#include
#include
#include
using namespace std;
const int maxn=100;
char A[maxn]="abcde";// 
int B[maxn];// 
void print_subset(int n,int *B,int cur)
{   //   
    // A , 
    if(cur==n)
    {// 
        for(int i=0;iif(B[i])
                {
                    printf("%c ",A[i]);
                }
        }
        printf("
"
); return ; } B[cur]=1;// cur print_subset(n,B,cur+1); B[cur]=0; print_subset(n,B,cur+1); } int main() { int n=strlen(A); print_subset(n,B,0); }

이진법

#include
#include
#include
#include
using namespace std;
const int maxn=100;
char A[maxn];// 
void print_subset(int n,int s)
{
    for(int i=0;iif(s&(1<printf("%c ",A[i]);
    }
    printf("
"
); } void subset(int n) {//n for(int i=1;i1<int main() { // cin>>A; int n=strlen(A); cout<1);// return 0; }

이 두 가지 방법은 모두 순서를 정하는 기교를 채택하여 하나의 집합 매거량 횟수를 피했다. (정렬 복합 사전 순서를 주면 각 하위 서열도 사전 순서에 부합된다) 모든 하위 서열을 사전 순서에 따라 출력하려면 출력 수조의 내용은vector 수조에 존재한다. sort를 통해 정렬하면 된다. 2진법을 예로 들면 코드는 다음과 같다.
#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn=1e5;
char A[maxn];// 

vector<string> ord;// 
void print_subset(int n,int s)
{
     string str;
    for(int i=0;iif(s&(1<void subset(int n)
{//n 
    for(int i=1;i1<int main()
{ // 
    cin>>A;
    int n=strlen(A);
    subset(n);// n
    sort(ord.begin(),ord.end());
    for(int i=0;icout<return 0;
}


좋은 웹페이지 즐겨찾기