I have pieces that need to be paint with 2 colors. For example: (Pc1 - Red - Blue) (Pc2 - Yellow - Green) (Pc3 - Yellow - Red) (Pc4 - Black - Yellow) I'm looking for an algorithm to find the best permutation to minimize the series change. In my example the order 1 -> 2 -> 3 -> 4 implies 4 paints change, whereas 2 -> 4 -> 3 -> 1 only need 3 changes.
I've tried a brute force with Heap permutation, but it can only handle 10 pieces, then there are two many possible permutations. I've tried to remove the "double single colors" (for example Pc5 - Pink - Purple) it doesn't reduce enough the list (~30 items)
I've tried @Stef solution, but the result is wrong, wih many occurences of the same object. I think it's because some objects have 2x the same colour, for example ['yellow', 'yellow']. Here is my sample: [[' 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']]
The output is [2, 8, 1, 8, 10, 7, 12, 6, 15, 5, 11, 4, 8, 14, 8, 9, 13, 8, 0, 3], with several occurences of the 8.
Your problem can be rephrased as a particular case of the Traveling salesman problem, with edges constrained to have a length of 0, 1 or 2. Consider the graph with one vertex per piece, and a weighted edge between two vertices representing the number of colour-changes required between these two pieces. Then you're looking for a minimum-weight path that goes through all vertices exactly once.
Unfortunately, the travelling salesman problem is NP-hard even when restricted to edges of lengths 0, 1 and 2 as is your case. See Traveling salesman problem with small edge weights. Still, there are heuristics to solve it that might or might not be more efficient than your implementation of heap permutations.
For instance, using python library networkx:
import random
import networkx as nx
from itertools import combinations, pairwise
colours = ['crimson', 'honey', 'almond', 'cherry', 'navy', 'sky', 'dandelion', 'melon', 'lavender', 'lemon']
n_rooms = 30
room_colour = [random.sample(colours, k=2) for _ in range(n_rooms)]
print(room_colour)
# [['lemon', 'sky'], ['crimson', 'dandelion'], ['sky', 'crimson'], ['navy', 'lemon'], ['cherry', 'melon'], ['honey', 'dandelion'], ['lavender', 'melon'], ['lavender', 'lemon'], ['dandelion', 'almond'], ['lemon', 'navy'], ['almond', 'cherry'], ['melon', 'dandelion'], ['melon', 'honey'], ['navy', 'crimson'], ['lavender', 'cherry'], ['almond', 'honey'], ['navy', 'almond'], ['lavender', 'cherry'], ['lavender', 'lemon'], ['melon', 'almond'], ['cherry', 'lavender'], ['honey', 'lavender'], ['lavender', 'lemon'], ['melon', 'navy'], ['melon', 'navy'], ['melon', 'crimson'], ['honey', 'crimson'], ['honey', 'crimson'], ['lavender', 'melon'], ['honey', 'sky']]
def get_weight(i, j):
return len(set(room_colour[i]+room_colour[j])) - 2
G = nx.Graph()
G.add_nodes_from(range(n_rooms))
G.add_weighted_edges_from((i, j, get_weight(i, j))
for i,j in combinations(range(n_rooms), 2))
permutation = nx.approximation.traveling_salesman_problem(G, cycle=False)
print(permutation)
print([room_colour[i] for i in permutation])
print('Total cost: ', sum(get_weight(i, j) for i,j in pairwise(permutation)))
# [11, 6, 28, 7, 22, 18, 3, 23, 24, 9, 16, 8, 2, 0, 29, 12, 4, 14, 20, 17, 21, 5, 15, 10, 19, 25, 1, 26, 27, 13]
# [['melon', 'dandelion'], ['lavender', 'melon'], ['lavender', 'melon'], ['lavender', 'lemon'], ['lavender', 'lemon'], ['lavender', 'lemon'], ['navy', 'lemon'], ['melon', 'navy'], ['melon', 'navy'], ['lemon', 'navy'], ['navy', 'almond'], ['dandelion', 'almond'], ['sky', 'crimson'], ['lemon', 'sky'], ['honey', 'sky'], ['melon', 'honey'], ['cherry', 'melon'], ['lavender', 'cherry'], ['cherry', 'lavender'], ['lavender', 'cherry'], ['honey', 'lavender'], ['honey', 'dandelion'], ['almond', 'honey'], ['almond', 'cherry'], ['melon', 'almond'], ['melon', 'crimson'], ['crimson', 'dandelion'], ['honey', 'crimson'], ['honey', 'crimson'], ['navy', 'crimson']]
# Total cost: 23