递归算法未能在规定时间内完成测试
Recursive algorithm fails to complete tests in allotted time
我正在做一个需要二元断层扫描算法的测试。提供了一组 38 个测试值来测试正确性，但也有 1 CPU 秒的时间限制来完成所有测试。问题如下：
如果存在一个m×n矩阵A，每个元素要么为0要么为1，则输出“是”，使得
否则输出“No”。
对于每个测试，提供了 2 个数组：
- r（矩阵中每一行的总和）
- c（矩阵各列之和）
等式中：
- m是r数组的长度，其中1 <= m
- n是c数组的长度，其中n <= 1000
- ri 是 r 的一个元素，其中 0 <= ri <= n
- cj 是 c 的一个元素，其中 0 <= cj <= m
一个"Yes"例子
米=3；
n = 4;
r = [2, 3, 2];
c = [1, 1, 3, 2];
一个"No"例子
米=3；
n = 3;
r = [0, 0, 3];
c = [0, 0, 3];
我有一个似乎可以给出正确答案的解决方案，但在超过 CPU 时间的 1 秒之前，它只能进行 12 / 38 次测试。
我最初在 ES5 中编写代码，然后返回并转换为 ES3 以尝试从中获得更多性能。 （最初作为 ES5 管理 9 个测试）。似乎我可以对当前算法做很多事情来提高性能（除非我弄错了）。这使我相信我的算法有问题，必须有更快的算法来执行此操作。我读了很多书试图找到一个，结果头疼 :)
所以我求助于社区，看看是否有人可以提出比我目前使用的更快的算法。
'use strict';
const ZEROS = (function (seed) {
let string = seed;
for (let i = 0; i < 19; i += 1) {
string += seed;
}
return string;
}('00000000000000000000000000000000000000000000000000'));
const ZEROSLEN = ZEROS.length;
const permutate = function (n, ri) {
const result = [];
const memoize = {};
let count = 0;
do {
const bin = count.toString(2);
if (ZEROSLEN + bin.length > ZEROSLEN + n) {
break;
}
if (!memoize[bin] && (bin.split('1').length - 1) === ri) {
const string = (ZEROS + bin).slice(-n);
const sLen = string.length;
const perm = new Array(sLen);
for (let i = sLen - 1; i >= 0; i -= 1) {
perm[i] = +string[i];
}
memoize[bin] = result.push(perm);
}
count += 1;
} while (count);
return result;
};
const getMatrixSum = function (n, matrix) {
const mLength = matrix.length;
const rows = new Array(mLength);
const a = new Array(n);
const last = mLength - 1;
for (let x = n - 1; x >= 0; x -= 1) {
for (let y = last; y >= 0; y -= 1) {
rows[y] = matrix[y][x];
}
let sum = 0;
for (let i = rows.length - 1; i >= 0; i -= 1) {
sum += rows[i];
}
a[x] = sum;
}
return a;
};
const isEqual = function (a, b) {
const length = a.length;
if (length !== b.length) {
return false;
}
for (let i = length - 1; i >= 0; i -= 1) {
if (a[i] !== b[i]) {
return false;
}
}
return true;
};
const addRow = function (i, prev, r, c, result) {
if (result) {
return result;
}
const n = c.length;
const ri = r[i];
if (ri < 0 || ri > n) {
throw new RangeError('ri out of range');
}
const p = permutate(n, ri);
const m = r.length;
const rsLast = m - 1;
const nextI = i + 1;
for (let x = p.length - 1; x >= 0; x -= 1) {
const permutation = p[x];
const next = prev.slice();
next.push(permutation);
const sums = getMatrixSum(n, next);
if (i < rsLast) {
let memo = 0;
for (let j = sums.length - 1; j >= 0; j -= 1) {
if (sums[j] > c[j]) {
memo += 1;
}
}
if (!memo && addRow(nextI, next, r, c, result)) {
return true;
}
} else if (isEqual(sums, c)) {
return true;
}
}
return false;
};
const isSolvable = function (r, c) {
const m = r.length;
const n = c.length;
if (m < 1 || n > 1000) {
throw new Error('Bad data');
}
for (let j = n; j >= 0; j -= 1) {
const cj = c[j];
if (cj < 0 || cj > m) {
throw new RangeError('cj out of range');
}
}
return addRow(0, [], r, c, false) ? 'Yes' : 'No';
};
console.log(isSolvable([2, 3, 2], [1, 1, 3, 2]));
console.log(isSolvable([0, 0, 3], [0, 0, 3]));
值得注意的是，正在对 SpiderMonkey 版本 JavaScript-C24.2.0
进行 运行 测试
参考文献：
我没有为我的测试准备好这个，但我在活动后发现了一个更有效的算法。
'use strict';
const sortNumber = function (a, b) {
return b - a;
};
const isSolvable = function (r, c) {
const m = r.length;
const n = c.length;
if (m < 1 || n > 1000) {
throw new Error('Bad data');
}
for (let j = n; j >= 0; j -= 1) {
const cj = c[j];
if (cj < 0 || cj > m) {
throw new RangeError('cj out of range');
}
}
while (r.length) {
c.sort(sortNumber);
const ri = r.pop();
if (ri < 0 || ri > n) {
throw new RangeError('ri out of range');
}
if (ri) {
if (!c[ri - 1]) {
return 'No';
}
for (let j = ri - 1; j >= 0; j -= 1) {
c[j] -= 1;
}
}
}
for (let j = n - 1; j >= 0; j -= 1) {
if (c[j]) {
return 'No';
}
}
return 'Yes';
};
console.log(isSolvable([2, 3, 2], [1, 1, 3, 2]));
console.log(isSolvable([0, 0, 3], [0, 0, 3]));
由于排列屈服于蛮力，因此在开发与此类似的算法时，它们应该是最后的手段。大多数时候不需要它们。
正如我在上面评论的那样，我觉得一种策略可能是首先对 r 和 c 数组进行降序排序，然后从较大的数组开始。我还没有时间实现一个 JS 代码来解决这个问题，所以我还没有机会彻底测试。请看一下，如果您发现缺陷请指出。
在下面的算法可视化表示中，我们尝试 r = [1,3,1,3] 和 c = [3,2,1,2]。 X 表示占用的单元格，红点表示不可触摸的单元格，而空的显然是空闲单元格。因此，在表示单元格的实际算法中，我们需要一种数据类型，如 {value: false, avail: false} 表示红点，而 {value: false, avail: true} 表示自由 space。或者为了节省 space 和速度，您可以使用 0b00 等数据类型表示红点，0b01 表示免费 space 和 0b1X 表示占用（这里的 X 表示不在乎）细胞。
注意： 值得一提的是我们处理 c[0] 的第 3 步。插入三个 X 后，我们必须检查 X 占用的行以更新这些行中空单元格的状态。在这种情况下，对于 r[2]，所有空单元格都变得不可触摸。
编辑：
嗯..好吧，因为我们不需要在类似结构的二维数组中构造解决方案，而只需要回答所提供的数据是否有意义，我想出了另一个更简单的想法本质上是基于上述方法。我真的不认为它能比这更快。它在大约 50 毫秒内解决了 999 x 1000 板的问题。
让我们开始吧。
- 输入是
r = [2, 3, 2]; c = [1, 1, 3, 2]; 然而这里的一个重要条件是 c 和 r 数组的总和应该是相同的数字 。我们可以在代码的开头简单地检查它或保留它，执行以下步骤，如果它们通过检查，则仅当 c 全部为 0 时。下面的代码更喜欢后一种方法。
- 排序
r 如此降序； r = [3, 2, 2]; c = [1, 1, 3, 2];
- 尝试将
r[0]（第一种情况下为 3）个 c 的许多非零元素减 1。现在 c 变为 [0, 0, 2, 2]。如果失败则不再尝试 return false.
- 现在我们已经完成了行
r[0]，当 r.length 大于 0 且 bool 参数 b 为 [=40 时，递归调用带有 r = [2, 2]; c = [0, 0, 2, 2]; 的函数=].下一次调用将是 r = [2]; c = [0, 0, 1, 1];，最后是 r = []; c = [0, 0, 0, 0];
- 如果最终调用空
r 的递归调用，则检查 b 是 true 并且 c 的所有项目都是 0。 (b && cs.every(n => !n)).
我相信这很好，但由于我没有您的测试用例，您可以尝试一下。我相信它会通过时间测试。这是最简单的代码。我在这里测试 rs = [7,3,5,4,6,2,8] 和 cs = [7,1,6,3,4,5,2,7]。看起来像；
71634527
7 x xxxxxx
3 x x x
5 x x xx x
4 x x x x
6 x xxxx x
2 x x
8 xxxxxxxx
function nonogram(rs,cs){
function runner(rs,cs, b = true){//console.log(rs,cs,b)
return b && rs.length ? runner(rs.slice(1), // rows argument
cs.map(e => rs[0] ? e ? (b = !--rs[0], e-1) // cols argument
: e
: e),
b) // bool argument
: b && cs.every(n => !n);
}
return runner(rs.sort((a,b) => b-a), cs);
}
var rs = [7,3,5,4,6,2,8],
cs = [7,1,6,3,4,5,2,7],
result;
console.time("test");
result = nonogram(rs,cs);
console.timeEnd("test");
console.log(result);
我正在做一个需要二元断层扫描算法的测试。提供了一组 38 个测试值来测试正确性，但也有 1 CPU 秒的时间限制来完成所有测试。问题如下：
如果存在一个m×n矩阵A，每个元素要么为0要么为1，则输出“是”，使得
否则输出“No”。
对于每个测试，提供了 2 个数组：
- r（矩阵中每一行的总和）
- c（矩阵各列之和）
等式中：
- m是r数组的长度，其中1 <= m
- n是c数组的长度，其中n <= 1000
- ri 是 r 的一个元素，其中 0 <= ri <= n
- cj 是 c 的一个元素，其中 0 <= cj <= m
一个"Yes"例子
米=3； n = 4; r = [2, 3, 2]; c = [1, 1, 3, 2];
一个"No"例子
米=3； n = 3; r = [0, 0, 3]; c = [0, 0, 3];
我有一个似乎可以给出正确答案的解决方案，但在超过 CPU 时间的 1 秒之前，它只能进行 12 / 38 次测试。
我最初在 ES5 中编写代码，然后返回并转换为 ES3 以尝试从中获得更多性能。 （最初作为 ES5 管理 9 个测试）。似乎我可以对当前算法做很多事情来提高性能（除非我弄错了）。这使我相信我的算法有问题，必须有更快的算法来执行此操作。我读了很多书试图找到一个，结果头疼 :)
所以我求助于社区，看看是否有人可以提出比我目前使用的更快的算法。
'use strict';
const ZEROS = (function (seed) {
let string = seed;
for (let i = 0; i < 19; i += 1) {
string += seed;
}
return string;
}('00000000000000000000000000000000000000000000000000'));
const ZEROSLEN = ZEROS.length;
const permutate = function (n, ri) {
const result = [];
const memoize = {};
let count = 0;
do {
const bin = count.toString(2);
if (ZEROSLEN + bin.length > ZEROSLEN + n) {
break;
}
if (!memoize[bin] && (bin.split('1').length - 1) === ri) {
const string = (ZEROS + bin).slice(-n);
const sLen = string.length;
const perm = new Array(sLen);
for (let i = sLen - 1; i >= 0; i -= 1) {
perm[i] = +string[i];
}
memoize[bin] = result.push(perm);
}
count += 1;
} while (count);
return result;
};
const getMatrixSum = function (n, matrix) {
const mLength = matrix.length;
const rows = new Array(mLength);
const a = new Array(n);
const last = mLength - 1;
for (let x = n - 1; x >= 0; x -= 1) {
for (let y = last; y >= 0; y -= 1) {
rows[y] = matrix[y][x];
}
let sum = 0;
for (let i = rows.length - 1; i >= 0; i -= 1) {
sum += rows[i];
}
a[x] = sum;
}
return a;
};
const isEqual = function (a, b) {
const length = a.length;
if (length !== b.length) {
return false;
}
for (let i = length - 1; i >= 0; i -= 1) {
if (a[i] !== b[i]) {
return false;
}
}
return true;
};
const addRow = function (i, prev, r, c, result) {
if (result) {
return result;
}
const n = c.length;
const ri = r[i];
if (ri < 0 || ri > n) {
throw new RangeError('ri out of range');
}
const p = permutate(n, ri);
const m = r.length;
const rsLast = m - 1;
const nextI = i + 1;
for (let x = p.length - 1; x >= 0; x -= 1) {
const permutation = p[x];
const next = prev.slice();
next.push(permutation);
const sums = getMatrixSum(n, next);
if (i < rsLast) {
let memo = 0;
for (let j = sums.length - 1; j >= 0; j -= 1) {
if (sums[j] > c[j]) {
memo += 1;
}
}
if (!memo && addRow(nextI, next, r, c, result)) {
return true;
}
} else if (isEqual(sums, c)) {
return true;
}
}
return false;
};
const isSolvable = function (r, c) {
const m = r.length;
const n = c.length;
if (m < 1 || n > 1000) {
throw new Error('Bad data');
}
for (let j = n; j >= 0; j -= 1) {
const cj = c[j];
if (cj < 0 || cj > m) {
throw new RangeError('cj out of range');
}
}
return addRow(0, [], r, c, false) ? 'Yes' : 'No';
};
console.log(isSolvable([2, 3, 2], [1, 1, 3, 2]));
console.log(isSolvable([0, 0, 3], [0, 0, 3]));
值得注意的是，正在对 SpiderMonkey 版本 JavaScript-C24.2.0
进行 运行 测试参考文献：
我没有为我的测试准备好这个，但我在活动后发现了一个更有效的算法。
'use strict';
const sortNumber = function (a, b) {
return b - a;
};
const isSolvable = function (r, c) {
const m = r.length;
const n = c.length;
if (m < 1 || n > 1000) {
throw new Error('Bad data');
}
for (let j = n; j >= 0; j -= 1) {
const cj = c[j];
if (cj < 0 || cj > m) {
throw new RangeError('cj out of range');
}
}
while (r.length) {
c.sort(sortNumber);
const ri = r.pop();
if (ri < 0 || ri > n) {
throw new RangeError('ri out of range');
}
if (ri) {
if (!c[ri - 1]) {
return 'No';
}
for (let j = ri - 1; j >= 0; j -= 1) {
c[j] -= 1;
}
}
}
for (let j = n - 1; j >= 0; j -= 1) {
if (c[j]) {
return 'No';
}
}
return 'Yes';
};
console.log(isSolvable([2, 3, 2], [1, 1, 3, 2]));
console.log(isSolvable([0, 0, 3], [0, 0, 3]));
由于排列屈服于蛮力，因此在开发与此类似的算法时，它们应该是最后的手段。大多数时候不需要它们。
正如我在上面评论的那样，我觉得一种策略可能是首先对 r 和 c 数组进行降序排序，然后从较大的数组开始。我还没有时间实现一个 JS 代码来解决这个问题，所以我还没有机会彻底测试。请看一下，如果您发现缺陷请指出。
在下面的算法可视化表示中，我们尝试 r = [1,3,1,3] 和 c = [3,2,1,2]。 X 表示占用的单元格，红点表示不可触摸的单元格，而空的显然是空闲单元格。因此，在表示单元格的实际算法中，我们需要一种数据类型，如 {value: false, avail: false} 表示红点，而 {value: false, avail: true} 表示自由 space。或者为了节省 space 和速度，您可以使用 0b00 等数据类型表示红点，0b01 表示免费 space 和 0b1X 表示占用（这里的 X 表示不在乎）细胞。
注意： 值得一提的是我们处理 c[0] 的第 3 步。插入三个 X 后，我们必须检查 X 占用的行以更新这些行中空单元格的状态。在这种情况下，对于 r[2]，所有空单元格都变得不可触摸。
编辑：
嗯..好吧，因为我们不需要在类似结构的二维数组中构造解决方案，而只需要回答所提供的数据是否有意义，我想出了另一个更简单的想法本质上是基于上述方法。我真的不认为它能比这更快。它在大约 50 毫秒内解决了 999 x 1000 板的问题。
让我们开始吧。
- 输入是
r = [2, 3, 2]; c = [1, 1, 3, 2];然而这里的一个重要条件是c和r数组的总和应该是相同的数字 。我们可以在代码的开头简单地检查它或保留它，执行以下步骤，如果它们通过检查，则仅当c全部为 0 时。下面的代码更喜欢后一种方法。 - 排序
r如此降序；r = [3, 2, 2]; c = [1, 1, 3, 2]; - 尝试将
r[0]（第一种情况下为 3）个c的许多非零元素减 1。现在c变为[0, 0, 2, 2]。如果失败则不再尝试 returnfalse. - 现在我们已经完成了行
r[0]，当r.length大于 0 且 bool 参数b为 [=40 时，递归调用带有r = [2, 2]; c = [0, 0, 2, 2];的函数=].下一次调用将是r = [2]; c = [0, 0, 1, 1];，最后是r = []; c = [0, 0, 0, 0]; - 如果最终调用空
r的递归调用，则检查b是true并且c的所有项目都是0。 (b && cs.every(n => !n)).
我相信这很好，但由于我没有您的测试用例，您可以尝试一下。我相信它会通过时间测试。这是最简单的代码。我在这里测试 rs = [7,3,5,4,6,2,8] 和 cs = [7,1,6,3,4,5,2,7]。看起来像；
71634527
7 x xxxxxx
3 x x x
5 x x xx x
4 x x x x
6 x xxxx x
2 x x
8 xxxxxxxx
function nonogram(rs,cs){
function runner(rs,cs, b = true){//console.log(rs,cs,b)
return b && rs.length ? runner(rs.slice(1), // rows argument
cs.map(e => rs[0] ? e ? (b = !--rs[0], e-1) // cols argument
: e
: e),
b) // bool argument
: b && cs.every(n => !n);
}
return runner(rs.sort((a,b) => b-a), cs);
}
var rs = [7,3,5,4,6,2,8],
cs = [7,1,6,3,4,5,2,7],
result;
console.time("test");
result = nonogram(rs,cs);
console.timeEnd("test");
console.log(result);