Permutation and Combination…again.

These here are updated versions to my previous attempts at listing permutations and combinations, and these are a lot shorter than those and easier to understand. Even though it is in C++, converting to pure C is not a huge endevour either.

Combinations

#include <iostream>
#include <string>
#include <cstdio>
#define MAX 100
using namespace std;
int count;
int r;
void comb(char *arr, int i, int j, const char *line){
    if (j<r) {
        for (int x=i;x<count;x++){
            char newline[MAX];
            sprintf(newline, "%d %s",x+1, line );
            comb(arr, x+1, j+1, newline);        
        }
    } else {
        cout<<line<<endl;
    }
}

int main(){
    cin>>count>>r;
    char bits[count];

    for (int i=0;i<count;i++) bits[i] = 0;
    comb(bits,0,0,"");
    return 0;
}

Permutations

#include <iostream>
#include <string>
#include <cstdio>
#define MAX 100
using namespace std;
int count;

void perm(char *arr, int i, const char *line){

    if (i<count) {
        for (int x=0;x<count;x++){
            if (arr[x] != 1) {
                char newline[MAX];
                sprintf(newline, "%d %s",x+1, line );

                arr[x] = 1;
                perm(arr, i+1, newline);
                arr[x] = 0;
            }
        }
    } else {
        cout<<line<<endl;
    }
}

int main(){
    cin>>count;
    char bits[count];

    for (int i=0;i<count;i++) bits[i] = 0;
    perm(bits,0,"");
    return 0;
}

Combinations and Permutations: UPDATE

This version brings updates to how it finds out all permutations, in the older version it used to search through the so far generated nodes backwards and pick a number that wasn’t used(dumb by all means, but got the job done). But when looked at it from a different perspective, why not have something like a dictionary? When used, mark it. But again there would be a problem of copying the whole array for the next call of the recursive method: it feels like we’d have to copy the whole thing but it doesn’t need to. What I did was to remove the change done after the recursive call, it was not a planned move but it should work. There was no reason not to. Done.

Download the source

Routines for listing all permutations and combinations

It’s recursive, it’s coded on C, it has dynamic memory allocation(and it frees it after using!). Check it out,

#include <stdio.h>
#include <stdlib.h>

#define TYPE unsigned char

int n, r, out_count=0;

typedef struct st_node {
    TYPE data;
    struct st_node *parent;
}node;

node *new_node(node *p){
    node *new = malloc(sizeof(node));
    new->parent = p;
    return new;
}
void back_track(node *child){
    while (child != NULL){
        printf(" %d", child->data);
        child = child->parent;
    }
    printf("n");
    out_count++;
}
int check_used(node *child, TYPE a){
    while (child != NULL){
        if (a == child->data)
            return 1;
        child = child->parent;
    }
    return 0;
}
void perm( int i, node *parent, int count){
    int j;
    if (count == r){
        back_track(parent);
        return;
    }

    for (j=0;j<n;j++){
        if (check_used(parent,(TYPE) j) == 1)
            continue;
        node *child = new_node(parent);
        child->data=j;

        perm( j, child, count + 1);
        free(child);
    }
}

void comb( int i, node *parent, int count){
    int j;
    if (count == r){
        back_track(parent);
        return;
    }

    for (j=i+1;j<=n;j++){
        if (n-j < r-count-1)
            break;
        node *child = new_node(parent);
        child->data=j-1;

        comb( j, child, count + 1);
        free(child);
    }
}
int main(){
    scanf("%d",&n);
    scanf("%d",&r);

    perm(0,NULL,0);
    //comb(0,NULL,0);
    printf("Count: %dn",out_count);
    return 0;
}