打印並計算排列次數（不使用stl next_permutation）

我是C程序員，想要在C++中變得更好。我想實現一個置換函數（不使用STL算法）。我提出了以下算法（出於我的C思維方式），但是打印並計算排列次數（不使用stl next_permutation）

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

來源

2012-04-03 zonked.zonda

如果它崩潰，那麼你應該調試它。 – 2012-04-03 22:07:59

如果它沒有崩潰，那不會是C的想法，會不會。 – 2012-04-03 22:14:50

@KerrekSB：具有諷刺意味的是，由於標準圖書館內部深處的細節造成的破壞。有趣，是不是:) – bitmask 2012-04-03 22:38:22

問題出在您對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來做到這一點），你可以非常便宜地刪除和重新插入對象。

來源

2012-04-03 22:33:57 bitmask

有道理。我證實它的工作原理。有沒有其他的方法可以排除已經選擇的元素，而不需要修改集合？如果它是一個向量，我可以交換元素並在原地創建排列。 – 2012-04-03 23:07:18

@ zonked.zonda：看我的編輯。第一段仍然試圖保留你的設定，而最後一段可能是你想要的。它的速度相當快，如果在類型的構造函數中使用自定義分配器，我將很難提出更快的解決方案（特別是因爲我們不知道「T」是什麼）。 – bitmask 2012-04-04 01:39:44

打印並計算排列次數（不使用stl next_permutation）

回答

相關問題