给出一个字符集和数目n，输出该字符集在该数目下的组合。解决思路

给出一个字符集和数目n，输出该字符集在该数目下的组合。
例如：
字符集 (p, o), n = 3，所以输出是:
ppp, ppo, poo, pop, opp, opo, oop, ooo

当然也可能是这样字符集是(p, o), n = 2 （这个我想大家应该都知道怎么算了）

------解决方案--------------------
用递归方法实现，lz有兴趣可以改成用栈的。

C/C++ code



#include <stdio.h>
#include <string.h>

void print_all( char* set, int set_size, int len, int depth, char result[] )
{
    if( len <= 0 || set_size <= 0 || depth < 0 ) { return; }
    if( depth == len ) { puts( result ); return; }
    for( int i = 0; i < set_size; ++i ) { result[depth] = set[i]; print_all( set, set_size, len, depth + 1, result ); }
}

int main()
{
    char* set = "po";
    int   len = 3;

    char* result = new char[len + 1];
    result[len] = 0; 
    print_all( set, strlen( set ), len, 0, result );
    delete[] result;

    return 0;
}

------解决方案--------------------
用集合的长度做进制
如本题 {o,p} 就用2进制
n=3
所以从 0(000) 到 7(111)循环输出
把输出的字符串映射出来就行
o--0
p--1
000 --- ooo
001 --- oop
010 --- opo
011 --- opp
100 --- poo
101 --- pop
110 --- ppo
111 --- ppp
其他进制同理

------解决方案--------------------
假设字符集的个数为m个，输出的长度为n
比如：
字符集 (p, o), n = 3，
这里，m = 2; n = 3;
取值是ppp, ppo, poo, pop, opp, opo, oop, ooo

其实就是n层循环，每层循环m种取值，也就是共有m的n次方种组合情况
因为n是变量，所以无法直接写n层循环,但是可以使用递归和回溯来替代循环
2楼给出的是递归方法，下面是使用回溯的方法，执行过程完全一样

C/C++ code


#include<iostream>

using namespace std;

void func(const char *str, const int len, int num)
{
    int cur = 0;
    char *table = new char[num];
    table[0] = -1;

    while (cur >= 0)
    {
        table[cur] += 1;

        if (table[cur] < len)
        {
            if (num - 1 == cur)
            {
                int i;
                for (i = 0; i < num; ++i)
                {
                    cout<<str[table[i]];
                }
                cout<<endl;
            }
            else
            {
                cur += 1;
                table[cur] = -1;
            }
        }
        else
        {
            cur -= 1;
        }
    }

    delete[]table;
}

int main()
{    
    const char *p = "opq";
    func(p, strlen(p), 4);
    
    system("pause");
    return 0;
}

------解决方案--------------------
/**
  * c-code
  * 位运算
  */
#include <stdio.h>
#include <math.h>

void main()
{
   int n=1,count,flag;
   char *ch = "op";//字符集
   while(n!=0)//当输入n=0时结束
   {
       printf("input n:");
       scanf("%d",&n);
       count=0;
       while( count != (int)pow(2,n) )//输出的结果有2的n次方种可能，从0到2^n-1
       {
           flag = n;
           while(flag!=0)//从2^n-1到0位，逐步检测
           {
               --flag ;
               if( ( count & (int)pow(2,flag) ) == (int)pow(2,flag))
               //为1，输出'o’
                   putchar(ch[0]);
               else
               //为0，输出'p’
                   putchar(ch[1]);
           }
           count++;
           putchar(' ');
       }
       putchar('\n');
   }
}
/*
例如：n=3时
有000,001,010,011,100,101,110,111这2^3种可能，对应
有ppp,ppo,pop,poo,opp,opo,oop,ooo
*/

------解决方案--------------------

C/C++ code



char ch[] = {'p', 'o'};
int length = 2;
int num =3;

void fun2(vector<char> v, int count)
{
    if(count > num)
    {
        return;
    }
    else if(count == num)
    {
        for(int i = 0; i < v.size(); i++)
            cout<<v[i]<<" ";

        cout<<endl;
    }
    else
    {
        for(int i = 0; i < length; i++)
        {
            v.push_back(ch[i]);
            fun2(v, count+1);
            v.pop_back();
        }
    }

}

void main()
{
    vector<char> v;
    fun2(v, 0);

    getchar();
}

给出一个字符集和数目n，输出该字符集在该数目下的组合。解决思路

相关推荐