Generating permutations is not very hard and normaly the algorithm are quite simple. But when I looked into traversing permutation using an iterator I had to invent some. Lets look first at the simple case witch just generates all permutations. I finally came up with two possible solutions:

1. traversing the derivation tree

This example looks at a tree. The root node is always empty. The first layer are all nodes containing one unique symbol out of the alphabet. The 2nd layer contains all possible strings containing 2 unique symbols etc.

01 printPerm(slist, tlist)
02 begin
03   if slist.isEmpty then print permutation in tlist
04   else
05     begin
06       for each item in slist do
07         slist':= slist / { item };
08         tlist':= tlist union { item };
09         printPerm(slist', tlist');
10       end
11     end 
12 end

As we can see this is not very usefull for iterations.

2. Traversing the tree with iterator

This is algorithm is a little bit more involved. Actually it's a extension to the first one. We simply keep track of each iterator position. Therefore we use for each level of the tree an iterator. Whenever we backtrack we reset the iterator (line 20).

01 perm:= getNextPerm()
02 begin
03   i:= 0;
04   repeat
05     it <- source.iterator[i];
06 
07     if it.hasNextUnmarkedItem then
08       begin
09         item <- it.nextUnmarkedItem;
10
11         mark item;
12         perm.push( item );
13         i++;
14       end
15     else
16       begin
17         i--
18         item = perm.pop
19         unmark item
20         it.reset();
21       end
22   until( i = source.length and i >= 0)
23 end

ZeusBase implementation

ZeusBase has been extended with the permutation class TPermutation. The use is quite simple:

01 TPermutation Perm(4); // with 4 elements
02 while(Perm.hasNextPerm())
03 {
04   TIterator<Int> It = Perm.getNextPerm().getIterator();
05   TString strOut;
06   while(It.hasNextItem())
07   {
08     strData += It.getNextItem();
09   }
10   printf("\nPerm: %s", strOut.c_str());
11 }

The TPerumtation class returns each time a list with the indices 1 to 4. These indices might be used as a lookup for other data structures such as string list, arrays etc.