Skip to content

Instantly share code, notes, and snippets.

@newfurniturey
Created June 15, 2014 12:49
Show Gist options
  • Save newfurniturey/a281d0366ccb594aec33 to your computer and use it in GitHub Desktop.
Save newfurniturey/a281d0366ccb594aec33 to your computer and use it in GitHub Desktop.
C - Alphabet permutations without arrays or recursion
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <math.h>
int main() {
int string_len = 4;
char alphabet[] = "abc";
int alphabet_len = ((sizeof(alphabet) / sizeof(alphabet[0])) - 1);
// null-initialize a char-array to hold a max-length of `string_len` characters
char *current_key = (char *)calloc((string_len + 1), sizeof(char));
// iterate over each keysize
for (int keysize = 1; keysize <= string_len; keysize++) {
// set `keysize` indexes to the first letter in our alphabet
for (int i = 0; i < keysize; i++) {
current_key[i] = alphabet[0];
}
// determine the max number of character combinations for the current keysize
double num_combinations = pow(alphabet_len, keysize);
int index = 0;
while (index++ < num_combinations) {
printf("%s\n", current_key);
// update the first character in our key
int alphabet_index = (index % alphabet_len);
current_key[0] = alphabet[alphabet_index];
if ((alphabet_index == 0) && (keysize != 1)) {
// our first character has wrapped back to the beginning; begin a waterfall updating the next
// character in the key (and repeat until the *next* character doesn't wrap)
int key_index = 1;
alphabet_index = ((int)(strchr(alphabet, current_key[key_index]) - alphabet) + 1) % alphabet_len;
current_key[key_index] = alphabet[alphabet_index];
printf("current_key[%d] = alphabet[%d], %d = %c\n", key_index, alphabet_index, key_index, alphabet[alphabet_index]);
if (alphabet_index == 0) {
key_index = (key_index + 1) % keysize;
while (key_index > 0) {
alphabet_index = ((int)(strchr(alphabet, current_key[key_index]) - alphabet) + 1) % alphabet_len;
current_key[key_index] = alphabet[alphabet_index];
printf("current_key[%d] = alphabet[%d], %d = %c\n", key_index, alphabet_index, key_index, alphabet[alphabet_index]);
key_index = (key_index + 1) % keysize;
if (alphabet_index != 0) break;
}
}
}
}
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment