In article <tm********************************@4ax.com>,
Jeff Kish <je*******@mro.com> wrote:
Hi.
I realize this might be more of a "figure out the algorithm" thing than
strictly an std question.. sorry if it is off topic? It certainly was in the
other group!
Also, I'm pretty old, not in school.. just trying to figure this out., so it
isn't an assignment.
I see you can use next_permutation to find the permutations of a string of a
given length.
Right now I'm using a string, sorting it and passing it repeated into
next_permutation.
Is there any slick way to find all of them of any length, i.e. given a string
"dear" to get all of all lengths including:
a
ra
are
ear
dear
read
dare
I'm trying to figure out an algorithm to find all possible words from a set of
strings, without using any letters any more than they are in the string, i.e.
given lott you would not come up with "loot"
There's a closely related article in the Feb. '05 issue of C/C++ Users
Journal by John Dibling titled "Extending the STL".
In this article he defines a generic algorithm:
template <class BidirectionalIterator, class Function, class Size>
Function
for_each_permutation(BidirectionalIterator first,
BidirectionalIterator last,
Size k,
Function fn);
The algorithm is documented to come from "The Art of Computer
Programming," Vol. 1, p. 45, Method 1.
for_each_permutation calls fn for each permutation of last-first items
taken k at a time:
fn(first, last)
I think this is a great algorithm, except that I think it would be
better if the Function were called with only the first k elements of the
permuted sequence, else you have to store k in fn:
fn(first, first+k)
Inspired by John's article, I wrote my own version of
for_each_permutation, which uses a slightly modified copy of
std::next_permutation to take into account that you sometimes only want
the items taken k at a time. However one could easily modify John's
publicly available listing to call fn(first, first+k) instead of
fn(first, last). Note, you might want to use std::advance where I've
used "+" to avoid requiring random access iterators.
At any rate, once you have this tool, your original problem can be
solved quite elegantly:
Create a printing functor:
class print
{
public:
print() : i_(0) {}
template <class It>
void operator()(It first, It last)
{
typedef typename std::iterator_traits<It>::value_type value_type;
std::ostream_iterator<value_type> out(std::cout, " ");
std::cout << ++i_ << "\t: ";
std::copy(first, last, out);
std::cout << '\n';
}
private:
unsigned i_;
};
And then call for_each_permutation with this functor and for each
permutation length you're interested in (1 to 4):
print p;
for (unsigned k = 1; k <= size_array; ++k)
p = for_each_permutation(array, array + size_array, k, p);
The printing functor keeps a simple state which is just the line number.
Note that by passing the same functor back in, and catching it from the
return, the line number is kept up to date. My output looks like:
1 : a
2 : d
3 : e
4 : r
5 : a d
6 : a e
7 : a r
8 : d e
....
Kudos to John Dibling for suggesting the for_each_permutation algorithm.
I think for_each_combination would also be a valuable tool in the box:
template <class BidirectionalIterator, class Size,
class Functor>
Functor
for_each_combination(BidirectionalIterator first,
BidirectionalIterator last, Size k,
Functor f);
template <class BidirectionalIterator, class Size,
class Functor, class Compare>
Functor
for_each_combination(BidirectionalIterator first,
BidirectionalIterator last, Size k,
Functor f, Compare comp);
-Howard
