max_dissim.R (2051B)
1 # For all possible numbers of colors return the set with the maximum minimum dissimilarity 2 3 max_dissim_colors <- function(dissim_mat) { 4 col_names <- colnames(dissim_mat) 5 N <- ncol(dissim_mat) 6 if (is.null(col_names)) 7 col_names <- as.character(seq(N)) 8 9 # Build a data frame of color pairs ordered from most to least dissimilar 10 col_pairs <- list() 11 for (n in seq_len(N-1)) { 12 for (m in seq(n+1, N)) { 13 col_pairs <- append(col_pairs, 14 list(c(n, m, dissim_mat[n, m]))) 15 } 16 } 17 col_pairs <- as.data.frame(matrix(unlist(col_pairs), ncol = 3, byrow = TRUE)) 18 colnames(col_pairs) <- c("n", "m", "dissim") 19 col_pairs <- col_pairs[order(col_pairs$dissim, decreasing = TRUE), ] 20 21 # Here's the algorithm: 22 # We're going to build up a list of sets of colors by considering pairs from the 23 # most to least dissimilar. The first set we encounter of a given length will be 24 # the set that maximizes its minimum dissimilarity. But we'll remember all of 25 # the sets we've seen because any given set could have the max-min dissimularity 26 # for a greater length. 27 col_sets <- list() 28 best_sets <- list() 29 set_length_target <- 2 30 for (pair_idx in seq_len(nrow(col_pairs))) { 31 col_sets <- append(col_sets, list(col_pairs[pair_idx, c('n', 'm')])) 32 33 for (set_idx in seq_along(col_sets)) { 34 # If either n or m is in the current set, add the other to it 35 if (any(col_pairs[pair_idx, c('n', 'm')] %in% col_sets[[set_idx]])) { 36 col_sets[[set_idx]] <- union(col_pairs[pair_idx, c('n', 'm')], 37 col_sets[[set_idx]]) 38 } 39 40 # Check if this set is the length we're looking for 41 if (length(col_sets[[set_idx]]) == set_length_target) { 42 best_sets <- append(best_sets, 43 list(col_sets[[set_idx]])) 44 set_length_target <- set_length_target + 1 45 } 46 } 47 48 # Any sets that differed only by substituting n for m are now duplicated, so 49 # get rid of them 50 col_sets <- unique(col_sets) 51 } 52 53 best_sets 54 }