c++ - 打印并计算排列数(不使用 STL next_permutation)

Question

我是一名 C 程序员，正在努力提高 C++ 水平。我想实现一个排列函数(不使用 STL 算法)。我想出了以下算法(出于我的 C 思维方式)，但是

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. 

你们中的 C++ 专家将如何实现它？

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;
}

Answer 1

问题出在您对 elements 的迭代中放。您尝试增加已删除的迭代器。那行不通。

如果你坚持使用这种方法，你必须存储it的后继者。 , 在调用 set::erase 之前.这意味着您必须将 for 循环的递增部分移到循环中。

像这样:

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;
}

---

编辑:从你的集合中临时“删除”对象的一种可能方法是使用 std::set<std::pair<T,bool>>然后简单地写it->second = false然后it->second = true .然后，在迭代时，您可以跳过 第二个值为 false 的条目.这会增加一些开销，因为您在下降时必须做更多的工作。但是插入+移除元素每次都会增加对数开销，这可能更糟。

如果您使用(自定义)链表(也许您甚至可以获得 std::list 来做到这一点)，您可以非常便宜地删除和重新插入对象。