I am interested in writing a function generate(n,m) which exhaustively generating strings of length n(n-1)/2 consisting solely of +/- characters. These strings will then be transformed into an n × n symmetric (-1,0,1)-matrix in the following way:
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 the given string represents the upper-right triangle of the matrix, which is then reflected to generate the rest of it.
Question: How can I generate all
+/-strings such that the resulting matrix has preciselym-1's per row?
For example, generate(5,3) will give all strings of length 5(5-1)/2 = 10 such that each row contains precisely three -1's.
I'd appreciate any help with constructing such an algorithm.
This is the logic to generate every matrix for a given n and m. It's a bit convoluted, so I'm not sure how much faster than brute force an implementation would be; I assume the difference will become more pronounced for larger values.
(The following will generate an output of zeros and ones for convenience, where zero represents a plus and a one represents a minus.)
A square matrix where each row has m ones translates to a triangular matrix where these folded row/columns have m ones:
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
Each of these groups overlaps with all the other groups; choosing values for the first k groups means that the vertical part of group k+1 is already determined.
We start by putting the number of ones required per row on the diagonal; e.g. for (5,2) that is:
2 . . . .
2 . . .
2 . .
2 .
2
Then we generate every bit pattern with m ones for the first group; there are (n-1 choose m) of these, and they can be efficiently generated, e.g. with Gosper's hack.
(4,2) -> 0011 0101 0110 1001 1010 1100
For each of these, we fill them in in the matrix, and subtract them from the numbers of required ones:
X 0 0 1 1
2 . . .
2 . .
1 .
1
and then recurse with the smaller triangle:
2 . . .
2 . .
1 .
1
If we come to a point where some of the numbers of required ones on the diagonal are zero, e.g.:
2 . . .
1 . .
0 .
1
then we can already put a zero in this column, and generate the possible bit patterns for fewer columns; in the example that would be (2,2) instead of (3,2), so there's only one possible bit pattern: 11. Then we distribute the bit pattern over the columns that have a non-zero required count under them:
2 . 0 . X 1 0 1
1 . . 0 . .
0 . 0 .
1 0
However, not all possible bit patterns will lead to valid solutions; take this example:
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
where we end up with a row that requires another 2 ones while both columns can no longer take any ones. The way to spot this situation is by looking at the list of required ones per column that is created by each option in the penultimate step:
pattern required
0 1 1 -> 2 0 0
1 0 1 -> 1 1 0
1 1 0 -> 1 0 1
If the first value in the list is x, then there must be at least x non-zero values after it; which is false for the first of the three options.
(There is room for optimization here: in a count list like 1,1,0,6,0,2,1,1 there are only 2 non-zero values before the 6, which means that the 6 will be decremented at most 2 times, so its minimum value when it becomes the first element will be 4; however, there are only 3 non-zero values after it, so at this stage you already know this list will not lead to any valid solutions. Checking this would add to the code complexity, so I'm not sure whether that would lead to an improvement in execution speed.)
So the complete algorithm for (n,m) starts with:
- 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.
and the recursive steps after that are:
- 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.
Here's a code snippet as a proof of concept; in a serious language, and using integers instead of arrays for the bitmaps, this should be much faster:
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(["+ ", "− "][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);Here are the number of results and the number of recursions for values of n up to 10, so you can compare them to check correctness. When n and m are both odd numbers, there are no valid results; this is calculated correctly, except in the case of (3,1); it is of course easy to catch these cases and return immediately.
(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