Daniel said:
Thanks to everyone who replied.
The thing is that all of the solutions referred to seem to be based on
exchanging elements. And that clearly cannot generate all the permutations of
length 2 of elements of the string A B C.
In fact I couldn't find anything that didn't start off by being dazzled by the
mathematical purity of exchanging elements. The best references I found were a
1977 review paper by Sedgewick (which starts off by saying "Over thirty
algorithms have been published during the last twenty years for generating
[permutations]", and then unifies them into a framework based on exchanges),
and -- inevitably -- Knuth. It's all very interesting, but none of it does
what I want :-(
It isn't that I don't know how to generate permutations (of substrings). For
instance any of the above algorithms could be applied to each combination in
turn. But it seems strange that while one can iterate over any of:
the length R combinations,
the length R combinations-with-repetition,
the length R permutations-with-repetition,
and the length R subsequences[*]
of N elements using minor variations to the framework in the original
algorithm, there is no obvious way of doing the permutations with the same
framework. It is obvious that the auxiliary array 'a' /does/ contain enough
information to permit generating permutations -- just iterate the
permutations-with-repetition skipping candidates with repeated elements, but
that's O(N**R) not O(N perm R). I still suspect that it /should/ be doable,
but can't think of or find a way of doing it. (The nearest I've got so far
requires keeping an addition Set of size O(R) and is basically the
generate-and-discard algorithm with a bit of early pruning).
-- chris
([*] same algorithm as for length R combinations)