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;
}
Advertisements

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