CODEWITHSUNDEEP
calgorithmbinary-tree
matovitch
matovitch

Reputation: 1284

Permutation of an array, binary tree, backtracking

I would like to write a function permuting an array in the following way. Given a binary tree like this one (in hexadecimal to maintain the symmetry) :

 0
        1
    2       3
  4   5   6   7
 8 9 A B C D E F

I would like to get the number following the backtracking algorithm :

[0,1,2,4,8,9,5,A,B,3,6,C,D,7,E,F]

I already wrote a C function, but I am sure there is a cleaner/faster recursive way to do it. Here is my code :

void bin_perm(float* data, float* bprm, size_t size) {
    bprm[0] = data[0];
    size_t j = 1;
    size_t i = 1;
    while (j < size) {
        while (i < size) {
            bprm[j++] = data[i];
            i *= 2;
        }
        i = i / 2 + 1;
        while (i % 2 == 0) {
            i /= 2;
        }
    }
}

Upvotes: 0

Views: 161

Answers (1)

timrau
timrau

Reputation: 23058

void bin_perm_recur(float* data, size_t data_idx, float* bprm, size_t* bprm_idx_ptr, size_t size)
{
    bprm[(*bprm_idx_ptr)++] = data[data_idx];
    if (data_idx * 2 < size)
        bin_perm_recur(data, data_idx * 2, bprm, bprm_idx_ptr, size);
    if (data_idx * 2 + 1 < size)
        bin_perm_recur(data, data_idx * 2 + 1, bprm, bprm_idx_ptr, size);
}

void bin_perm(float* data, float* bprm, size_t size)
{
    bprm[0] = data[0];
    size_t j = 1;
    bin_perm_recur(data, 1, bprm, &j, size);
}

Upvotes: 2

Related Questions