permutations.

Whether you're a newbie or an experienced programmer, any questions, help, or just talk of any language will be welcomed here.

Moderator: Coders of Rage

Post Reply
User avatar
avansc
Respected Programmer
Respected Programmer
Posts: 1708
Joined: Sun Nov 02, 2008 6:29 pm

permutations.

Post by avansc »

hey, i wrote a program like this a while back. thought i had post it but seems as though i might not have. anyways. hope someone finds it useful.
note: there are some semi-advanced pointer usage/arithmetic going on, but nothing to bad. let me know if you need help understanding it.

Code: Select all

/*
 *  main.cpp
 *  perm
 *
 *  Created by avansc on 10/15/09.
 *  Copyright 2009 Andre van Schalkwyk. All rights reserved.
 *
 */

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

char *permv;
char **permt;
int length;
int size;

void printPerm(char **perm);
void permute(char **perm);
bool done(char **perm);

void printPerm(char **perm)
{
	while(*perm)
	{
		printf("%c",**perm);
		perm++;
	}
	printf("\n");
}

void permute(char **perm)
{
	if(*perm == &permv[length-1])
	{
		*perm = permv;
		permute(++perm);
	}else{
		(*perm)++;
	}
}

bool done(char **perm)
{
	while(*perm)
	{
		if(**perm != permv[length-1])
		{
			return false;
		}
		perm++;
	}

	return true;
}

int main (int argc, char * const argv[])
{
	if(argc != 3)
	{
		printf("\nUSAGE : perm n c\n\n\tn = length of permutation.\n\tc = characters to permutatt.\n\n");
		return 0;
	}
	
	size = atoi(argv[1]);
	length = strlen(argv[2]);
	
	permv = (char*)malloc(sizeof(char)*length);
	permt = (char**)malloc(sizeof(char*)*size);
	
	permv[length] = NULL;
	permt[size] = NULL;
	
	for(int a = 0;a < length;a++)
	{
		permv[a] = argv[2][a];
	}
	
	for(int a = 0;a < size;a++)
	{
		permt[a] = (char*)malloc(sizeof(char)*length);
		permt[a] = permv;
		permt[a][length] = NULL;
	}
		
	while(!done(permt))
	{
		printPerm(permt);
		permute(permt);
	}
	printPerm(permt);
	
	free(permv);
	free(permt);
	
	return 0;
}
EDIT: i didnt check for any bugs. ran it and it seemed fine. so if you spot something let me know.
Some person, "I have a black belt in karate"
Dad, "Yea well I have a fan belt in street fighting"
Post Reply