Friday, March 22, 2013

Subset, Combination and Permutation (Recursion)



#define MAX_K 100 

void subset_rec(
    const char *cont, 
    const size_t start, 
    const size_t n,
    char *res, 
    const size_t last)  
{
    size_t i;

    // print (res, last);
    for (i = start; i < n; i++) {
        res[last] = cont[i];
        subset_rec(cont, i+1, n, res, last+1);
    }
}

void subset(const char *content, const size_t n) {
    char *result;
    result = (char*)malloc(MAX_K * sizeof(char));
    subset_rec(content, 0, n, result, 0);
    free(result);
    result = NULL;
}

void comb_rec(
    const char *cont,       // pointer to combination's content
    const size_t start,     // starting index of the content
    const size_t n,         // n of C(n,k)
    const size_t k,         // k of C(n,k)
    char *res,              // pointer to one combination generated so far
    const size_t last)      // length of the result
{
    size_t i;

    if (k == 0) {
        // print (res, last);
    } else {
        for (i = start; i < n; i++) {
            res[last] = cont[i];
            comb_rec(cont, i+1, n, k-1, res, last+1);
        }
    }
}

void combination(const char *content, const size_t n, const size_t k) 
{
    char *result;
    if (k > n || k == 0 || n == 0)  return;
    result = (char*)malloc(MAX_K * sizeof(char));
    comb_rec(content, 0, n, k, result, 0);
    free(result);
    result = NULL;
}

void perm_rec(
    char *cont, 
    const size_t n, 
    const size_t k, 
    char *res, 
    const size_t last)  
{
    size_t i;
    char t;

    if (k == 0) {
        // print (res, last);
    } else {
        for (i = 0; i < n; i++) {
            t = cont[i];
            res[last] = t;                          // A B C D
            memmove(cont+i, cont+i+1, n-i-1);       // A C D
            perm_rec(cont, n-1, k-1, res, last+1); 
            memmove(cont+i+1, cont+i, n-i-1);       // A A C D
            cont[i] = t;                            // A B C D
        }
    }
}

void permutation(const char *content, const size_t n, const size_t k) 
{
    char *result;
    if (k > n || k == 0 || n == 0)  return;
    result = (char*)malloc(MAX_K * sizeof(char));
    perm_rec((char*)content, n, k, result, 0);
    free(result);
    result = NULL;
} 
 

For the permutation of set that contains duplicates, the solution can be found here:
https://oj.leetcode.com/discuss/16264/a-simple-recursion-solution-c

No comments:

Post a Comment

(Coding && Eating) || Sleeping