从字符串中随机选择特定的子序列

Question

给定一个字符串，其中包含一些穿插着破折号的字符，例如 string s = "A--TG-DF----GR--";，我希望随机 select 一个破折号块（大小可以是 1、2、…、最大字符串中连续破折号的数量），并将它们复制到随机选择的字符串的另一部分。

例如，A--TG-DF(---)-GR-- 移动到 A--T(---)G-DF-GR-- 而另一次迭代可能会使 A--TG-DF----GR(--) 移动到 A--TG-(--)DF----GR。

我正在通过 int i = rand() % (int) s.length(); 生成字符串的随机索引。通过 s.insert(rand() % (int) s.length(), substr); 进行插入，其中 substr 是破折号块。

我的主要问题在于随机一组连续的破折号。我想过使用 s.find("-")，但那只是 return 单个破折号的第一个实例，而不是破折号集合的随机位置。

Answer 1

string::find() 有 optional second parameter: 开始搜索的位置。因此，s.find("-", rand() % L) 之类的东西可能会为您解决问题，其中 L 是（最后一个破折号的位置 + 1）。

Answer 2

据我了解，所有破折号块被选中的概率应该相同。因此我们必须首先找到所有这些块开始的位置，然后随机选择其中一个位置。

如果允许我将 Smalltalk 用于伪代码，那么我会首先找到每个破折号块开始的索引：

dashPositionsOn: aString
    | indexes i n |
    indexes := OrderedCollection new.
    i := 1.
    n := aString size.
    [i <= n] whileTrue: [| char |
        char := aString at: i.
        char = $-
            ifTrue: [
                indexes add: i.
                [
                    i := i + 1.
                    i <= n and: [
                        char := aString at: i.
                        char = $-]] whileTrue]
            ifFalse: [i := i + 1]].
    ^indexes

现在我们可以随机选择以下索引之一：indexes atRandom。

请注意，在 Smalltalk（以及其他语言）中有（很多）更好的方法来实现这个算法。

Answer 3

您可以 pre-process 字符串获取指向字符串中连续破折号开头的迭代器列表，然后从该列表中统一选择一个随机元素。

我将在本示例中使用以下标准库 headers（如果您连接以下代码块，它是完整的并且可以工作）：

#include <cstddef>
#include <iostream>
#include <random>
#include <stdexcept>
#include <string>
#include <vector>

首先，我们定义一个函数来找到我们所说的迭代器列表。为此，我们使用 std::string::find_first_of and std::string::find_first_not_of 来查找下一个序列中的第一个字符和之后的第一个字符的索引。这两个函数都使用索引而不是迭代器，所以我们必须将它们添加到 cbegin()。该函数适用于任何字符，而不仅仅是破折号。

std::vector<std::string::const_iterator>
find_conscutive_sequences(const std::string& text, const char c)
{
  std::vector<std::string::const_iterator> positions {};
  std::size_t idx = 0UL;
  while (idx != std::string::npos && idx < text.length())
    {
      const auto first = text.find_first_of(c, idx);
      if (first == std::string::npos)
        break;
      positions.push_back(text.cbegin() + first);
      idx = text.find_first_not_of(c, first);
    }
  return positions;
}

接下来，我们定义一个函数，该函数使用上述函数的结果 return 一个指向随机 select 破折号序列开头的迭代器。

我们将随机引擎作为参数传入，因此它可以播种一次并反复使用。 random standard library introduced in C++11 is so great that it should be preferred whenever possible over the legacy rand 函数。

如果给定一个 positions 的空向量，我们必须失败，因为没有我们可能 select.

的序列

std::string::const_iterator
get_random_consecutive_sequence(const std::vector<std::string::const_iterator>& positions,
                                std::default_random_engine& prng)
{
  if (positions.empty())
    throw std::invalid_argument {"string does not contain any sequence"};
  std::uniform_int_distribution<std::size_t> rnddist {0UL, positions.size() - 1UL};
  const auto idx = rnddist(prng);
  return positions.at(idx);
}

最后，我定义了这个小辅助函数来标记 selected 序列。您的代码将在此处进行复制/移动/移动。

std::string
mark_sequence(const std::string& text,
              const std::string::const_iterator start)
{
  const auto c = *start;
  const std::size_t first = start - text.cbegin();
  std::size_t last = text.find_first_not_of(c, first);
  if (last == std::string::npos)
    last = text.length();
  std::string marked {};
  marked.reserve(text.length() + 2UL);
  marked += text.substr(0UL, first);
  marked += '(';
  marked += text.substr(first, last - first);
  marked += ')';
  marked += text.substr(last, text.length() - last);
  return marked;
}

可以这样用

int
main()
{
  const std::string example {"--A--B-CD----E-F---"};
  std::random_device rnddev {};
  std::default_random_engine rndengine {rnddev()};
  const auto positions = find_conscutive_sequences(example, '-');
  for (int i = 0; i < 10; ++i)
    {
      const auto pos = get_random_consecutive_sequence(positions, rndengine);
      std::cout << mark_sequence(example, pos) << std::endl;
    }
}

可能的输出：

--A--B-CD(----)E-F---
--A--B(-)CD----E-F---
--A(--)B-CD----E-F---
--A(--)B-CD----E-F---
--A--B-CD(----)E-F---
--A--B-CD----E-F(---)
--A--B-CD----E-F(---)
(--)A--B-CD----E-F---
--A--B(-)CD----E-F---
(--)A--B-CD----E-F---

Answer 4

我知道这个问题很可能在 XY problems 中存在，但我发现它是一个很好的挑战 none-the-less，所以我考虑使用 Boost Interval Container 库来实现它。

库的美妙之处在于您可以忘记很多细节，同时又不会牺牲很多性能。

我冒昧地概括了它，因此它能够同时移动多个破折号块（统一随机选择）。

解决方案运行 Live On Coliru 并在大约 2673 毫秒（在我的机器上为 1156 毫秒):

Generator gen(test_case);

std::string result;
std::map<std::string, size_t> histo;

for(int i = 0; i < 1000000; ++i) {
    auto const mobility = gen.gen_relocations(1 + gen.random(3)); // move n blocks of dashes

    result.clear();
    gen.apply_relocations(mobility, std::back_inserter(result));

    histo[result]++;
}

Note: the benchmark times include the time taken to build the histogram of unique results generated

让我们在这里做一个代码演练来解释事情：

我尝试使用 "readable" 类型：

namespace icl = boost::icl;

using Position = size_t;
using Map      = icl::interval_set<Position>;
using Region   = Map::value_type;

例如构建破折号 Map 的函数很简单：

template <typename It> Map region_map(It f, It l) {
    Map dashes;

    for (Position pos = 0; f!=l; ++f, ++pos)
        if ('-' == *f)
            dashes += pos;

    return dashes;
}

Note how I didn't particularly optimize this. I let the interval_set combine adjacent dashes. We might use hinted insertion, or a parser that add consecutive dashes as a block. I opted for KISS here.

稍后，我们生成重定位，将 Region 映射到文本其余部分的非移动 Position。
```
using Relocs   = boost::container::flat_multimap<Position, Region>;
```
通过使用平面多图，调用者已经按插入点升序对条目进行了排序。因为我们使用了reserve()-ed up-front flat multimap，所以我们在这里避免了基于节点的映射实现的开销。

我们首先选择要移动的破折号块：

Map pick_dashes(int n) {
    Map map;
    if (!_dashes.empty())
        for (int i = 0; i < n; ++i)
            map += *std::next(_dashes.begin(), _select(_rng));
    return map;
}

随机分布在构建时已经确定尺寸，例如：

  _dashes(region_map(_input.begin(), _input.end())),
  _rng(std::random_device {}()),
  _select (0, _dashes.iterative_size() - 1),
  _randpos(0, _input.size() - 1),

接下来，我们为每个分配插入位置。诀窍是在源的非移动（惰性）区域内分配位置。

这包括留在原处的其他破折号块
有退化的情况，所有东西都是破折号块，我们在构造函数中检测到这一点：
```
  _is_degenerate(cardinality(_dashes) == _input.size())
```

所以代码如下：

Relocs gen_relocations(int n=1) {
    Map const moving = pick_dashes(n);

    Relocs relocs;
    relocs.reserve(moving.iterative_size());

    if (_is_degenerate)
    {
        // degenerate case (everything is a dash); no non-moving positions
        // exist, just pick 0
        for(auto& region : moving)
            relocs.emplace(0, region);
    } else {
        auto inertia = [&] {
            Position inert_point;
            while (contains(moving, inert_point = _randpos(_rng)))
                ; // discard insertion points that are moving
            return inert_point;
        };

        for(auto& region : moving)
            relocs.emplace(inertia(), region);
    }

    return relocs;
}

现在我们需要做的就是应用重定位。

这个的通用实现非常简单。同样，它不是为了保持简单而特别优化的（KISS）：

template <typename F>
    void do_apply_relocations(Relocs const& mobility, F const& apply) const {
        icl::split_interval_set<Position> steps {{0, _input.size()}};

        for (auto& m : mobility) {
            steps += m.first; // force a split on insertion point
            steps -= m.second; // remove the source of the move
            //std::cout << m.second << " moving to #" << m.first << ": " << steps << "\n";
        }

        auto next_mover = mobility.begin();

        for(auto& step : steps) {
            while (next_mover!=mobility.end() && contains(step, next_mover->first))
                apply((next_mover++)->second, true);

            apply(step, false);
        }
    }

Note The trick here is that we "abuse" the split_interval_set combining strategy to break the processing into sub-ranges that "stop" at the randomly generated insertion points: these artificial regions are the "steps" in our generation loop.

apply函数就是我们为了得到我们想要的而实现的。在我们的例子中，我们想要一个像 A--TG-DFGR(----)-- 这样的字符串，所以我们使用任何输出迭代器编写一个附加到容器（例如 std::string）的重载：

template <typename Out>
    Out apply_relocations(Relocs const& mobility, Out out) const {
        if (_is_degenerate)
            return std::copy(_input.begin(), _input.end(), out);

        auto to_iter = [this](Position pos) { return _input.begin() + pos; };

        do_apply_relocations(mobility, [&](Region const& r, bool relocated) {
            if (relocated) *out++ = '(';
            out = std::copy(
                to_iter(first(r)),
                to_iter(last(r)+1),
                out
            );
            if (relocated) *out++ = ')';
        });

        return out;
    }

Note The "complicated" part here are mapping the Position to input iterators (to_iter) and the code to optionally add () around moved blocks.

至此，我们已经看到了所有代码。

完整列表

#include <boost/container/flat_map.hpp>
#include <boost/icl/interval_set.hpp>
#include <boost/icl/split_interval_set.hpp>
#include <boost/icl/separate_interval_set.hpp>
#include <boost/lexical_cast.hpp>
#include <boost/range/algorithm.hpp>
#include <iomanip>
#include <iostream>
#include <random>
#include <map>
#include <chrono>

namespace icl = boost::icl;

using Position = size_t;
using Map      = icl::interval_set<Position>;
using Region   = Map::value_type;
using Relocs   = boost::container::flat_multimap<Position, Region>;

struct Generator {
    Generator(std::string const& input) 
        : _input(input),
          _dashes(region_map(_input.begin(), _input.end())),
          _rng(std::random_device {}()),
          _select (0, _dashes.iterative_size() - 1),
          _randpos(0, _input.size() - 1),
          _is_degenerate(cardinality(_dashes) == _input.size())
    {
    }

    unsigned random(unsigned below) {
        return _rng() % below; // q&d, only here to make the tests deterministic for a fixed seed
    }

    Map full() const { 
        return Map { { 0, _input.size() } };
    }

    Relocs gen_relocations(int n=1) {
        Map const moving = pick_dashes(n);

        Relocs relocs;
        relocs.reserve(moving.iterative_size());

        if (_is_degenerate)
        {
            // degenerate case (everything is a dash); no non-moving positions
            // exist, just pick 0
            for(auto& region : moving)
                relocs.emplace(0, region);
        } else {
            auto inertia = [&] {
                Position inert_point;
                while (contains(moving, inert_point = _randpos(_rng)))
                    ; // discard insertion points that are moving
                return inert_point;
            };

            for(auto& region : moving)
                relocs.emplace(inertia(), region);
        }

        return relocs;
    }

    template <typename Out>
        Out apply_relocations(Relocs const& mobility, Out out) const {
            if (_is_degenerate)
                return std::copy(_input.begin(), _input.end(), out);

            auto to_iter = [this](Position pos) { return _input.begin() + pos; };

            do_apply_relocations(mobility, [&](Region const& r, bool relocated) {
                if (relocated) *out++ = '(';
                out = std::copy(
                    to_iter(first(r)),
                    to_iter(last(r)+1),
                    out
                );
                if (relocated) *out++ = ')';
            });

            return out;
        }

    template <typename F>
        void do_apply_relocations(Relocs const& mobility, F const& apply) const {
            icl::split_interval_set<Position> steps {{0, _input.size()}};

            for (auto& m : mobility) {
                steps += m.first; // force a split on insertion point
                steps -= m.second; // remove the source of the move
                //std::cout << m.second << " moving to #" << m.first << ": " << steps << "\n";
            }

            auto next_mover = mobility.begin();

            for(auto& step : steps) {
                while (next_mover!=mobility.end() && contains(step, next_mover->first))
                    apply((next_mover++)->second, true);

                apply(step, false);
            }
        }

  private:
    std::string                             _input;
    Map                                     _dashes;
    std::mt19937                            _rng;
    std::uniform_int_distribution<Position> _select;
    std::uniform_int_distribution<Position> _randpos;
    bool                                    _is_degenerate;

    Map pick_dashes(int n) {
        Map map;
        if (!_dashes.empty())
            for (int i = 0; i < n; ++i)
                map += *std::next(_dashes.begin(), _select(_rng));
        return map;
    }

    template <typename It> Map region_map(It f, It l) {
        Map dashes;

        for (Position pos = 0; f!=l; ++f, ++pos)
            if ('-' == *f)
                dashes += pos;

        return dashes;
    }
};

int main() {

    for (std::string test_case : {
            "----",
            "A--TG-DF----GR--",
            "",
            "ATGDFGR",
        })
    {
        auto start = std::chrono::high_resolution_clock::now();
        Generator gen(test_case);

        std::string result;
        std::map<std::string, size_t> histo;

        for(int i = 0; i < 1000000; ++i) {
            auto const mobility = gen.gen_relocations(1 + gen.random(3)); // move n blocks of dashes

            result.clear();
            gen.apply_relocations(mobility, std::back_inserter(result));

            histo[result]++;
        }
        std::cout << histo.size() << " unique results for '" << test_case << "'"
                  << " in " << std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::high_resolution_clock::now()-start).count() << "ms\n";

        std::multimap<size_t, std::string, std::greater<size_t> > ranked;
        for (auto& entry : histo)
            ranked.emplace(entry.second, entry.first);

        int topN = 10;
        for (auto& rank : ranked)
        {
            std::cout << std::setw(8) << std::right << rank.first << ": " << rank.second << "\n";
            if (0 == --topN)
                break;
        }
    }
}

打印例如

1 unique results for '----' in 186ms
 1000000: ----
3430 unique results for 'A--TG-DF----GR--' in 1156ms
    9251: A(----)--TG-DFGR--
    9226: (----)A--TG-DFGR--
    9191: A--T(----)G-DFGR--
    9150: A--TG-DFGR-(----)-
    9132: A--(----)TG-DFGR--
    9128: A--TG(----)-DFGR--
    9109: A--TG-D(----)FGR--
    9098: A--TG-DFG(----)R--
    9079: A--TG-DFGR(----)--
    9047: A-(----)-TG-DFGR--
1 unique results for '' in 25ms
 1000000: 
1 unique results for 'ATGDFGR' in 77ms
 1000000: ATGDFGR

从字符串中随机选择特定的子序列

Randomly selecting specific subsequence from string

c++

string

random

完整列表