Прошу ваших отзывов о моем коде. Меня особенно беспокоит простота моей реализации. Мой код правильный, и производительность в порядке, но я чувствую, что должен быть более простой способ решить эту проблему. Если вы обнаружите какие-либо проблемы, помимо простоты, я буду рад, если вы также укажете на них. Имейте в виду, что я ищу только рекурсивные решения.
Описание проблемы
Задача найти рекурсивный (не итеративное!) решение следующей проблемы:
Список токенов может быть устроен по-разному, например [r,r,r,b,b,w,w] может быть оформлен как:
1: фиолетовый
2: rbrwrbw
3: rbrwbrw
4: щебень
Качество любого расположения — кортеж («минимальное расстояние между одними и теми же токенами», «умноженное на минимальное расстояние»). Качество сортируется в порядке возрастания, сначала по «минимальному расстоянию», и только если «минимальное расстояние» равно, качество сортируется в порядке убывания по «количеству минимального расстояния». В данном примере мы получаем следующие баллы:
1: (0,1) // минимальное расстояние между токенами r равно 0. Минимальное расстояние встречается один раз.
2: (1,2) // минимальное расстояние между токенами r равно 1, встречается дважды.
3: (1,1) // минимальное расстояние между токенами r равно 1, встречается один раз.
4: (2,4) // минимальное расстояние между токенами r, b и w соответственно. равно 2, встречается 4 раза.
Следовательно, 4 имеет наивысшее качество, за ним следует 3 и так далее.
Задача состоит в том, чтобы найти аранжировки с максимально возможными баллами для данного входного списка!
Мое решение на Java
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.HashSet;
public class Combinations {
private int minimumDistance;
private int countDistance;
/**
* {@summary} Finds all optimal permutations and returns them.
* @param arr The list of Characters to be permuted.
*/
public List<List<Character>> findOptimalPermutation(ArrayList<Character> arr) {
for (int i=arr.size()-1; i>=0 ;i--) {
minimumDistance = i;
for (int j=0; j<arr.size(); j++) {
countDistance = j;
if (permute(arr,0).size()!=0) {break;}
}
if (permute(arr,0).size()!=0) {break;};
}
return permute(arr,0);
}
/**
* {@summary} Finds permutations depending on the value of maxMinDistance and countDistance.
*
* @param arr
* @param k
*/
private List<List<Character>> permute(ArrayList<Character> arr, int k){
HashSet<Character> index = new HashSet<>();
ArrayList<ArrayList<Character>> arrs = new ArrayList<>();
for(int i = k; i < arr.size(); i++){
java.util.Collections.swap(arr, i, k);
if (!index.contains(arr.get(k))) {
index.add(arr.get(k));
arrs.add(new ArrayList<Character>(arr));
}
java.util.Collections.swap(arr, k, i);
}
List<List<Character>> solutions = new ArrayList<>();
for (ArrayList<Character> unique_arr : arrs) {
boolean minDistanceBiggerThan = findMinimumDistance(arr,k-1)>=minimumDistance;
if (k>0 && minDistanceBiggerThan) {
solutions.addAll(permute(unique_arr, k+1));
} else if (k==0) {
solutions.addAll(permute(unique_arr, k+1));
}
}
if (k == arr.size() -1) {
boolean minDistanceBiggerThan = findMinimumDistance(arr, k)>=minimumDistance;
boolean minDistanceOccursLessThan = countMinimumDistance(arr,minimumDistance)<=countDistance;
if (minDistanceBiggerThan && minDistanceOccursLessThan) {
solutions.add(new ArrayList<>(arr));
}
}
return solutions;
}
/**
* {@summary} Finds the minimal distance between all pairs of identical elements.
* @param arr
* @param k
* @return min
*/
private int findMinimumDistance(List<Character> arr, int k) {
HashMap<Character, Integer> map = new HashMap<>();
int min = 99999;
for (int i=0; i<=k ;i++) {
if (map.containsKey(arr.get(i))) {
if (i - map.get(arr.get(i)) - 1 < min) {
min = i - map.get(arr.get(i)) - 1;
}
map.put(arr.get(i), i);
} else {
map.put(arr.get(i), i);
}
}
return min;
}
/**
* {@summary} Counts how often the minimal distance occurs.
* @param arr
* @param min
* @return count
*/
private int countMinimumDistance(List<Character> arr, int min) {
HashMap<Character, Integer> map = new HashMap<>();
int count = 0;
for (int i=0; i<arr.size(); i++) {
if (!map.containsKey(arr.get(i))) {
map.put(arr.get(i), i);
} else {
if (i - map.get(arr.get(i)) - 1 == min) {
count++;
}
map.put(arr.get(i), i);
}
}
return count;
}
public int getMaxMinDistance() {
return minimumDistance;
}
public int getCountDistance() {
return countDistance;
}
}
Выполнение в Main:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Main {
public static void main(String[] args) {
ArrayList<Character> arr = new ArrayList<Character>(Arrays.asList('r','r','r','r',
'b','b','b',
'g','g',
'w','w','w','w',
's','s'));
Combinations combinations = new Combinations();
List<List<Character>> optimalVals = combinations.findOptimalPermutation(arr);
System.out.println("All possible lists of tokens: ");
System.out.println(optimalVals);
System.out.println();
int maxMinDistance = combinations.getMaxMinDistance();
int countDistance = combinations.getCountDistance();
System.out.printf("The number of possible is solutions is: %d. These solutions have the following score:n", optimalVals.size());
System.out.printf("Minimal Distance: %d, Frequency count of minimal distance: %dn", maxMinDistance, countDistance);
System.out.println();
}
}
Выход:
All possible lists of tokens:
[[r, w, b, g, r, w, s, b, g, r, w, s, b, r, w], [r, w, b, g, r, w, s, b, r, g, w, s, b, r, w], [r, w, b, g, r, w, s, b, r, w, g, s, b, r, w], [r, w, b, g, r, s, w, b, g, r, w, s, b, r, w], [r, w, b, g, r, s, w, b, r, g, w, s, b, r, w], [r, w, b, g, s, r, w, b, g, r, w, s, b, r, w], [r, w, b, s, r, g, w, b, r, s, w, g, b, r, w], [r, w, b, s, r, g, w, b, s, r, w, g, b, r, w], [r, w, b, s, r, w, g, b, r, w, s, g, b, r, w], [r, w, b, s, r, w, g, b, r, s, w, g, b, r, w], [r, w, b, s, r, w, g, b, s, r, w, g, b, r, w], [r, w, b, s, g, r, w, b, s, r, w, g, b, r, w], [w, r, b, g, w, r, s, b, g, w, r, s, b, w, r], [w, r, b, g, w, r, s, b, w, r, g, s, b, w, r], [w, r, b, g, w, r, s, b, w, g, r, s, b, w, r], [w, r, b, g, w, s, r, b, g, w, r, s, b, w, r], [w, r, b, g, w, s, r, b, w, g, r, s, b, w, r], [w, r, b, g, s, w, r, b, g, w, r, s, b, w, r], [w, r, b, s, g, w, r, b, s, w, r, g, b, w, r], [w, r, b, s, w, g, r, b, w, s, r, g, b, w, r], [w, r, b, s, w, g, r, b, s, w, r, g, b, w, r], [w, r, b, s, w, r, g, b, w, r, s, g, b, w, r], [w, r, b, s, w, r, g, b, w, s, r, g, b, w, r], [w, r, b, s, w, r, g, b, s, w, r, g, b, w, r]]
The number of possible is solutions is: 24. These solutions have the following score:
Minimal Distance: 3, Frequency count of minimal distance: 4