- It must be able to produce the variable-length permutation with repetition of the given set.
- It must be based on backtracking.
- It must be a state machine.
- It must have basic programming elements only.
- It must be clean without irrelevant part.
// 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 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