c++ - 将字符串重新排序为没有连续相同字符的字符串

Question

标题是不言自明的，但这里有几个例子:

• aabbcc -> abcabc
• abcabc -> cbabac
• cbacbaca -> bcacacba

我认为 std::random_shuffle(myString.begin(), myString.end()) 会很有趣，因为它永远不会通过不同的调用进行相同的重新排序，但它需要当生成的字符串在连续位置没有相似字符时循环。是否有更合乎逻辑的方式来进行重新排序，或任何其他功能做类似的事情？

注意:重新排序不需要随机进行。只要相同的字符不在连续的位置，就可以使用排序功能。

更新:如评论中所述...是的，random_shuffle 可以连续多次返回相同的字符串顺序。假设采用上述方法，next_permutation 会更合适。

Answer 1

首先请注意，解决方案并不总是存在。当且仅当出现次数最多的元素不超过 (n+1)/2 时，它才存在。

因此很容易检查解是否存在。如果它存在，那么下面的代码将找到它

bool cmpBySecond(const std::pair<char, int>& a, const std::pair<char, int>& b) {
    if (a.second == b.second) return a.first < b.first;
    return a.second < b.second;
}

std::string reorder(const std::string& input) {
    std::map<char, int> cnt;
    for (auto& c: input) cnt[c]++;
    auto items = std::vector<std::pair<char, int>>(cnt.begin(), cnt.end());
    std::sort(items.begin(), items.end(), cmpBySecond);
    std::reverse(items.begin(), items.end());
    // now we have chars with occurencies counts in descending order
    std::string result(input);
    int pos = 0;
    for (auto& it: items) {
        char c = it.first;
        int times = it.second;
        for (int i = 0; i < times; ++i) {
            result[pos] = c;
            pos += 2;
            if (pos >= result.size()) pos = 1;
        }
    }
    return result;
}

超越它的想法是分布最频繁的元素，然后用其余元素填补空白。

还有一些测试的相同代码 here .