全排列和组合问题

#include "stdafx.h"
#include <string.h>

#define MAXLEN 128

bool flags[MAXLEN];
char output[MAXLEN];

/* 全排列：
 * n个字符全排列，轮流将数组中每个数字放在第一位上，
 * 然后调用剩下n-1个数字的全排列。以此形成递归。
 * @parame every 必须从0开始
 */
void permutation(char input[], int len, int every)
{
    int i;
    for(i = 0; i < len; ++i)
    {
        if(false == flags[i])
        {
            output[every] = input[i];
            if(every == len - 1) //the last char has checked
            {
                output[len] = '\0';
                printf("%s\n", output);
                return;
            }
            else
            {
                flags[i] = true;
                permutation(input, len, every+1);
                flags[i] = false;
            }
        }
    }
    return;
}

// another same way
void doPermutation(char input[], int len, int every)
{
    int i;

    if(every == len) // make sure data[len-1] was handled below
    {
        printf("%s\n", output);
        return;
    }
    for(i = 0; i < len; ++i)
    {
        if(false == flags[i])
        {
            flags[i] = true;
            output[every] = input[i];
            if(every == len - 1)
            {
                output[len] = '\0';
            }
            doPermutation(input, len, every+1);
            flags[i] = false;

        }
    }
}

/* 组合：
 * 比如输入1，2，3，4长度为len，输出所有长度为k(k<len)的组合，
 * 比如k=3时，有123,124,134,234，共四种。
*/
/* 在n个元素中取m个的组合，对每一个元素可以将此问题划分为两个子问题：
 * 1）把该元素放入组合中：在剩下的n-1个可选数据求得可能的m-1个元素的组合
 * 2）不把该元素放到组合中：在剩下的n-1个可选数据求得可能的m个元素的组合
 * @parame cur, pos 必须从0开始。
 */
void combination(char input[], int k, int cur, int pos )
{
    int i;
    if(0 == k)
    {
        for(i = 0; i < pos; ++i)
            printf("%c", output[i]);
        printf("\n");
        return;
    }
    if('\0' == input[cur])
        return;

    output[pos] = input[cur];
    combination(input, k-1, cur+1, pos+1);
    pos--;
    combination(input, k, cur+1, pos+1);
}

// another same way
void doCombination(char input[], int len, int k, int cur, int pos )
{
    if(cur >= len) return;
    if(0 == k) return;

    output[pos] = input[cur];
    if(1 == k)
    {
        output[pos+1] = '\0';
        printf("%s\n", output);
    }
    doCombination(input, len, k-1, cur+1, pos+1);
    pos--;
    doCombination(input, len, k, cur+1, pos+1);
}

int _tmain(int argc, _TCHAR* argv[])
{
    char input[] = "1234";
    int i,k = 3;

    int len;
    len = strlen(input);
    memset(flags, false, MAXLEN);

    //permutation(input, len, 0);
    //doPermutation(input, len, 0);
    combination(input, k, 0, 0);
    //doCombination(input, len, k, 0, 0);
    printf("-------------------------\n");
    //所有组合
    for(i=1; i<len; ++i)
        combination(input, i, 0, 0);

    return 0;
}