如何生成满足均匀成对采样条件的小规模比特字符串集合

你要找的是两两平衡的二进制字符串集合，这类问题在组合设计领域已有成熟研究，核心要求是集合内任意两个比特位置上，00、01、10、11四种组合的出现次数完全相等。以下是几种符合「集合大小≤2N」要求的构造方法：

方法1：全1串+单位矩阵行（适用于N≥3，集合大小=N+1） #

对于N比特字符串，直接构造包含：

• 全1字符串：11...1（共N个1）
• 单位矩阵的每一行：即第k个字符串仅第k位为1，其余位为0（比如3比特的001、010、100）

这类集合中任意两位置的四种组合恰好各出现1次，完全满足平衡要求。集合大小为N+1，N≥3时必然≤2N，符合规模限制。

方法2：互补对+交错翻转（适用于偶数N，集合大小=2N） #

当N为偶数时，按以下步骤构造：

1. 先加入全1串11...1和它的补串全0串00...0
2. 生成多组互补的交错字符串：
   比如N=4时的0101与1010、1001与0110、1100与0011，每一组都是互补关系，且是按位交错翻转的结果

这类集合总大小为2N，任意两位置的四种组合各出现2次（总规模除以4），满足平衡条件。

方法3：哈达玛矩阵行子集 #

哈达玛矩阵是一种特殊的二进制矩阵，任意两行的内积相等。取4阶或更高阶哈达玛矩阵的前N+1行，转换成二进制字符串后，即可得到符合要求的集合。比如你给出的3比特例子，恰好是4阶哈达玛矩阵的行转换而来。

核心性质提示 #

• 满足条件的集合大小M必须是4的倍数，因为四种组合要均分出现次数。因此N=2时最小规模为4（所有2比特字符串），N=3时最小为4，N=4时最小为8。
• 当N为奇数时，最小可行规模为N+1（只要N+1是4的倍数，比如N=3时4是4的倍数）；当N为偶数时，2N是稳定可行的规模。

内容的提问来源于stack exchange，提问作者Paul Nation