Compute all permutations over n integers

Categories: Algorithms
Tags: , ,
Comments: 1 Comment
Published on: 28 mars 2012
#include "float.h"
#include <stdio.h>
#include <time.h>
#include <stdint.h>
#include <stdlib.h>

#define add(bitset, i) (bitset | (1<<i)) // add element in bit set
#define in(bitset, i) ( (bitset) & (1<< (i) )) // check if the element is in
#define rem(bitset, i) (bitset & ~(1<<i)) // rem element 

void print_bitset(int32_t, int32_t);
void print_tab(int*, int32_t);
int32_t next(int32_t, int32_t, int32_t);
void incr(int*, int32_t, int32_t, int*);
void print_binary(int32_t);
int32_t nlz(int32_t);
int32_t find_next_zero_bit(int32_t, int32_t);

/**
 * Utility function to display the bitset content
 */
inline void print_bitset(int32_t bs, int32_t n)
{
    for(int32_t i=0; i<n; i++) printf("%d:%d ",i ,(in(bs,i)>0 ? 1 : 0));
    printf("\n");
}
/**
 * Utility function to display the solution
 */
inline void print_tab(int* t, int32_t n)
{
    int32_t i;
    for(i=0; i -1)
    {
        ret[0] = 1;
        ret[1] = rem(ret[1], sol[i]);
        sol[i] = inc;
        ret[1] = add(ret[1], inc);
    }
}

inline void print_binary(int32_t a)
{
    for(int32_t i=0; i&lt; 32; i++)
    {
        int32_t n = in(a,i);
        printf("%d ", (n&gt;0 ? 1 : 0));
    }
    printf("\n");
}

inline int32_t nlz(int32_t x)
{
    int32_t y, m, n;
    y = -(x &gt;&gt; 16);	// If left half of x is 0,
    m = (y &gt;&gt; 16) &amp; 16;	// set n = 16. If left half
    n = 16 - m;	// is nonzero, set n = 0 and
    x = x &gt;&gt; m;	// shift x right 16.
    // Now x is of the form 0000xxxx.
    y = x - 0x100;	// If positions 8-15 are 0,
    m = (y &gt;&gt; 16) &amp; 8;	// add 8 to n and shift x left 8.
    n = n + m;
    x = x &lt;&lt; m;
    y = x - 0x1000;	// If positions 12-15 are 0,
    m = (y &gt;&gt; 16) &amp; 4;	// add 4 to n and shift x left 4.
    n = n + m;
    x = x &lt;&lt; m;
    y = x - 0x4000;	// If positions 14-15 are 0,
    m = (y &gt;&gt; 16) &amp; 2;	// add 2 to n and shift x left 2.
    n = n + m;
    x = x &lt;&lt; m;
    y = x &gt;&gt; 14;	// Set y = 0, 1, 2, or 3.
    m = y &amp; ~(y &gt;&gt; 1);	// Set m = 0, 1, 2, or 2 resp.
    return n + 2 - m;
}

inline int32_t find_next_zero_bit(int32_t o, int32_t offset)
{
    o = o &gt;&gt; offset;
    o = ~o;
    int32_t mask = o &amp; -o;
    return 31 - nlz(((mask) &lt;&lt; offset));
}

int32_t main(int32_t argc, char *argv[])
{
    clock_t start = clock();
    int32_t* solution;
    int32_t n = 10; // number of meetings
    int32_t i = n-1;  // last item index
    int32_t bs = 0; // bitset which contains the already tuned meetings
    double bound = DBL_MAX;
    double currentValue = 0;
    int32_t options[2];

    solution = (int32_t *) malloc(n * sizeof(int32_t));

    for(int32_t j=0; j<n; j++)
    {
        solution[j] = j;
        bs = add(bs, j);
    }

    //print_bitset(bs, n);

    while(i > 0)
    {
        if(i == n-1 && solution[n-1] > -1)
        {
            // currentValue = eval(i)
            //print_tab(solution, n);
        }

        if(currentValue < bound)
        {
            options[1] = bs;
            incr(solution, i, n, options);
            bs = options[1];
            if(options[0]>0)
            {
                i++;// = (i<n-1 ? i+1 : i-1);
            }
            else
            {
                // Set the end of the solution to -1
                // (because the first index is 0)
                for(int32_t j=i; j<n; j++)
                {
                    bs = rem(bs, solution[j]);
                    solution[j] = -1;
                }
                i--;
            }
        }
        else
        {
            i--;
        }
    }
    printf("%d %f\n", n, ((double)clock() - start) / CLOCKS_PER_SEC);
}
page 1 of 1

Welcome , today is Mardi, 8 mai 2012