I'm looking for a way to generate all of the possible complete partitions
of a string.
That is, if I have a string "ABCD", I want to generate the list:
"ABCD"
"ABC" "D"
"AB" "CD"
"AB" "C" "D"
"A" "BCD"
"A" "BC" "D"
"A" "B" "CD"
"A" "B" "C" "D"
Of course, defining an algorithm for generating these partitions is
pretty straightforward. But this looks like the sort of problem that
would have had some history behind it, and I'm interested in seeing what
other people have written about it.
If I had wanted to generate all possible permutations of a string, for
example, I might write my own permutation algorithm, but I'd want to read
a bit on what others have to say on permutation algorithms, first. Or at
least I'd look up permutation algorithms in Knuth.
Generating all the possible complete partitions of a string is a simpler
problem than all the permutations of a set. But I'd still like to read
what others have had to say about the problem.
The problem is I don't know what people call the problem.
What do people call this? Are there any preferred algorithms, other than
the obvious?
--
When a clever man was stupid, he was stupid in a way a man who was
stupid all the time could never hope to match, for the clever man's
stupidity, drawing as it did on so much more knowledge, had a breadth
and depth to it the run-of-the-mill fool found impossible to duplicate.
- Harry Turtledove
|
