c++ - 将n组文件组合在一起(随机且不重复)

Question

我有以下几组文件:

每个文件的描述如下 type-ID-pageNumber-R.xml 即 jugement_017_3

第 1 组:

 - Conclusions-009-1-R.xml   
 - Conclusions-010-1-R.xml 
 - Conclusions-011-1-R.xml

第 2 组:

 - Assignation-043-1-R.xml    
 - Assignation-043-2-R.xml 
 - Assignation-045-1-R.xml 

第 3 组:

 - Jugement-017-1-R.xml     
 - Jugement-017-2-R.xml  
 - Jugement-017-3-R.xml 
 - Jugement-018-1-R.xml 
 - Jugement-018-2-R.xml 

---

我想将 set 1、set 2 和 set 3 组合成 set 4，方法如下规则:

1. 随机组合顺序(每次我们要组合文件时，set 4中的顺序都会改变)
2. 相同类型的文件如果具有相同的ID
可以一个接一个地放置

---

第 4 组:

- Conclusions-009-1-R.xml 
- Jugement-018-1-R.xml 
- Jugement-018-2-R.xml 
- Assignation-043-1-R.xml    
- Assignation-043-2-R.xml
- Conclusions-010-1-R.xml 
- Assignation-045-1-R.xml 
- Conclusions-011-1-R.xml
- Jugement-017-1-R.xml     
- Jugement-017-2-R.xml  
- Jugement-017-3-R.xml

---

Answer 1

这是我的 0.05 美元实现，以详细说明我的评论:

1. 将所有章节存储在一个集合中，以唯一(章节，章节编号)为键:

   using Section = std::string;
   using Page    = int;
   using Chapter = int;
   using Pages   = icl::interval_set<Page>::type;
   
   struct Module {
       Section section;
       Chapter chapter;
   
       bool operator<(Module const& o) const;
   };
   
   using Table = std::map<Module, Pages>;
   

   如您所见，我选择了一个间隔集来存储页面范围。这使得无论输入顺序如何都更容易进行合并。

2. 那么让我们开始吧。我以“随机”顺序填写表格:

    struct Fill { Section s; Chapter c; Page p; };
    for (auto& fill : std::vector<Fill> { 
        { "Jugement",    18 , 2 },
        { "Conclusions", 11 , 1 },
        { "Assignation", 43 , 1 },
        { "Assignation", 43 , 2 },
        { "Conclusions", 10 , 1 },
        { "Jugement",    17 , 3 },
        { "Assignation", 45 , 1 },
        { "Jugement",    17 , 1 },
        { "Conclusions", 9  , 1 },
        { "Jugement",    17 , 2 },
        { "Jugement",    18 , 1 },
    })
    {
        table[{fill.s, fill.c}] += fill.p; // add page to (existing) range
    }
   

   就是这样!

3. 现在我们可以像这样简单地按节/章打印模块:

    std::cout << "------------- table: \n";
    for (auto& r:table)
        std::cout << r << "\n";
   

   打印:

    ------------- table: 
    Assignation    43  {[1,2]}
    Assignation    45  {[1,1]}
    Conclusions    9   {[1,1]}
    Conclusions    10  {[1,1]}
    Conclusions    11  {[1,1]}
    Jugement   17  {[1,3]}
    Jugement   18  {[1,2]}
   

4. 现在我们已经创建了所需的顺序，让我们添加一些不可预测性(这与混沌有微妙的不同)。

   using rv = rw<Table::value_type>;
   std::vector<rv> vw(begin(table), end(table));
   
   // blind shuffle
   srand(time(0));
   std::random_shuffle(vw.begin(), vw.end());
   

   砰。我们有一个对模块表条目的引用的混洗 View 。 但是!随机不是目标。

   所以我们从匹配的部分中找到相邻的对，并尝试通过旋转它们来移除它们。当然，可能没有任何东西可以交换(来自另一个部分)，在这种情况下，我们将重复项留在尾随位置:

   // try to avoid subsequent modules from equal sections (dup)
   auto dup     = [](rv a, rv b) { return a.get().first.section == b.get().first.section; };
   auto it      = vw.begin();
   auto const e = vw.end();
   
   while(it != e) { // bit redundant, could be while(true)
       it = std::adjacent_find(it, e, dup);
       if (it == e) 
           break;
   
       auto m = std::find_if(it+1, e, [&] (rv r) { return r.get().first.section != it->get().first.section; });
   
       if (m == e) {
           it = m;
       } else {
           std::rotate(it+1, m, e);
           it = std::adjacent_find(it, e, dup);
       }
   }
   

5. 当然，打印结果选择:

   std::cout << "------------- selection: \n";
   for (auto& r : vw)
       std::cout << r.get() << "\n";
   

打印一些诊断/跟踪信息的版本可以在这里看到:

Live On Coliru

完整 list

Live On Coliru

#include <boost/bind.hpp>
#include <boost/icl/interval_set.hpp>
#include <boost/tuple/tuple_comparison.hpp>
#include <iomanip>
#include <iostream>
#include <map>

namespace icl = boost::icl;

template<typename T> using rw = boost::reference_wrapper<T>;

using Section = std::string;
using Page    = int;
using Chapter = int;
using Pages   = icl::interval_set<Page>::type;

struct Module {
    Section section;
    Chapter chapter;

    bool operator<(Module const& o) const { return boost::tie(section,chapter) < boost::tie(o.section,o.chapter); }
};

using Table = std::map<Module, Pages>;

static inline std::ostream& operator<<(std::ostream& os, Table::value_type const& p) {
    return os << p.first.section << "\t" << p.first.chapter << "\t" << p.second;
}

int main()
{
    std::cout << std::unitbuf;
    Table table;

    {
        struct Fill { Section s; Chapter c; Page p; };
        for (auto& tup : std::vector<Fill> { 
            { "Jugement",    18 , 2 },
            { "Conclusions", 11 , 1 },
            { "Assignation", 43 , 1 },
            { "Assignation", 43 , 2 },
            { "Conclusions", 10 , 1 },
            { "Jugement",    17 , 3 },
            { "Assignation", 45 , 1 },
            { "Jugement",    17 , 1 },
            { "Conclusions", 9  , 1 },
            { "Jugement",    17 , 2 },
            { "Jugement",    18 , 1 },
        })
        {
            table[{tup.s, tup.c}] += tup.p; // add page to (existing) range
        }
    }

    std::cout << "------------- table: \n";
    for (auto& r:table)
        std::cout << r << "\n";

    {
        using rv = rw<Table::value_type>;
        std::vector<rv> vw(begin(table), end(table));

        // blind shuffle
        srand(time(0));
        std::random_shuffle(vw.begin(), vw.end());

        // try to avoid subsequent modules from equal sections (dup)
        auto dup     = [](rv a, rv b) { return a.get().first.section == b.get().first.section; };
        auto it      = vw.begin();
        auto const e = vw.end();

        while(it != e) // bit redundant, could be while(true)
        {
            std::cout << "------------- STATE: \n";
            for (auto& rv:vw)
                std::cout << rv.get() << (it->get_pointer() == rv.get_pointer()? "*\n":"\n");

            it = std::adjacent_find(it, e, dup);
            if (it == e) 
                break;

            std::cout << "------------- dupes: \n";
            std::cout << "\t" << (it+0)->get() << "\n";
            std::cout << "\t" << (it+1)->get() << "\n";

            auto m = std::find_if(it+1, e, [&] (rv r) { return r.get().first.section != it->get().first.section; });

            if (m == e)
            {
                it = m;
            } else
            {
                std::cout << "------------- rotating to: \n";
                std::cout << "\t" << m->get() << "\n";

                std::rotate(it+1, m, e);

                it = std::adjacent_find(it, e, dup);
            }
        }
        std::cout << "------------- selection: \n";
        for (auto& r : vw)
            std::cout << r.get() << "\n";
    }
}