求三个不同数的倍数的连续最小和，javascript
Find sequential smallest sums of the multiples of three different numbers, javascript
在 this post 我找到了一种算法来确定 RGB 颜色的亮度：
Luminance (standard for certain colour spaces): (0.2126*R + 0.7152*G + 0.0722*B)
我想使用这个等式，从 rgb(0,0,0) 开始，按照从最低到最高亮度的顺序生成所有 RGB 颜色，然后将它们绘制到 4096x4096 canvas。
我的问题是，由于有 1670 万种不同的组合，我无法在不使浏览器崩溃或不花费多天时间完成渲染的情况下全部生成然后对它们进行排序。所以我想找到一种方法来找到每个数字的倍数，这些数字将求和到下一个最小数字。
例如，从 0,0,0 和 rgb 开始，亮度将为 0 (0.2126*0 + 0.7152*0 + 0.0722*0 = 0)，下一个最不发光的 rgb 值将是 0,0,1，因为 0.2126*0 + 0.7152*0 + 0.0722*1 = .0722，并且没有一组倍数可以合计为较小的数字。
前 19 个连续亮度值如下（我可能遗漏了一两个，因为我手动计算了它们，但希望它有助于说明这一点）：
RGB => Luminence
0,0,0 => 0
0,0,1 => .0722
0,0,2 => .1444
1,0,0 => .2126
0,0,3 => .2166
1,0,1 => .2848
0,0,4 => .2888
1,0,2 => .357
0,0,5 => .361
2,0,0 => .4252
1,0,3 => .4292
0,0,6 => .4332
2,0,1 => .4974
1,0,4 => .5014
0,0,7 => .5054
2,0,2 => .5696
1,0,5 => .5736
0,0,8 => .5776
3,0,0 => .6378
我似乎找不到任何模式，所以我希望可能有一个等式或编码技巧可以让我找到最小的总和，高于之前的总和，是的倍数三个数字，无需暴力破解并检查每个可能的值。
编辑： 我做了一些额外的研究，看起来解决方案可能在于使用线性丢番图方程。如果我取每个小数并乘以 1000，得到 2126, 7152, & 722。然后 1 乘 1 数到 2,550,000 (2126*255 + 7152*255 + 722*255)，我可以检查每个数字以查看它是否是方程 2126r + 7152g + 722b = n 的解，其中 n 是当前计数到的数字, 和 r, g, & b 是未知数。如果我能做到这一点，我就可以计算出下一个连续亮度值的所有可能的 rgb 值，甚至不必将重复亮度值的任何值加倍，而且我只需要进行 255 万次计算而不是 1677+ 万次（每种颜色一个）。如果有人知道如何编写这个等式，或者如果有人有更好的解决方案，我将非常感激。谢谢！
您可以利用的一个事实是，序列中的每个三元组的 R、G 或 B 值仅比已输出的三元组大一个。
因此，您可以维护一个 BinaryHeap（按亮度排序），其中包含所有在 R、G 或 B 中比已经输出的三元组大 1 的三元组，并在循环中执行此操作:
- 从堆中移除最小的元素(r,g,b)
- 输出它
- 将 (r+1, g, b)、(r, g+1, b) 和 (r, g, b+1) 添加到堆中，但前提是它们是有效的三元组（所有值都小于大于或等于 255)，并且仅当它们不在堆中时。如果可以从中生成的替代三元组（在允许范围内的 r、g 或 b 中减少 1）具有比（r、g、b）更高的亮度，则三元组将不会已经在堆中。
例如，如果 (r+1, g-1, b) 的亮度高于 (r, g, b) 或 (r+1, g-)，则仅添加 (r+1, g, b) 1、b）无效。由于基于 r、g、b 计算亮度的因素是固定的，(r+1, g-1, b) 将始终具有较低的亮度，您应该只添加 (r+1, g, b) 如果 ( r+1,g-1,b)无效，即g为0时。
在pseudo-code中，规则是这样的：
function addTriplets(r, g, b)
{
if(g < 255)
pushTripletToHeap(r, g + 1, b);
if((g == 0) && (r < 255))
pushTripletToHeap(r + 1, g, b);
if((g == 0) && (r == 0) && (b < 255))
pushTripletToHeap(r, g, b + 1);
}
在开始循环之前将(0, 0, 0)三元组压入堆中，当堆为空时停止循环。
这是针对您的问题的算法（忘记了它的名字）：
该算法可以列出按某种顺序排序的所有颜色元组 {R,G,B}。在您的情况下，它是按亮度递增的：color1 < color2 <==> f(color1) < f(color2)，其中 f(color) = 0.2126*R + 0.7152*G + 0.0722*B
- 初始化：arr = [{r:0, g:0, b:0}]（最小颜色）
- 重复：
- Select min(iR)：a[iR] = {rR < 255, gR, bR}，并且 cR = {rR + 1, gR, bR} > arr[i] 对于每个 i . (Select arr 中的第一个颜色，这样如果我们将 1 添加到它的 r 分量，我们会得到一个新的颜色，它比 arr 中当前的所有颜色都大)
- iG 和 iB 类似 => 也得到 cG = {rG, gG + 1, bG} 和 cB = {rB, gB, bB + 1}
- cR、cG、cB中select最小颜色c
- 将 c 追加到数组 arr
当找不到这样的 iR、iG 或 iB 时，算法停止。
备注：
- arr 总是按升序排列的，因为每次给 arr 追加一个新颜色时，它总是更大比当前 arr.
中的每个元素
- 因为arr是升序排列的，所以我们只需要将cR/cG/cB和arr的最后一个元素进行比较即可如果它大于 arr
的每个元素
- iR、iG 和 iB 通过算法增加
- 复杂度为 O(N)，其中 N 种颜色 (2^24) ~ 16M。使用 heap-based 算法，复杂度约为 O(NlogN)。
这是我的实现（在 nodejs 6 中测试）
// use integer to avoid floating point inaccuracy
const lumixOf = {r: 2126, g: 7152, b: 722};
const maxValue = 256;
const components = ['r', 'g', 'b'];
class Color {
constructor(r, g, b, lum) {
this.r = r;
this.g = g;
this.b = b;
this.lum = lum;
}
add(component) {
const ans = new Color(this.r, this.g, this.b, this.lum);
if (++ans[component] >= maxValue) return null; // exceed 255
ans.lum += lumixOf[component];
return ans;
}
greater(color2) {
// return this.lum > color2.lum;
if (this.lum !== color2.lum) return this.lum > color2.lum;
if (this.r !== color2.r) return this.r > color2.r;
if (this.g !== color2.g) return this.g > color2.g;
return this.b > color2.b;
}
}
let a = [new Color(0, 0, 0, 0)]; // R, G, B, lumix
let index = {r: 0, g: 0, b: 0};
console.log('#0:', a[0]);
// Test: print the first 100 colors
for (let count = 1; count < 100; ++count) {
let nextColor = null;
const len = a.length;
const currentColor = a[len - 1];
components.forEach(component => {
let cIndex = index[component];
for (; cIndex < len; ++cIndex) {
const newColor = a[cIndex].add(component);
if (!newColor || !newColor.greater(currentColor)) continue;
// find the minimum next color
if (nextColor == null || nextColor.greater(newColor)) {
nextColor = newColor;
}
break;
}
index[component] = cIndex;
});
if (!nextColor) break; // done. No more color
a.push(nextColor);
console.log('#' + count + ':', nextColor);
}
console.log(a.length);
这个实现列出了所有 2^24 = 16777216 种颜色（一旦你在主循环中删除了 count < 100 条件，但你不想打印出那么多行）。如果某些颜色具有相同的亮度值，则按它们的 R 值排序，然后是 G 值，然后是 B 值。如果每个亮度值只需要一种颜色，请取消注释 greater() 函数中的第一行 - 然后您将获得 1207615 种具有不同亮度
的颜色
对不起，但我不得不说你在做一些无用功。
RGB 的 8 位量化将在 256 个亮度级别（包括黑色和白色）产生 1670 万种颜色但是你没有足够的像素来在 4K 显示器上显示它们，就像 3840 x 2160 = 8294400 4K 电视标准上的像素或 4K 电影标准上的 4096 x 2160 = 8847360。除了 1 像素颜色样本对眼睛的意义，尤其是在 4K 显示器上..？
我建议您使用 7 位量化而不是 8 位。这将为您提供 2^21 => 2097152 个颜色样本，它们将在 HD monitor/TV 上映射为单个像素，在 4K monitor/TV 上映射为 2x2 像素。漂亮。
代码如下；
"use strict";
var allColors = Array(Math.pow(2,21)), // All 2^21 colors
cgbl = Array(128).fill().map(e => []); // Colors gropuped by luminance
for (var i = 0, len = allColors.length; i < len; i++) allColors[i] = [i>>14, (i&16256)>>7, i&127];
allColors.reduce((g,c) => (g[Math.round(c[0]*0.2126 + c[1]*0.7152 + c[2]*0.0722)].push(c),g), cgbl);
cgbl.forEach((y,i) => console.log(y.length,"Colors at luminance level:",i));
但是请记住，您的 RGB 值现在处于 7 位量化。由于我们已经将它们分组为 128 个亮度级别，因此我还建议您在显示它们之前将亮度组（子数组）中的每个 RGB 值向左移动 1 位（r << 1; g << 1; b << 1;），从而将它们映射回 8 位.通过使用 .map() 仿函数，这是一项微不足道的工作。
因为我原来的答案已经很长了，我做这个答案是为了澄清算法，因为 OP 要求
让我们考虑一个类似的问题（但更容易推理）：
- 设 A 是一组数字，按升序排列，除了 2、3 和 5 外没有其他质因数
(Ai = 2^x * 3^y * 5^z)
- 求出A的n-th个数
确定 A1 = 1 = 2^0 * 3^0 * 5^0
假设在某个步骤中，我们已经计算出 A1..An 并且我们需要找到 A[n+1]
- 如果 A[n+1] 可以被 2 整除，则 A[n+1] = A[i2]*2 其中 1 <= i2 <= n
- 如果 A[n+1] 能被 3 整除，则 A[n+1] = A[i3]*3 且 1 <= i3 <= n
- 如果 A[n+1] 能被 5 整除，则 A[n+1] = A[i5]*5 且 1 <= i5 <= n
（显然 A[n+1] 至少可以被其中之一整除）
证明：A[n+1] = 2^x * 3^y * 5^z。如果 A[n+1] 可被 2 整除，则 x > 0，因此 B = A[n+1]/2 = 2^(x-1) * 3^y * 5^z 必须在 A 中。并且因为 B < A[n+1]，它必须在 A 中的 A[n+1] 之前, 所以 B = A[i2], 其中 1 <= i2 <= n.
所以要找到A[n+1]，我们可以：
- 求A[i2]*2 > A[n]的最小i2
- i3 和 i5 类似
- ==> A[n+1] = min(A[i2]*2, A[i3]*3, A[i5]*5)
A1 = 1, 运行 这些步骤 (n - 1) 次，我们找到 n-th 个 A
现在，如果每次迭代找到A[n+1]，我们使用3次for循环从1到n计算i2、i3和i5，时间复杂度为O(N^2)。但是你可以看到每次迭代的 i2、i3 和 i5 都不会减少（分别小于前一次迭代的值）。所以我们可以保存那些 i2、i3 和 i5 值，并且在每次迭代中我们只需要：
while (A[i2]*2 <= A[n]) ++i2;
while (A[i3]*3 <= A[n]) ++i3;
while (A[i5]*5 <= A[n]) ++i5;
现在时间复杂度变为O(N)：虽然while循环仍然嵌套在主for 1->n循环中，但只有4个变量从1->n增加，可以被认为是4个独立的循环。您可以通过使用时钟来验证 O(N) 属性 并测量不同 N s
的 运行 时间
将此算法应用于您的问题：
- 2、3 和 5 变为 R、G 和 B
- 整数比较变成你定义的颜色比较函数
- 如果您需要列出所有 2^24 种颜色，请定义比较函数，以便没有 2 种不同的颜色 "equal"（如果 C1 和 C2 是 2 种不同的颜色，则 C1 < C2 或 C2 < C1 ) - 就像我在原始答案中所做的那样
在 this post 我找到了一种算法来确定 RGB 颜色的亮度：
Luminance (standard for certain colour spaces): (0.2126*R + 0.7152*G + 0.0722*B)
我想使用这个等式，从 rgb(0,0,0) 开始，按照从最低到最高亮度的顺序生成所有 RGB 颜色，然后将它们绘制到 4096x4096 canvas。
我的问题是，由于有 1670 万种不同的组合，我无法在不使浏览器崩溃或不花费多天时间完成渲染的情况下全部生成然后对它们进行排序。所以我想找到一种方法来找到每个数字的倍数，这些数字将求和到下一个最小数字。
例如，从 0,0,0 和 rgb 开始，亮度将为 0 (0.2126*0 + 0.7152*0 + 0.0722*0 = 0)，下一个最不发光的 rgb 值将是 0,0,1，因为 0.2126*0 + 0.7152*0 + 0.0722*1 = .0722，并且没有一组倍数可以合计为较小的数字。
前 19 个连续亮度值如下（我可能遗漏了一两个，因为我手动计算了它们，但希望它有助于说明这一点）：
RGB => Luminence
0,0,0 => 0
0,0,1 => .0722
0,0,2 => .1444
1,0,0 => .2126
0,0,3 => .2166
1,0,1 => .2848
0,0,4 => .2888
1,0,2 => .357
0,0,5 => .361
2,0,0 => .4252
1,0,3 => .4292
0,0,6 => .4332
2,0,1 => .4974
1,0,4 => .5014
0,0,7 => .5054
2,0,2 => .5696
1,0,5 => .5736
0,0,8 => .5776
3,0,0 => .6378
我似乎找不到任何模式，所以我希望可能有一个等式或编码技巧可以让我找到最小的总和，高于之前的总和，是的倍数三个数字，无需暴力破解并检查每个可能的值。
编辑： 我做了一些额外的研究，看起来解决方案可能在于使用线性丢番图方程。如果我取每个小数并乘以 1000，得到 2126, 7152, & 722。然后 1 乘 1 数到 2,550,000 (2126*255 + 7152*255 + 722*255)，我可以检查每个数字以查看它是否是方程 2126r + 7152g + 722b = n 的解，其中 n 是当前计数到的数字, 和 r, g, & b 是未知数。如果我能做到这一点，我就可以计算出下一个连续亮度值的所有可能的 rgb 值，甚至不必将重复亮度值的任何值加倍，而且我只需要进行 255 万次计算而不是 1677+ 万次（每种颜色一个）。如果有人知道如何编写这个等式，或者如果有人有更好的解决方案，我将非常感激。谢谢！
您可以利用的一个事实是，序列中的每个三元组的 R、G 或 B 值仅比已输出的三元组大一个。
因此，您可以维护一个 BinaryHeap（按亮度排序），其中包含所有在 R、G 或 B 中比已经输出的三元组大 1 的三元组，并在循环中执行此操作:
- 从堆中移除最小的元素(r,g,b)
- 输出它
- 将 (r+1, g, b)、(r, g+1, b) 和 (r, g, b+1) 添加到堆中，但前提是它们是有效的三元组（所有值都小于大于或等于 255)，并且仅当它们不在堆中时。如果可以从中生成的替代三元组（在允许范围内的 r、g 或 b 中减少 1）具有比（r、g、b）更高的亮度，则三元组将不会已经在堆中。
例如，如果 (r+1, g-1, b) 的亮度高于 (r, g, b) 或 (r+1, g-)，则仅添加 (r+1, g, b) 1、b）无效。由于基于 r、g、b 计算亮度的因素是固定的，(r+1, g-1, b) 将始终具有较低的亮度，您应该只添加 (r+1, g, b) 如果 ( r+1,g-1,b)无效，即g为0时。
在pseudo-code中，规则是这样的：
function addTriplets(r, g, b)
{
if(g < 255)
pushTripletToHeap(r, g + 1, b);
if((g == 0) && (r < 255))
pushTripletToHeap(r + 1, g, b);
if((g == 0) && (r == 0) && (b < 255))
pushTripletToHeap(r, g, b + 1);
}
在开始循环之前将(0, 0, 0)三元组压入堆中，当堆为空时停止循环。
这是针对您的问题的算法（忘记了它的名字）： 该算法可以列出按某种顺序排序的所有颜色元组 {R,G,B}。在您的情况下，它是按亮度递增的：color1 < color2 <==> f(color1) < f(color2)，其中 f(color) = 0.2126*R + 0.7152*G + 0.0722*B
- 初始化：arr = [{r:0, g:0, b:0}]（最小颜色）
- 重复：
- Select min(iR)：a[iR] = {rR < 255, gR, bR}，并且 cR = {rR + 1, gR, bR} > arr[i] 对于每个 i . (Select arr 中的第一个颜色，这样如果我们将 1 添加到它的 r 分量，我们会得到一个新的颜色，它比 arr 中当前的所有颜色都大)
- iG 和 iB 类似 => 也得到 cG = {rG, gG + 1, bG} 和 cB = {rB, gB, bB + 1}
- cR、cG、cB中select最小颜色c
- 将 c 追加到数组 arr
当找不到这样的 iR、iG 或 iB 时，算法停止。
备注：
- arr 总是按升序排列的，因为每次给 arr 追加一个新颜色时，它总是更大比当前 arr. 中的每个元素
- 因为arr是升序排列的，所以我们只需要将cR/cG/cB和arr的最后一个元素进行比较即可如果它大于 arr 的每个元素
- iR、iG 和 iB 通过算法增加
- 复杂度为 O(N)，其中 N 种颜色 (2^24) ~ 16M。使用 heap-based 算法，复杂度约为 O(NlogN)。
这是我的实现（在 nodejs 6 中测试）
// use integer to avoid floating point inaccuracy
const lumixOf = {r: 2126, g: 7152, b: 722};
const maxValue = 256;
const components = ['r', 'g', 'b'];
class Color {
constructor(r, g, b, lum) {
this.r = r;
this.g = g;
this.b = b;
this.lum = lum;
}
add(component) {
const ans = new Color(this.r, this.g, this.b, this.lum);
if (++ans[component] >= maxValue) return null; // exceed 255
ans.lum += lumixOf[component];
return ans;
}
greater(color2) {
// return this.lum > color2.lum;
if (this.lum !== color2.lum) return this.lum > color2.lum;
if (this.r !== color2.r) return this.r > color2.r;
if (this.g !== color2.g) return this.g > color2.g;
return this.b > color2.b;
}
}
let a = [new Color(0, 0, 0, 0)]; // R, G, B, lumix
let index = {r: 0, g: 0, b: 0};
console.log('#0:', a[0]);
// Test: print the first 100 colors
for (let count = 1; count < 100; ++count) {
let nextColor = null;
const len = a.length;
const currentColor = a[len - 1];
components.forEach(component => {
let cIndex = index[component];
for (; cIndex < len; ++cIndex) {
const newColor = a[cIndex].add(component);
if (!newColor || !newColor.greater(currentColor)) continue;
// find the minimum next color
if (nextColor == null || nextColor.greater(newColor)) {
nextColor = newColor;
}
break;
}
index[component] = cIndex;
});
if (!nextColor) break; // done. No more color
a.push(nextColor);
console.log('#' + count + ':', nextColor);
}
console.log(a.length);
这个实现列出了所有 2^24 = 16777216 种颜色（一旦你在主循环中删除了 count < 100 条件，但你不想打印出那么多行）。如果某些颜色具有相同的亮度值，则按它们的 R 值排序，然后是 G 值，然后是 B 值。如果每个亮度值只需要一种颜色，请取消注释 greater() 函数中的第一行 - 然后您将获得 1207615 种具有不同亮度
对不起，但我不得不说你在做一些无用功。
RGB 的 8 位量化将在 256 个亮度级别（包括黑色和白色）产生 1670 万种颜色但是你没有足够的像素来在 4K 显示器上显示它们，就像 3840 x 2160 = 8294400 4K 电视标准上的像素或 4K 电影标准上的 4096 x 2160 = 8847360。除了 1 像素颜色样本对眼睛的意义，尤其是在 4K 显示器上..？
我建议您使用 7 位量化而不是 8 位。这将为您提供 2^21 => 2097152 个颜色样本，它们将在 HD monitor/TV 上映射为单个像素，在 4K monitor/TV 上映射为 2x2 像素。漂亮。
代码如下；
"use strict";
var allColors = Array(Math.pow(2,21)), // All 2^21 colors
cgbl = Array(128).fill().map(e => []); // Colors gropuped by luminance
for (var i = 0, len = allColors.length; i < len; i++) allColors[i] = [i>>14, (i&16256)>>7, i&127];
allColors.reduce((g,c) => (g[Math.round(c[0]*0.2126 + c[1]*0.7152 + c[2]*0.0722)].push(c),g), cgbl);
cgbl.forEach((y,i) => console.log(y.length,"Colors at luminance level:",i));
但是请记住，您的 RGB 值现在处于 7 位量化。由于我们已经将它们分组为 128 个亮度级别，因此我还建议您在显示它们之前将亮度组（子数组）中的每个 RGB 值向左移动 1 位（r << 1; g << 1; b << 1;），从而将它们映射回 8 位.通过使用 .map() 仿函数，这是一项微不足道的工作。
因为我原来的答案已经很长了，我做这个答案是为了澄清算法，因为 OP 要求
让我们考虑一个类似的问题（但更容易推理）：
- 设 A 是一组数字，按升序排列，除了 2、3 和 5 外没有其他质因数 (Ai = 2^x * 3^y * 5^z)
- 求出A的n-th个数
确定 A1 = 1 = 2^0 * 3^0 * 5^0
假设在某个步骤中，我们已经计算出 A1..An 并且我们需要找到 A[n+1]
- 如果 A[n+1] 可以被 2 整除，则 A[n+1] = A[i2]*2 其中 1 <= i2 <= n
- 如果 A[n+1] 能被 3 整除，则 A[n+1] = A[i3]*3 且 1 <= i3 <= n
- 如果 A[n+1] 能被 5 整除，则 A[n+1] = A[i5]*5 且 1 <= i5 <= n
（显然 A[n+1] 至少可以被其中之一整除）
证明：A[n+1] = 2^x * 3^y * 5^z。如果 A[n+1] 可被 2 整除，则 x > 0，因此 B = A[n+1]/2 = 2^(x-1) * 3^y * 5^z 必须在 A 中。并且因为 B < A[n+1]，它必须在 A 中的 A[n+1] 之前, 所以 B = A[i2], 其中 1 <= i2 <= n.
所以要找到A[n+1]，我们可以：
- 求A[i2]*2 > A[n]的最小i2
- i3 和 i5 类似
- ==> A[n+1] = min(A[i2]*2, A[i3]*3, A[i5]*5)
A1 = 1, 运行 这些步骤 (n - 1) 次，我们找到 n-th 个 A
现在，如果每次迭代找到A[n+1]，我们使用3次for循环从1到n计算i2、i3和i5，时间复杂度为O(N^2)。但是你可以看到每次迭代的 i2、i3 和 i5 都不会减少（分别小于前一次迭代的值）。所以我们可以保存那些 i2、i3 和 i5 值，并且在每次迭代中我们只需要：
while (A[i2]*2 <= A[n]) ++i2;
while (A[i3]*3 <= A[n]) ++i3;
while (A[i5]*5 <= A[n]) ++i5;
现在时间复杂度变为O(N)：虽然while循环仍然嵌套在主for 1->n循环中，但只有4个变量从1->n增加，可以被认为是4个独立的循环。您可以通过使用时钟来验证 O(N) 属性 并测量不同 N s
将此算法应用于您的问题：
- 2、3 和 5 变为 R、G 和 B
- 整数比较变成你定义的颜色比较函数
- 如果您需要列出所有 2^24 种颜色，请定义比较函数，以便没有 2 种不同的颜色 "equal"（如果 C1 和 C2 是 2 种不同的颜色，则 C1 < C2 或 C2 < C1 ) - 就像我在原始答案中所做的那样