Optimizing Permutation Algorithm

[memcpy]

I was wondering if anybody could help me optimize my algorithm that calculates permutations of specified length, using a specified character set. I've tested it and it works for everything I've tried, including different character sets, and different min/max lengths (provided max > min and both nonzero).

int permutation (char **res, char *chrset, int min_len, int max_len)
{
	char *tmp;
	int pow_count, pos, set_len, count, permc, perm_per_len, size_set, wordlen;


	count = 0;
	size_set = 0;
	
	while (chrset[size_set])
		size_set++;
	
	for (set_len = min_len; set_len <= max_len; set_len++) {
		perm_per_len = 1;
		pow_count = set_len;
		while (pow_count--) {
			perm_per_len *= size_set;
		}
		count += perm_per_len;
		for (pow_count = 0; pow_count < perm_per_len; pow_count++) {
			permc = 1;
			tmp = *res++;
			for (wordlen = 0; wordlen < set_len; wordlen++) {
				pos = (pow_count / permc) % size_set;
				*tmp++ = chrset[pos];
				permc *= size_set;
			} 
		}
	}
	
	return count;
}

Although it functions correctly, there is most likely a way that I'm missing that could be used to optimize it. For example, the inner loop calculates the value of "permc" every time it is run.

[oogabooga]

It would be nice if you would post a runnable program with a main.

[memcpy]

void print_columns (size_t numw, char **c1, char **c2, char **c3)
{
	while (numw--) {
		if (c1 && **c1) {
			printf("| %10s |", *(c1++));
		} else {
			printf("|            |");
		}
		
		if (c2 && **c2) {
			printf("| %10s |", *(c2++));
		} else {
			printf("|            |");
		}
		
		if (c3 && **c3) {
			printf("| %10s |", *(c3++));
		} else {
			printf("|            |");
		}
		
		printf("\n");
	}
}


char ** alloc_permutation_array (size_t lenw, size_t numw)
{
	int i;
	char **res;
	
	res = calloc(sizeof(char *), numw);
	for (i = 0; i < numw; i++) 
		res[i] = calloc(1, lenw);


	return res;
}


void free_permutation_array (size_t numw, char **data)
{
	int i;
	
	for (i = 0; i < numw; i++) 
		free(data[i]);
	
	free(data);
}


int main (void)
{
	char **r1 = alloc_permutation_array(3, 50);
	char **r2 = alloc_permutation_array(4, 100);
	char **r3 = alloc_permutation_array(4, 100);


	int len;


	len = permutation (r1, "abc", 1, 3);
	printf("len=1-3 chrset=3 | %d perm.\n", len);
	
	len = permutation (r2, "abc", 3, 3);
	printf("len=3-3 chrset=3 | %d perm.\n", len);
	
	len = permutation (r3, "a", 1, 9);
	printf("len=1-9 chrset=1 | %d perm.\n", len);
	
	print_columns(100, r1, r2, r3);
	
	free_permutation_array(50, r1);
	free_permutation_array(100, r2);
	free_permutation_array(100, r3);
}

Testing framework that I was using earlier

[Subsonics]

I'm probably missing something here but you can calculate permutation like this:

size_t permutations(char *chrset, size_t range) {
    size_t len = strlen(chrset);
    return pow(range, len);
}

[phantomotap]

O_o

He isn't calculating permutations. He is generating permutations. I agree, his question is misleading.

Anyway, I admit, I only looked at your code for a minute, but from what I glanced you've missed an opportunity in the form of `min_len == max_len'.

That said, I don't think the code is correct. I only looked for minute, but it seems to me you aren't checking things relevant to `min_len' and `max_len' enough for this to be correct. Of course, that may just be because you are assuming too much and not calculating enough. (One such case is `r3' from the testbed which doesn't have nearly enough memory allocated for the algorithm.)

And that said, you can derived the number of permutations without exhaustively generating them. You may want to split off such a function so that you may allocate a more reasonable approximation of how much memory you need allowing you to not rely on assumptions.

And that said, my thinky thoughts aren't organized today, a more reasonable approach to this concept is using a form which can be called iteratively (`while(next_permutation(???))') or at least providing a callback through which the client can store the results however they choose. This can most effectively done by a single appropriately sized buffer.

Soma

[KCfromNC]

What are you trying to optimize for? Speed? Run time memory use? Code size? Cache-friendliness? Multi-threading improvements? And how much faster / smaller or whatever does it need to be?

Have you profiled the code yet? You're almost certainly spending most of your time in printf(). Is that part of the final application or just test code?

Generally when you want to test permutations of something, the problem isn't the speed of generating them. The problem is that the number of the multiplies very quickly so no matter how quickly you process each one, there's just way too many to calculate&test practically. Typically the best optimization here is to find a way to reduce the number of permutations you need to process rather than generate them more quickly. But that all depends on what you're trying to do.