print and count the number of permutation (without using stl next_permutation)

Go To StackoverFlow.com

2

I'm a C programmer and trying to get better at C++. I want to implement a permutation function (without using the STL algorithms). I came up with the following algorithm (out of my C way of thinking), but

a) it crashes for k > 2 (I suppose because the element that the iterator 
   points to, gets deleted, is inserted back and then incremented).
b) erase/insert operation seem unnecessary. 

How would the C++ experts amongst you implement it?

template <class T>
class Ordering {
    public:
          Ordering(int n);
          int combination(int k);
          int permutation(int k);
    private:
          set<T> elements;
          vector<T> order;
}

template <class T>
int Ordering<T>::permutation (int k) {
    if (k > elements.size()) {
        return 0;
    }

    if (k == 0) {
        printOrder();
        return 1;
    }

    int count = 0;
    for (typename set<T>::iterator it = elements.begin();
        it != elements.end();
        it++
    )
    {
        order[k-1] = *it;
        elements.erase(*it);
        count += permutation(k-1);
        elements.insert(*it);
    }
    return count;
}
2012-04-03 22:01
by zonked.zonda
If it crashes, then you should probably debug it - Oliver Charlesworth 2012-04-03 22:07
If it didn't crash, it wouldn't be C thinking, would it - Kerrek SB 2012-04-03 22:14
@KerrekSB: Ironically, it breaks due to a detail deep in the bowels of the standard library. Funny, isn't it : - bitmask 2012-04-03 22:38


0

The problem is in your iteration over the elements set. You try to increment an iterator which you have removed. That cannot work.

If you insist in using this approach, you must store the successor of it, before calling set::erase. That means you have to move the incrementation part of your for loop into the loop.

Like this:

for (typename set<T>::iterator it = elements.begin();
    it != elements.end();
    /* nothing here */
)
{
    order[k-1] = *it;
    typename set<T>::iterator next = it;
    ++next;
    elements.erase(*it);
    count += permutation(k-1);
    elements.insert(order[k-1]);
    it = next;
}

Edit: One possible way of temporarily "removing" objects from your set would be to have a std::set<std::pair<T,bool>> and simply write it->second = false and afterwards it->second = true. Then, while iterating, you can skip entries where the second value is false. This adds a bit of an overhead since you have to do a lot more work while descending. But inserting+removing elements adds a logarithmic overhead every time, which is probably worse.

If you used a (custom) linked list (perhaps you can even get std::list to do that) you could very inexpensively remove and re-insert objects.

2012-04-03 22:33
by bitmask
Makes sense. And I confirmed that it works. Is there any other way to exclude the already selected elements, without modifying the set? If it were a vector instead, I could have swapped elements and created the permutations in-place - zonked.zonda 2012-04-03 23:07
@zonked.zonda: See my edit. The first paragraph still tries to keep your set, while the last paragraph is probably what you want. It's reasonably fast, and if you use a custom allocator in the constructor of your type, I would have a hard time coming up with an even faster solution (especially since we don't know what T is) - bitmask 2012-04-04 01:39