将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：

组合顺序随机（每次我们要组合文件时，set 4中的顺序都会改变）
相同类型的文件可以一个接一个地放置如果它们具有相同的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

如果您能以某种方式消除连续放置具有相同 ID 的文件的第二个要求，您的问题可能会减少到 well-known algorithm for random shuffling。

您可以通过随机排列文件组而不是单个文件来解决此问题（当然，一个组可能只包含一个文件）。

制作一个数据结构，表示具有特定类型和ID的文件组，以及一组页面
将您的文件列表组合成组
运行一组随机洗牌
将结果展开回单个文件的列表

此组结构可能如下所示：

class FileGroup {
    string name;
    string id;
    set<int> pages;
public:
    FileGroup(const string& _name, const string& _id) : name(_name), id(_id) {}
    void addPage(int pg) { pages.insert(pg); }
    ...
};

您的示例数据如下所示：

"Assignation" - "043" - { 1, 2 }
"Assignation" - "045" - { 1 }
"Conclusions" - "009" - { 1 }
"Conclusions" - "010" - { 1 }
"Conclusions" - "011" - { 1 }
"Judgement"   - "017" - { 1, 2, 3 }
"Judgement"   - "018" - { 1, 2 }

现在相关文件的页面将保持在一起，无论您以何种方式打乱分组。

Answer 2

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

将所有章节存储在由唯一（章节，章节编号）键控的集合中：

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

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

让我们开始吧。我在 "random" 订单中填写 table：

 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
 }

就这些了！

现在我们可以像这样通过section/chapter打印模块：

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

既然我们已经创建了所需的顺序，让我们添加一些不可预测性（这与混沌有微妙的不同） .

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());

砰。我们对模块 table 条目的引用进行了混洗。 但是！随机不是目标。

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

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

当然，打印结果选择：

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

打印一些diagnostic/trace信息的版本可以在这里看到：

Live On Coliru

完整列表

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

将n组文件组合在一起（随机且不重复）

Combine n sets of files together (randomly and no repetition)

c++

sorting

algorithm

merge

完整列表