What's new

Generic lexical permutations

AceInfinity

Moderator, Programming, Contributor
Joined
Feb 21, 2012
Posts
1,729
Location
Canada
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:

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)));
        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) continue;

        // result[index] = tokens;
        memcpy((char *)result + (index * token_size),
               (char *)tokens + (i * token_size),
               token_size);

        --tokens_cnt;
        lexical_permutation(result, index + 1, result_length,
                            tokens, token_size, tokens_cnt, num_tokens,
                            callback);
        ++tokens_cnt;
    }
}

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:
Top