1. #1
    AceInfinity's Avatar
    Join Date
    Feb 2012
    Location
    Canada
    Posts
    1,708

    Generic lexical permutations

    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:
    #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;
    }
    This code demonstrates all of the lexical permutations (unique) of a binary string with 3 set bits. The results are below:

    Code:
    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
    Last edited by AceInfinity; 08-26-2017 at 01:46 AM.
    writhziden, x BlueRobot and tom982 say thanks for this.
    \n\n

    Automation Programmer
    Development Site: aceinfinity.net


    • Ad Bot

      advertising
      Beep.

        
       

Similar Threads

  1. Replies: 0
    Last Post: 05-20-2012, 07:35 PM

Log in

Log in