The same approach can now be applied to develop a nonrecursive translation for next.
Nonrecursive Version
"explicit" exit must be made
where setvar(&n,&i) simply sets n to n-1.
The same program can be written in a more structured way. First notice that the statement labeled "two" and the goto "two" statement create a while loop. Introducing that while loop but retaining the structure of "one," the overall structure of the program becomes as follows
Next, the structure of "one" can also be improved, as follows.
The logic of this version is much easier to follow. You can see at a glance that the segment control flows from the top down. It consists of a loop, followed by a decision, followed by a loop. The iterative version of next, translated from the recursive next, and using the improved structure, now becomes as follows:
Second Nonrecursive Version
In general, when the value of a scratchpad variable does not change or does not need to be maintained between recursive calls, it need not be stacked. This is the case with the variable i of next. Also, when there is only one return place from a recursive call, there is no need to stack a return indicator. This is the situation with next. Finally, the value of n varies in a predictable fashion. Its restored value will always be 1 greater than its current value. Thus there is no need to stack n. Each time a recursive call returns, n may be correctly restored by adding 1 to its current value.
Therefore, the stack is unnecessary, since no information must be retained on it. The s_tack function can be removed, setvar can be replaced by the statement n = n-1, and restore can be replaced by the statement n = n+1. Still, the stack controls the second while loop in our translated version. Even though no information needs to be stacked, it is still necessary to know when the stack would have been empty so that the loop may be properly exited.
Notice that the first while loop decreases n by l every time a stack entry would have been made, and the second while increases n by l every time an entry would have been deleted from the stack. Hence, if an integer variable s is set to n initially, prior to the first while loop, the test to see if the stack is empty in the second while loop becomes s = n. The final version of next is an iterative program that has no stack. It is an example of the translated version giving us a better solution. This four-step solution is efficient and is also clear.
1. Set s to n.
2. Set n to the rightmost entry in the permutation that can still be shifted right.
3. If that entry is not l, then
Shift it right
else
Set done to true
4. Place the s-n entries that could not be moved to the right in the proper order at the left end of the permutation.
The final program is as follows:
Final Nonrecursive Version
By translating the recursive solution and analyzing it, a highly efficient nonrecursive solution was built. A little insight can help a lot. For more on recursion, see Barron [1968] and Bird [1977a, 1977b]. It may now be time for you to make a recursive call on all preceding material!
next(n,pdone)
/* Generates the next permutation unless
the current one is the last. In this case
done is set to true.
*/
int n,*pdone;
{int i,retrn;
stack s;
one: if(n > 1)
if(l[n] < n)
{p[l[n]] = p[l[n] + 1];
p[l[n] + 1] = n;
l[n] = l[n] + 1;
}
else
{s_tack(1,n,i,&s);
setvar(&n,&i);
goto one;
}
else
*pdone = TRUE;
two: if(!empty(&s))
{restore(&retrn,&n,&i,&s);
switch(retrn)
{case 1:
{for(i=n-1;i>=1;i--)
p[i+1] = p[i];
p[1] = n;
l[n] = 1;
goto two;
{{{{one: if c1 then
if c2 then
task c1 and c2 both true
else
task for c1 true but c2 false
goto one
else
task for c1 false
while not empty(&s)
loop task
while (c1 and not c2)
task for c1 true but c2 false
if c1, then
task for c1 and c2 both true
else
task for c1 false
while not empty (&s)
loop task.
next(n,pdone)
/* Generates the next permutation unless
the current one is the last. In this case
done is set to true.
*/
int n,*pdone
{int i,retrn;
stack s;
while((n > 1) && !(l[n] < n))
{s_tack(1,n,i,&s);
setvar(&n,&i);
}
if(n > 1)
{p[l[n]] = p[l[n] + 1];
p[l[n] + 1] = n;
l[n] = l[n] + 1;
}
else
*pdone = TRUE;
while(!empty(&s))
{restore(&retrn,&n,&i,&s);
switch(retrn)
{case 1:
{for(i=n-1;i>=1;i--)
p[i+1] = p[i];
p[1] = n;
l[n] = 1;
}
}
}
}
next(n,pdone)
/* Generates the next permutation unless
the current one is the last. In this case
done is set to true.
*/
int n,*pdone
{int i,s;
1. s = n;
2. while((n > 1) && !(l[n] < n))
n--;
3. if(n > 1)
{p[l[n]] = p[l[n] + 1];
p[l[n] + 1] = n;
l[n] = l[n] + 1;
}
else
*pdone = TRUE;
4. while(s > n)
{n++
for(i=n-1;i>=1;i--)
p[i+1] = p[i];
p[1] = n;
l[n] = 1;
}
}