生成具有特定 属性 的 +/-s 字符串的算法

Algorithm for generating strings of +/-s with a specific property

我有兴趣编写一个函数 generate(n,m),它可以详尽地生成长度为 n(n-1)/2 且仅由 +/- 个字符组成的字符串。然后这些字符串将按以下方式转换为 n × n 对称 (-1,0,1)-矩阵:

toTriangle["+--+-+-++-"]  

{{1, -1, -1, 1}, {-1, 1, -1}, {1, 1}, {-1}}
toMatrix[%, 0] // MatrixForm

             | 0  1 -1 -1  1 |  
             | 1  0 -1  1 -1 |  
matrixForm = |-1 -1  0  1  1 |  
             |-1  1  1  0 -1 |
             | 1 -1  1 -1  0 |  

因此,给定的字符串表示矩阵的右上三角形,然后将其反射以生成其余部分。

Question: How can I generate all +/- strings such that the resulting matrix has precisely m -1's per row?

例如,generate(5,3) 将给出长度为 5(5-1)/2 = 10 的所有字符串,使得每一行恰好包含三个 -1。

对于构建此类算法的任何帮助,我将不胜感激。

我怀疑您是否真的想要大 n,m 值的所有变体 - 它们的数量非常大。

这道题等同于m-正则图的生成(注意,如果我们把所有的1都换成0,把所有的-1都换成1——我们可以看到图的邻接矩阵。正则图——所有顶点的度都相等到米)。

Here we can see that number of (18,4) regular graphs is about 10^9 and rises fast with n/m values. Article contains link 编程 genreg 用于生成此类图形。 FTP link 代码和可执行文件对我不起作用 - 可能太旧了。

更新: Here is 另一个 link 来源(虽然是 1996 年而不是论文的 1999 年)

描述了生成一个正则图实例的简单方法here

对于较小的 n/m 值,您还可以尝试暴力破解:用 m 个填充第一行(有 C(n,m) 个变体,对于每个变体,在第二行中填充空闲位置,并且等等)

这是为给定的 n 和 m 生成每个矩阵的逻辑。这有点令人费解,所以我不确定实施会比蛮力快多少;我假设对于较大的值,差异会变得更加明显。

(下面为了方便会生成0和1的输出,其中0代表正,1代表负)

每行有 m 个的方阵转换为三角矩阵,其中这些折叠 row/columns 有 m 个:

x 0 1 0 1    x 0 1 0 1    0          1        0      1
0 x 1 1 0                 x 1 1 0    1        1      0
1 1 x 0 0                            x 0 0    0      0
0 1 0 x 1                                     x 1    1
1 0 0 1 x                                            x

这些组中的每一个都与所有其他组重叠;选择前 k 组的值意味着 k+1 组的垂直部分已经确定。

我们首先将每行所需的数量放在对角线上;例如对于 (5,2) 即:

2 . . . .
  2 . . .
    2 . .
      2 .
        2

然后我们为第一组生成每个位模式,其中m个1;其中有 (n-1 choose m) 个,并且可以有效地生成它们,例如使用 Gosper 的 hack。

(4,2)  ->  0011  0101  0110  1001  1010  1100  

对于其中的每一个,我们将它们填入矩阵,然后从所需数量中减去它们:

X 0 0 1 1
  2 . . .
    2 . .
      1 .
        1

然后用较小的三角形递归:

2 . . .
  2 . .
    1 .
      1

如果我们到达某个点,其中对角线上的某些所需数字为零,例如:

2 . . .
  1 . .
    0 .
      1

那么我们已经可以在这一列中放置一个零,并为更少的列生成可能的位模式;在示例中是 (2,2) 而不是 (3,2),因此只有一种可能的位模式:11。然后我们将位模式分布在其下具有非零所需计数的列上:

2 . 0 .    X 1 0 1
  1 . .      0 . .
    0 .        0 .
      1          0

但是,并非所有可能的位模式都会导致有效的解决方案;举个例子:

2 . . . .    X 0 0 1 1
  2 . . .      2 . . .    2 . . .    X 0 1 1
    2 . .        2 . .      2 . .      2 . .    2 . .
      2 .          1 .        1 .        0 .      0 .
        2            1          1          0        0

我们最终得到一行需要另外 2 个,而两列都不能再接受任何一个。发现这种情况的方法是查看倒数第二步中每个选项创建的每列所需列表:

pattern    required
 0 1 1  ->  2 0 0
 1 0 1  ->  1 1 0
 1 1 0  ->  1 0 1

如果列表中的第一个值是x,那么它后面必须至少有x个非零值;对于三个选项中的第一个,这是错误的。

(这里有优化的空间:在像1,1,0,6,0,2,1,1这样的计数列表中,6之前只有2个非零值,也就是说6最多减1 2 次,所以当它成为第一个元素时它的最小值将是 4;但是,它后面只有 3 个非零值,所以在这个阶段你已经知道这个列表不会导致任何有效的解决方案。检查这个会增加了代码的复杂性,所以我不确定这是否会导致执行速度的提高。)

所以 (n,m) 的完整算法开始于:

  • Create an n-sized list with all values set to m (count of ones required per group).
  • Generate all bit patterns of size n-1 with m ones; for each of these:
    • Subtract the pattern from a copy of the count list (without the first element).
    • Recurse with the pattern and the copy of the count list.

之后的递归步骤是:

  • Receive the sequence so far, and a count list.
  • The length of the count list is n, and its first element is m.
  • Let k be the number of non-zero values in the count list (without the first element).
  • Generate all bit pattern of size k with m ones; for each of these:
    • Create a 0-filled list sized n-1.
    • Distribute the bit pattern over it, skipping the columns with a zero count.
    • Add the value list to the sequence so far.
    • Subtract the value list from a copy of the count list (without the first element).
    • If the first value in the copy of the count list is greater than the number of non-zeros after it, skip this pattern.
    • At the deepest recursion level, store the sequence, or else:
    • Recurse with the sequence so far, and the copy of the count list.

这是一个代码片段作为概念证明;在严肃的语言中,并使用整数而不是位图数组,这应该快得多:

function generate(n, m) {
    // if ((n % 2) && (m % 2)) return; // to catch (3,1)
    var counts = [], pattern = [];
    for (var i = 0; i < n - 1; i++) {
        counts.push(m);
        pattern.push(i < m ? 1 : 0);
    }
    do {
        var c_copy = counts.slice();
        for (var i = 0; i < n - 1; i++) c_copy[i] -= pattern[i];
        recurse(pattern, c_copy);
    }
    while (revLexi(pattern));
}

function recurse(sequence, counts) {
    var n = counts.length, m = counts.shift(), k = 0;
    for (var i = 0; i < n - 1; i++) if (counts[i]) ++k;
    var pattern = [];
    for (var i = 0; i < k; i++) pattern.push(i < m ? 1 : 0);
    do {
        var values = [], pos = 0;
        for (var i = 0; i < n - 1; i++) {
            if (counts[i]) values.push(pattern[pos++]);
            else values.push(0);
        }
        var s_copy = sequence.concat(values);
        var c_copy = counts.slice();
        var nonzero = 0;
        for (var i = 0; i < n - 1; i++) {
            c_copy[i] -= values[i];
            if (i && c_copy[i]) ++nonzero;
        }
        if (c_copy[0] > nonzero) continue;
        if (n == 2) {
            for (var i = 0; i < s_copy.length; i++) {
                document.write(["+ ", "&minus; "][s_copy[i]]);
            }
            document.write("<br>");
        }
        else recurse(s_copy, c_copy);
    }
    while (revLexi(pattern));
}

function revLexi(seq) { // reverse lexicographical because I had this lying around
    var max = true, pos = seq.length, set = 1;
    while (pos-- && (max || !seq[pos])) if (seq[pos]) ++set; else max = false;
    if (pos < 0) return false;
    seq[pos] = 0;
    while (++pos < seq.length) seq[pos] = set-- > 0 ? 1 : 0;
    return true;
}

generate(5, 2);


这里是结果数和递归数 n 到 10,所以你可以比较它们来检查正确性。当n和m都是奇数时,没有有效结果;这是正确计算的,除了 (3,1) 的情况;当然很容易立即发现这些情况并return。

 (n,m)            results        number of recursions

 (4,0)  (4,3)           1            2            2
 (4,1)  (4,2)           3            6            7

 (5,0)  (5,4)           1            3            3
 (5,1)  (5,3)           0           12           20
 (5,2)                 12           36

 (6,0)  (6,5)           1            4            4
 (6,1)  (6,4)          15           48           76
 (6,2)  (6,3)          70          226          269

 (7,0)  (7,6)           1            5            5
 (7,1)  (7,5)           0           99          257
 (7,2)  (7,4)         465        1,627        2,313
 (7,3)                  0        3,413

 (8,0)  (8,7)           1            6            6
 (8,1)  (8,6)         105          422        1,041
 (8,2)  (8,5)       3,507       13,180       23,302
 (8,3)  (8,4)      19,355       77,466       93,441

 (9,0)  (9,8)           1            7            7
 (9,1)  (9,7)           0          948        4,192
 (9,2)  (9,6)      30,016      119,896      270,707
 (9,3)  (9,5)           0    1,427,457    2,405,396
 (9,4)          1,024,380    4,851,650

(10,0) (10,9)           1            8            8
(10,1) (10,8)         945         4440        18930
(10,2) (10,7)     286,884    1,210,612    3,574,257
(10,3) (10,6)  11,180,820   47,559,340   88,725,087
(10,4) (10,5)  66,462,606  313,129,003  383,079,169

用 Wolfram Mathematica 编写。

generate[n_, m_] := Module[{},
  x = Table[StringJoin["i", ToString[i], "j", ToString[j]],
    {j, 1, n}, {i, 2, n}];
  y = Transpose[x];
  MapThread[(x[[#, ;; #2]] = y[[#, ;; #2]]) &,
   {-Range[n - 1], Reverse@Range[n - 1]}];
  Clear @@ Names["i*"];
  z = ToExpression[x];
  Clear[s];
  s = Reduce[Join[Total@# == m & /@ z,
     0 <= # <= 1 & /@ Union[Flatten@z]],
    Union@Flatten[z], Integers];
  Clear[t, u, v];
  Array[(t[#] = 
      Partition[Flatten[z] /.
         ToRules[s[[#]]], n - 1] /.
       {1 -> -1, 0 -> 1}) &, Length[s]];
  Array[Function[a,
    (u[a] = StringJoin[Flatten[MapThread[
          Take[#, 1 - #2] &,
          {t[a], Reverse[Range[n]]}]] /.
        {1 -> "+", -1 -> "-"}])], Length[s]];
  Array[Function[a,
    (v[a] = MapThread[Insert[#, 0, #2] &,
       {t[a], Range[n]}])], Length[s]]]

Timing[generate[9, 4];]
Length[s]
{202.208, Null}
1024380

程序生成 1,024,380 个解需要 202 秒。例如。最后一个

u[1024380]
----++++---++++-+-+++++-++++--------
v[1024380]
 0  -1  -1  -1  -1   1   1   1   1   
-1   0  -1  -1  -1   1   1   1   1   
-1  -1   0  -1   1  -1   1   1   1   
-1  -1  -1   0   1   1  -1   1   1   
-1  -1   1   1   0   1   1  -1  -1   
 1   1  -1   1   1   0  -1  -1  -1   
 1   1   1  -1   1  -1   0  -1  -1   
 1   1   1   1  -1  -1  -1   0  -1   
 1   1   1   1  -1  -1  -1  -1   0   

和前十个字符串

u /@ Range[10]
++++----+++----+-+-----+----++++++++
++++----+++----+-+------+--+-+++++++
++++----+++----+-+-------+-++-++++++
++++----+++----+--+---+-----++++++++
++++----+++----+---+--+----+-+++++++
++++----+++----+----+-+----++-++++++
++++----+++----+--+-----+-+--+++++++ 
++++----+++----+--+------++-+-++++++
++++----+++----+---+---+--+--+++++++