3

我正在玩一些Hadamard 矩阵的变体。我想生成满足这些要求的所有 n位二进制字符串：

  1. 您可以假设n是 4 的倍数。
  2. 第一个字符串是 0 n。
    → 一个全 0 的字符串。
  3. 其余字符串按字母顺序排序。
    → 0 在 1 之前。
  4. 每两个不同的n位字符串具有汉明距离 n/2。
    → 两个不同的n位字符串恰好在 n/2 个位置一致，而在恰好n /2 个位置不一致。
  5. 由于上述条件，除第一个字符串之外的每个字符串都必须具有相同数量的 0 和 1。
    → 除第一个字符串之外的每个字符串都必须有n/2个 1 和n/2 个零。
  6. （更新）所有n位字符串都以 . 开头0。

例如，这是我在n=4时想要的列表。

0000
0011
0101
0110

您可以很容易地看到每两个不同的行具有汉明距离n/2 = 4/2 = 2，并且该列表也满足所有其他要求。

请注意，我想生成所有此类字符串。我的算法在终止之前可能只输出三个字符串0000,0011和。0101此列表满足上述所有要求，但未满足0110.

  1. 生成此类集合的好方法是什么？
    首选 python 伪代码，但任何高级描述都可以。
  2. 对于给定的n ，此类字符串的最大数量是多少？例如，当n=4时，此类字符串的最大数量恰好是 4。我想知道这个上限是否有任何封闭形式的解决方案。

谢谢。

4

1 回答 1

0

要回答问题 1，

从一串n零（我们称之为它s0）和一串n/2零后跟n/21（称之为它s1）开始，生成下一个排列（称之为它p）：

scan string from right to left
replace first occurrence of "01" with "10"
(unless the first occurrence is at the string start)
move all "1"'s that are on the right of the "01" to the string end
return replaced string

使用排列生成顺序来记录添加到集合中的排列。如果与当前集合中的每个数字在xoring中设置的位数为 n/2，则添加到列表中；否则，如果在ing中设置的位数为 n/2且未记录，则使用 , 开始新的集合搜索；并且仅作为 xor 测试的附加条件（由于主要搜索将检查所有排列，因此该集合不需要生成其他集合）。用于生成下一个排列。ppxorps1ps0s1pp

于 2013-09-19T11:07:26.817 回答