更新：问题已经附带具体细节和代码，请见下文。
警告：此问题是关于优化矩阵中项目排列的。它不是关于比较颜色的。最初，我决定提供有关我的问题的背景会有所帮助。现在我后悔了这个决定，因为结果是相反的：太多无关的谈论颜色，几乎没有关于实际算法的内容。
我为孩子买了一盒80支毛笔，但让我很烦恼的是它们没有分类。
我曾经在Android上玩过一个名为Blendoku的游戏，你需要做的就是将颜色排列成一种渐变的方式，使得相邻的颜色最为相似：
这就是我拥有的：
- 熟练掌握JavaScript - 所有笔的颜色值的平坦数组 - 一个function
distance(color1, color2)，显示颜色对的相似程度。它返回一个介于0和100之间的浮点数，其中0表示颜色相同。我所缺少的只是一个算法。
80的阶乘是一个有118位数字的数字，这排除了蛮力破解。
可能有方法使蛮力破解成为可行的：
- 固定几支笔的位置（例如在角落里）以减少可能的组合数量； - 放弃包含至少一个非常不相似邻居对的分支； - 在找到第一个令人满意的安排后停止。
但是，我仍然缺少实际的算法，更不用说非暴力的算法了。
PS作业：
- 相似性排序矩阵 -- 没有答案。
- 最佳二维调色板排列算法 -- 非常相似的问题，没有答案。
- 如何在二维中排序颜色？ -- 超过50％的单元格已经包含正确组织的颜色；不熟悉编程语言；实际排序解决方案未得到解释。
- 对颜色/颜色值进行排序 -- 单个平坦数组。
更新
目标
以这样一种方式将预定义的80种颜色排列在8×10网格中，使得颜色形成漂亮的渐变而不会出现撕裂。
由于下文所述原因，此问题没有明确的解决方案，可能的解决方案容易产生不完美的结果和主观性。这是可以预期的。
请注意，我已经有一个比较两种颜色并告诉它们相似程度的函数。
颜色空间是三维的
人眼有三种类型的感受器来区分颜色。人类的颜色空间是三维的（三色）。
描述颜色的不同模型都是三维的：RGB、HSL、HSV、XYZ、LAB、CMY（请注意，CMYK中的“K”仅需要是因为有色墨水不完全不透明且昂贵）。
例如，这个调色板：
这个调色板使用极坐标，色相在角度上表示，饱和度在半径上表示。没有第三个维度（亮度），这个调色板缺少所有明亮和暗淡的颜色：白色、黑色、所有灰色（除了中心的50%灰色）和着色灰色。
这个调色板只是HSL/HSV色彩空间的一个薄片：
不可能在渐变中将所有颜色在2D网格上布置而不出现撕裂。
例如，这里列举了所有32位RGB颜色，按字典序排列成2D网格。你可以看到渐变有很多撕裂：
这个问题是关于在JavaScript中优化网格，而不是比较颜色！
我已经选择了一个函数来确定颜色的相似性：Delta E 2000。该函数专门设计用于反映人类对颜色相似度的主观感知。这里有一篇whitepaper描述它的工作原理。
这个问题是关于优化二维网格中每对相邻项（垂直和水平）的相似度尽可能低的排列方式。
“优化”一词并不是指让算法运行得更快。它是指Mathematical optimization的意义：
在最简单的情况下，optimization problem由通过系统地选择允许集合内的输入值并计算函数值来最大化或最小化实数函数组成。
在我的情况下：
这里的“函数”是运行
DeltaE.getDeltaE00(color1, color2)函数以计算所有相邻项的输出，输出是一堆数字（大约142个数字），反映出所有相邻对之间的不相似程度。“最大化或最小化”- 目标是将“函数”的输出最小化。
“输入值”- 是在8×10网格中80个预定义项的特定排列。共有
80！个输入值，这使得在家用电脑上无法通过暴力破解来完成任务。请注意，我没有明确定义“函数”的最小化标准。如果我们只使用所有数字的最小总和，那么获胜的结果可能是总和最低的情况，但是有些相邻的项对非常不相似。
因此，“函数”应该考虑不仅所有比较的总和，而且还要确保没有比较偏离得太远。
解决问题的可能路径：
从我之前在这个问题上尝试的赏金中，我学到了以下路径：
遗传算法
优化器/求解器库
带有某种算法帮助的手动排序
其他东西？
优化器/求解器库的解决方案是我最初希望的。但是成熟的库，如CPLEX和Gurobi不支持JS。虽然有一些JS库，但它们没有很好的文档，并且没有新手教程。
遗传算法方法非常令人兴奋。但它需要构思突变和交配样本（网格排列）的算法。突变似乎很琐碎：只需交换相邻项即可。但我对交配一无所知。而且我对整个过程的理解很少。
手动排序建议乍一看很有前途，但深入研究后不足为奇。它们还假设使用算法来解决某些步骤，却没有提供实际算法。
代码样板和颜色样本
我已经准备了JS代码样板：https://codepen.io/lolmaus/pen/oNxGmqz?editors=0010 注意：代码运行需要一段时间。为了更轻松地处理它，请执行以下操作：
- 登录/注册CodePen以便能够fork模板。
- Fork模板。
- 前往设置/行为并确保自动更新已禁用。
- 调整窗格大小，最大化JS窗格并最小化其他窗格。
- 前往查看更改/调试模式以在单独的选项卡中打开结果。这将启用
console.log()。此外，如果代码执行停止，您可以关闭渲染选项卡而不失去访问编码选项卡的权利。 - 在对代码进行更改后，在代码选项卡中点击保存，然后刷新渲染选项卡并等待。
- 为了包含JS库，请前往设置/JS。我使用这个CDN来链接到来自GitHub的代码：https://www.jsdelivr.com/?docs=gh
源数据:
const data = [
{index: 1, id: "1", name: "Wine Red", rgb: "#A35A6E"},
{index: 2, id: "3", name: "Rose Red", rgb: "#F3595F"},
{index: 3, id: "4", name: "Vivid Red", rgb: "#F4565F"},
// ...
];
Index是基于1的颜色编号，按照它们在盒子中出现的顺序排序，但在代码中未使用。
Id是笔制造商颜色的编号。由于某些编号以WG3形式出现，因此它们是字符串。
颜色类。
该类提供了一些抽象方法来处理单个颜色。它使得比较给定颜色和另一个颜色变得容易。
index;
id;
name;
rgbStr;
collection;
constructor({index, id, name, rgb}, collection) {
this.index = index;
this.id = id;
this.name = name;
this.rgbStr = rgb;
this.collection = collection;
}
// Representation of RGB color stirng in a format consumable by the `rgb2lab` function
@memoized
get rgbArr() {
return [
parseInt(this.rgbStr.slice(1,3), 16),
parseInt(this.rgbStr.slice(3,5), 16),
parseInt(this.rgbStr.slice(5,7), 16)
];
}
// LAB value of the color in a format consumable by the DeltaE function
@memoized
get labObj() {
const [L, A, B] = rgb2lab(this.rgbArr);
return {L, A, B};
}
// object where distances from current color to all other colors are calculated
// {id: {distance, color}}
@memoized
get distancesObj() {
return this.collection.colors.reduce((result, color) => {
if (color !== this) {
result[color.id] = {
distance: this.compare(color),
color,
};
}
return result;
}, {});
}
// array of distances from current color to all other colors
// [{distance, color}]
@memoized
get distancesArr() {
return Object.values(this.distancesObj);
}
// Number reprtesenting sum of distances from this color to all other colors
@memoized
get totalDistance() {
return this.distancesArr.reduce((result, {distance}) => {
return result + distance;
}, 0);
}
// Accepts another color instance. Returns a number indicating distance between two numbers.
// Lower number means more similarity.
compare(color) {
return DeltaE.getDeltaE00(this.labObj, color.labObj);
}
}
集合：一个用于存储所有颜色并对其进行排序的类。
class Collection {
// Source data goes here. Do not mutate after setting in the constructor!
data;
constructor(data) {
this.data = data;
}
// Instantiates all colors
@memoized
get colors() {
const colors = [];
data.forEach((datum) => {
const color = new Color(datum, this);
colors.push(color);
});
return colors;
}
// Copy of the colors array, sorted by total distance
@memoized
get colorsSortedByTotalDistance() {
return this.colors.slice().sort((a, b) => a.totalDistance - b.totalDistance);
}
// Copy of the colors array, arranged by similarity of adjacent items
@memoized
get colorsLinear() {
// Create copy of colors array to manipualte with
const colors = this.colors.slice();
// Pick starting color
const startingColor = colors.find((color) => color.id === "138");
// Remove starting color
const startingColorIndex = colors.indexOf(startingColor);
colors.splice(startingColorIndex, 1);
// Start populating ordered array
const result = [startingColor];
let i = 0;
while (colors.length) {
if (i >= 81) throw new Error('Too many iterations');
const color = result[result.length - 1];
colors.sort((a, b) => a.distancesObj[color.id].distance - b.distancesObj[color.id].distance);
const nextColor = colors.shift();
result.push(nextColor);
}
return result;
}
// Accepts name of a property containing a flat array of colors.
// Renders those colors into HTML. CSS makes color wrap into 8 rows, with 10 colors in every row.
render(propertyName) {
const html =
this[propertyName]
.map((color) => {
return `
<div
class="color"
style="--color: ${color.rgbStr};"
title="${color.name}\n${color.rgbStr}"
>
<span class="color-name">
${color.id}
</span>
</div>
`;
})
.join("\n\n");
document.querySelector('#box').innerHTML = html;
document.querySelector('#title').innerHTML = propertyName;
}
}
使用方法：
const collection = new Collection(data);
console.log(collection);
collection.render("colorsLinear"); // Implement your own getter on Collection and use its name here
样例输出：
