All geek questions in one place

Algorithm for generating lines +/- s with a specific property

I am interested in writing a function generate(n,m)that exhaustively generates lines of length n(n-1)/2consisting entirely of +/ characters -. Then these rows are converted into an n × n symmetric (-1,0,1) -matrix as follows:

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 |

Thus, this row represents the upper right triangle of the matrix, which is then reflected to generate the rest.

Question . How can I generate all rows +/ -so that the resulting matrix has exactly m-1 for each row?

For example, it generate(5,3)will give all lines of length 5(5-1)/2 = 10so that each line contains exactly three -1.

I would be grateful for the help in building such an algorithm.

+4
3

n m. , , , , ; , .

( , , .)

, m , , / 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 ; (n-1 m) , , . Gosper.

(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. , :/p >

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 2 , , , 4, 3 , , - . , , .)

, (n, m) :

  • n- , m ( , ).
  • n-1 m-; :
    • ( ).
    • .

:

  • .
  • n, - m.
  • k - ( ).
  • k m-; :
    • 0- n-1.
    • , .
    • .
    • ( ).
    • , .
    • , :
    • .

; , :

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); , .

 (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
+3

, n, m - .

m- (, 1 -1 1, . - m).

, (18,4) 10 ^ 9 n/m , genreg, . FTP - , .

: ( 1996 1999)

.

n/m : m ( C (n, m) ..)

+2

Written in 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

The program takes 202 seconds to generate 1,024,380 solutions. For instance. last

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

and the first ten lines

u /@ Range[10]

++++----+++----+-+-----+----++++++++
++++----+++----+-+------+--+-+++++++
++++----+++----+-+-------+-++-++++++
++++----+++----+--+---+-----++++++++
++++----+++----+---+--+----+-+++++++
++++----+++----+----+-+----++-++++++
++++----+++----+--+-----+-+--+++++++ 
++++----+++----+--+------++-+-++++++
++++----+++----+---+---+--+--+++++++
+1
source

Source: https://habr.com/ru/post/1686146/

More articles:


All Articles