Permutations of the alphabet with backtracking

Question

/* Generates permutations over an array of integers by backtracking. 
 *
 * chain[]  Status stack with box index per level 
 * box[]    Marks pieces available for next permutation 
 *
 * The candidate_next() is a filter or wrapper to box_next(). It is needed 
 * to prune the huge tree (26! = 10^25 final permutations). It also simulates
 * the way to place a constraint satisfaction test (does the current chain 
 * plus the new piece fit?).
 *
 * If show_chain() is added higher up in the main while loop, 
 * then the growing and shrinking chains can be observed.  
 *
 * With only 5 levels ("ABCDE") the candidate testing can be set to always return.  
 */

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define LEVELS 26
char pieces[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
int chain[LEVELS];
int box[LEVELS];

const int TOPLEVEL = LEVELS - 1;

/* Prints the chain up to level "lvl", translating index to letter. */
void show_chain(int lvl) {
    for (int i = 0; i <= lvl; i++ )
        printf("%c", pieces[chain[i]]);
    printf(" ");
}

/* Returns lowest *present* index *above* "lim",  -1 if fail. */
int box_next(int lim) {
    while (++lim < LEVELS)
        if (box[lim]) {
            box[lim] = 0;
            return lim;
        }
    return -1;
}

/* Returns first index in box[] above "start" that passes some tests */
/* "lvl" is only here for tweaking probability */
int candidate_next(int start, int lvl) {
    int new;
    while (start < LEVELS) {
        new = box_next(start);
        if (new == -1)
            return -1;

        /* Test the new candidate -- somehow, or not at all */
        //return new;
        if (lvl == 0)
            return new;
        if (rand() >  RAND_MAX*0.86 + RAND_MAX*0.11 * lvl*lvl/(LEVELS*LEVELS))
            return new;

        /* Failed, put back and continue above */
        box[new] = 1;
        start = new;
    }
    /* Should only happen with a careless call */
    return -1;
}

int main() {
    srand(time(NULL));
    /* Fill the box */
    for (int i = 0; i < LEVELS; i++)
        box[i] = 1;
    int new;
    int loops = 1;
    int lvl = -1;
    int btrack = 0;
    /* The loop starts at "lvl" underground (-1), non-backtracking ("btrack" is 0).
     * It breaks when it reaches same level *backways*
     */
    while (loops++) {

        if (!btrack) {
            //show_chain(lvl); printf("\n");
            if (lvl < TOPLEVEL) {
                new = candidate_next(-1, lvl+1);            /* Search all (-1) */
                if (new >= 0) {
                    chain[++lvl] = new;                         /* Next Level UP/forward and done */
                    continue;
                }
            } else {
                show_chain(lvl); printf("*\n");                 /* On TOPLEVEL. Print before tracking back */
            }
            btrack = 1;
            box[chain[lvl--]] = 1;                      /* Back Down one level */
            continue;
        }
        /* Backtracking */
        if (lvl == -1)
            break;
        box[chain[lvl]] = 1;
        new = candidate_next(chain[lvl], lvl);      /* Search only above current */
        if (new >= 0) {
            chain[lvl] = new;                           /* Stay, Replace this node, Turn around Forwards */
            btrack = 0;
        } else {
            lvl--;                                      /* Go back, still pointing backwards */
        }
    }
    printf("%9d\n", loops);
}

A typical output is:

  IRMPGALUBWJKZSYHXTCQFDVOEN *
  OZBPDAMKULGVIFWRCETHSYQXNJ *
  ZERKJTCSGBUHFWNMXDPIOQAVYL *
   10915520

I adjusted the probability if (rand() > RAND_MAX*0.86 + RAND_MAX*0.11 * lvl*lvl/(LEVELS*LEVELS)) to give a large number of branch visits (10 million), but only a few that reach maximum level of 26. It takes one second.

I think this is quite a generic and flexible algorithm, but I can not find any other examples - if, then they use recursion.

The while loop in main() does have some "if"s on lvl and btrack, and these variables are also modified in different ways in different branches.

But this is all needed to cover the combinations up/down x success/fail plus the check for min. and max. level, isn't it?

Would a recursive solution "look better"?

Is there another way to backtrack? Or can the same incremental permutations be generated without?

---

With #define LEVELS 5 and printing every forward chain

A 
AB 
ABC 
ABCD 
ABCDE *
ABCE 
ABCED *
ABD 
ABDC 
ABDCE *
ABDE 
ABDEC *
ABE 
ABEC 
ABECD *
ABED 
ABEDC *
AC
...