寻找最小化换漆次数的排列算法（喷漆件场景）

问题背景 #

我有一批需要喷涂两种颜色的工件，示例如下：

• Pc1：红、蓝
• Pc2：黄、绿
• Pc3：黄、红
• Pc4：黑、黄

目标是找到一种排列算法，最小化序列中的换漆次数。比如示例里，顺序1→2→3→4需要换漆4次，而顺序2→4→3→1仅需3次。

已尝试的解法 #

• 暴力解法：基于Heap permutation实现，但最多只能处理10个工件，工件数量增多（约30个）时排列组合数过大，无法运行。
• 缩减工件列表：尝试移除“双异色”工件（如Pc5：粉、紫），但对缩减列表规模没有明显效果。

遇到的新问题 #

我尝试了@Stef的解决方案，但输出结果错误，出现大量重复工件。推测原因是部分工件的两种颜色相同（如['yellow', 'yellow']）。

我的样本数据：

[[' 254 C PURPLE', ' 2C NOIR'], ['YELLOW C', 'BLEU 072 C'], [' 342 C GREEN', ' 430 C  GREY'], [' 254 C PURPLE', 'WHITE'], [' 392 C KAKI ', ' 392 C KAKI'], [' 342 C GREEN ', ' 342 C GREEN'], ['RUBINE RED C', ' 153 C OCRE'], [' 196 C MAUVE', ' VERT 375 C'], ['YELLOW C', 'YELLOW C'], [' 331 C VERT', ' 331 C VERT'], [' 072 C BLEU', ' 155 C BEIGE'], [' 263 C VIOLET', 'BLEU 072 C'], ['GREEN C', ' 153 C OCRE'], [' 427 C GRIS', 'RUBINE RED  C'], ['YELLOW C', ' 254 C PURPLE'], ['PROCESS BLUE C', ' 342 C GREEN']]

该方案输出结果：

[2, 8, 1, 8, 10, 7, 12, 6, 15, 5, 11, 4, 8, 14, 8, 9, 13, 8, 0, 3]

可以看到编号8的工件多次重复出现，不符合需求。

内容的提问来源于stack exchange，提问作者Medestrac