如何将二进制序列分解为周期性二进制序列？

问题概述 #

给定二进制序列（示例：[1,1,1,1,0,1,1,1,0,1]），需将其分解为若干周期序列的按位或运算结果，要求每个分解出的序列满足：

• 周期尽可能小
• 偏移量小于自身周期（偏移量指序列起始位置对应的周期偏移）

适用算法思路 #

这类问题可通过贪心+周期检测的策略实现，相比傅里叶级数频域分析，该方法更直接高效：

1. 先标记序列中所有未被覆盖的1位置；
2. 对每个未被覆盖的1位置，尝试从最小可能的周期（从1开始）出发，计算该周期下对应偏移（位置%周期）的周期序列能覆盖的未被覆盖1数量；
3. 选择能覆盖最多未被覆盖1的最小周期序列，将其加入分解集合，并标记所有被该序列覆盖的1为已覆盖；
4. 重复上述步骤，直到所有1都被覆盖。

C++ 实现示例 #

#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>

using namespace std;

// 存储分解得到的周期和偏移
struct PeriodicSeq {
    int period;
    int offset;
};

// 计算给定周期和偏移的序列能覆盖的未被覆盖的1的数量
int countCovered(const vector<int>& seq, const unordered_set<int>& uncovered, int period, int offset) {
    int count = 0;
    int n = seq.size();
    for (int i = offset; i < n; i += period) {
        if (uncovered.count(i)) {
            count++;
        }
    }
    return count;
}

// 执行分解
vector<PeriodicSeq> decomposeBinarySeq(const vector<int>& seq) {
    vector<PeriodicSeq> result;
    int n = seq.size();
    unordered_set<int> uncovered;

    // 初始化未覆盖的1的位置
    for (int i = 0; i < n; ++i) {
        if (seq[i] == 1) {
            uncovered.insert(i);
        }
    }

    while (!uncovered.empty()) {
        int bestPeriod = -1;
        int bestOffset = -1;
        int maxCover = 0;

        // 遍历所有未被覆盖的位置，尝试寻找最优周期和偏移
        for (int pos : uncovered) {
            // 尝试从最小的周期开始（最小为1，最大为pos+1，因为偏移<周期）
            for (int period = 1; period <= pos + 1; ++period) {
                int offset = pos % period;
                int cover = countCovered(seq, uncovered, period, offset);
                // 优先选择覆盖数多的，若覆盖数相同则选周期更小的
                if (cover > maxCover || (cover == maxCover && period < bestPeriod)) {
                    maxCover = cover;
                    bestPeriod = period;
                    bestOffset = offset;
                }
            }
        }

        // 将找到的最优序列加入结果
        result.push_back({bestPeriod, bestOffset});

        // 标记该序列覆盖的位置为已覆盖
        for (int i = bestOffset; i < n; i += bestPeriod) {
            if (uncovered.count(i)) {
                uncovered.erase(i);
            }
        }
    }

    return result;
}

int main() {
    vector<int> seq = {1,1,1,1,0,1,1,1,0,1};
    vector<PeriodicSeq> decomposition = decomposeBinarySeq(seq);

    cout << "分解结果：" << endl;
    for (const auto& ps : decomposition) {
        cout << "周期：" << ps.period << "，偏移：" << ps.offset << endl;
    }

    return 0;
}

代码说明 #

• 该实现通过贪心策略每次选择覆盖最多未被覆盖1的最小周期序列，确保分解出的序列周期尽可能小；
• countCovered函数用于计算指定周期和偏移的序列能覆盖的未处理1数量；
• 最终输出的分解结果会符合题目要求的周期最小、偏移小于周期的条件。

内容的提问来源于stack exchange，提问作者bio grisha