AceInfinity
Emeritus, Contributor
I tried coming up with a good way to allow for lexical permutations in C in such a generic way that hopefully wouldn't violate strict aliasing rules, and still retained a lot of the capability I needed. Here's what I came up with:
This code demonstrates all of the lexical permutations (unique) of a binary string with 3 set bits. The results are below:
Code:
[NO-PARSE]#include <stdio.h>
#include <string.h>
#include <assert.h>
#define UNUSED(x) ((void)(x))
#define BITS 8 // max bits for permutation
#define NUM_TOKENS 2 // binary 1 or 0
void evaluate_result(void *data, size_t size, size_t length)
{
char ch;
size_t i, n;
n = 0;
for (i = 0; i < length; ++i)
{
putchar((ch = ((char *)data)[i]));
n = (n << 1) | (ch - '0');
}
printf(" = %u\n", n);
UNUSED(size);
}
void lexical_permutation(void *restrict result, size_t index, size_t result_length,
void *restrict tokens, size_t token_size, unsigned int *restrict tokens_cnt, size_t num_tokens,
void callback(void *, size_t, size_t))
{
size_t i;
assert(index <= result_length);
if (index == result_length)
{
if (callback) callback(result, token_size, result_length);
return;
}
for (i = 0; i < num_tokens; ++i)
{
if (!tokens_cnt[i]) continue;
// result[index] = tokens[i];
memcpy((char *)result + (index * token_size),
(char *)tokens + (i * token_size),
token_size);
--tokens_cnt[i];
lexical_permutation(result, index + 1, result_length,
tokens, token_size, tokens_cnt, num_tokens,
callback);
++tokens_cnt[i];
}
}
int main(void)
{
char result[BITS];
int setbits = 3;
char tokens[NUM_TOKENS] = { '1', '0' };
unsigned int tokens_cnt[NUM_TOKENS] = { setbits, BITS - setbits };
assert(setbits <= BITS);
lexical_permutation(result, 0, BITS, tokens, sizeof(*tokens), tokens_cnt, NUM_TOKENS, evaluate_result);
return 0;
}[/NO-PARSE]
This code demonstrates all of the lexical permutations (unique) of a binary string with 3 set bits. The results are below:
Code:
[NO-PARSE]11100000 = 224
11010000 = 208
11001000 = 200
11000100 = 196
11000010 = 194
11000001 = 193
10110000 = 176
10101000 = 168
10100100 = 164
10100010 = 162
10100001 = 161
10011000 = 152
10010100 = 148
10010010 = 146
10010001 = 145
10001100 = 140
10001010 = 138
10001001 = 137
10000110 = 134
10000101 = 133
10000011 = 131
01110000 = 112
01101000 = 104
01100100 = 100
01100010 = 98
01100001 = 97
01011000 = 88
01010100 = 84
01010010 = 82
01010001 = 81
01001100 = 76
01001010 = 74
01001001 = 73
01000110 = 70
01000101 = 69
01000011 = 67
00111000 = 56
00110100 = 52
00110010 = 50
00110001 = 49
00101100 = 44
00101010 = 42
00101001 = 41
00100110 = 38
00100101 = 37
00100011 = 35
00011100 = 28
00011010 = 26
00011001 = 25
00010110 = 22
00010101 = 21
00010011 = 19
00001110 = 14
00001101 = 13
00001011 = 11
00000111 = 7[/NO-PARSE]
Last edited: