迭代計算功率集一集或矢量

雖然有很多關於如何生成的實際功率集一集的例子，我無法找到任何迭代產生的功率設置（如std::iterator）的。我會欣賞這種算法的原因是我的基本集的大小。由於n元素集合的冪集具有2^n個元素，因此在實際計算集合時，我會很快耗盡內存。那麼，有沒有辦法爲給定集的冪集創建一個迭代器？它甚至有可能嗎？迭代計算功率集一集或矢量

如果它會更容易，創建套int s就可以了迭代器 - 我可以用它們作爲評價實際設置/矢量。
正如我實際上是在一個std::vector工作，如果使用for_each_combination從Combinations and Permutations一個neccessary

來源

2014-09-22 wondering

使用'n'位的位，初始化爲零。在每一步中，加上1進位，就好像該位表示一個「n」位整數。使用結果模式的零和1來確定哪些元素屬於當前子集。重複，直到bitset達到全部1。如果'n <= 64'（或任何平臺上可用的最大整數），則可以使用實際的整數變量來代替位集。 – 2014-09-22 23:41:01

謝謝@IgorTandetnik - 關於如何處理這個問題的常識，就是我沒有足夠努力去尋找？如果你將它添加爲一個，我會高興地接受這個答案。 – wondering 2014-09-22 23:45:14

可以很容易地通過電源集std::vector<AnyType>的所有成員進行迭代隨機訪問將是可能的。例如：

#include <vector> 
#include <iostream> 
#include "../combinations/combinations" 

int 
main() 
{ 
    std::vector<int> v{1, 2, 3, 4, 5}; 
    std::size_t num_visits = 0; 
    for (std::size_t k = 0; k <= v.size(); ++k) 
     for_each_combination(v.begin(), v.begin()+k, v.end(), 
      [&](auto first, auto last) 
      { 
       std::cout << '{'; 
       if (first != last) 
       { 
        std::cout << *first; 
        for (++first; first != last; ++first) 
         std::cout << ", " << *first; 
       } 
       std::cout << "}\n"; 
       ++num_visits; 
       return false; 
      }); 
    std::cout << "num_visits = " << num_visits << '\n'; 
}

此訪問這個vector的每個發電機組成員，並執行函子，它只是計數的訪問次數，並打印出當前的功率設置：

{} 
{1} 
{2} 
{3} 
{4} 
{5} 
{1, 2} 
{1, 3} 
{1, 4} 
{1, 5} 
{2, 3} 
{2, 4} 
{2, 5} 
{3, 4} 
{3, 5} 
{4, 5} 
{1, 2, 3} 
{1, 2, 4} 
{1, 2, 5} 
{1, 3, 4} 
{1, 3, 5} 
{1, 4, 5} 
{2, 3, 4} 
{2, 3, 5} 
{2, 4, 5} 
{3, 4, 5} 
{1, 2, 3, 4} 
{1, 2, 3, 5} 
{1, 2, 4, 5} 
{1, 3, 4, 5} 
{2, 3, 4, 5} 
{1, 2, 3, 4, 5} 
num_visits = 32

語法我上面使用的是C++ 14。如果你有C++ 11，你將需要改變：

[&](auto first, auto last)

到：

[&](std::vector<int>::const_iterator first, std::vector<int>::const_iterator last)

而如果你是在C++ 98/03，你將不得不寫一個函子或函數來替換lambda。

for_each_combination函數不分配額外的存儲空間。這全部通過將vector的成員交換到[v.begin(), v.begin()+k)範圍內來完成。在每次調用for_each_combination結束時，矢量都保持其原始狀態。

如果由於某種原因想要提早退出for_each_combination，只需返回true而不是false即可。

來源

2014-09-22 23:49:10

迭代計算功率集一集或矢量

回答

相關問題