The blog continues at suszter.com/ReversingOnWindows

December 19, 2014

Variable-length permutation with repetition using backtracking

Recently, I needed the implementation of the search algorithm that qualifies for the followings.
  1. It must be able to produce the variable-length permutation with repetition of the given set.
  2. It must be based on backtracking.
  3. It must be a state machine.
  4. It must have basic programming elements only.
  5. It must be clean without irrelevant part.
Even I needed the final implementation in ActionScript, I was searching for the algorithm in C that I would convert later. Thought my odds would be better if I did so. Unluckily I didn't find anything useful, and so I wrote the code myself. Here is the sample implementation in C.

// Features:
// - Variable-length permutation with repetition
// - Backtracking
// - State machine

#include <stdio.h>

#define ITEMS            3                       // number of items
#define LASTITEM_IDX     (ITEMS-1)               // index of the last item
#define INIT             -1                      // initial value
#define EMPTY            0                       // empty

static char set[ITEMS]  = {1,2,3};               // set

// State
static char idx[ITEMS]  = {INIT,INIT,INIT};      // indices into set
static char out[ITEMS]  = {EMPTY,EMPTY,EMPTY};   // output

static int index = INIT;
static bool dir = 1;                             // direction: deep(1) / wide(0)
// State - END

bool backtrack();

// item to try
void add_item() {
    idx[index]++;
    out[index] = set[idx[index]];
}

bool step_wide() {
    if (index == INIT) {
        // reached initial level
        // no more items to take
        return false;
    }
    // way to go wider?
    if (idx[index] < LASTITEM_IDX) {
        add_item();          // take item
        return true;
    }
    else {
        return backtrack();  // backtrack a level higher
    }
}

bool backtrack() {
    // backtrack a level higher
    idx[index] = INIT;
    out[index] = EMPTY;
    index--;

    return step_wide();
}

bool step_deep() {
    // way to go deeper?
    if (index < LASTITEM_IDX) {
        index++;             // step a level deeper
        add_item();          // take item
        return true;
    }
    else {
        return step_wide();  // step wide
    }
}

// returns true if step is successful
// returns false if no more items to take
bool step() {
    if (dir) {
        return step_deep();
    } else {
        return step_wide();
    }
}

int main(int argc, char* argv[])
{
    while (step()) {
        for (int i=0; i<ITEMS && out[i]!=EMPTY; i++) {
            printf("%02x ", out[i]);
        }
        printf("\n");
    }

    return 0;
}

The source can be downloaded from here.

The output of the run looks like this.

01
01 01
01 01 01
01 01 02
01 01 03
01 02
01 02 01
01 02 02
01 02 03
01 03
01 03 01
01 03 02
01 03 03
02
02 01
02 01 01
02 01 02
02 01 03
02 02
02 02 01
02 02 02
02 02 03
02 03
02 03 01
02 03 02
02 03 03
03
03 01
03 01 01
03 01 02
03 01 03
03 02
03 02 01
03 02 02
03 02 03
03 03
03 03 01
03 03 02
03 03 03
  This blog is written and maintained by Attila Suszter. Read in Feed Reader.