Мне недавно пришлось это сделать, за исключением того, что предметы могли существовать несколько раз. Это сложные вещи, но я смог сделать это с помощью счетчиков упреждения и некоторых других сумасшествий. Это похоже на решение Роба, так что спасибо ему за то, что я начал!
Прежде всего, давайте предположим, что мы хотим вернуть список операций, которые преобразуют первый список во второй:
public interface Operation {
/**
* Apply the operation to the given list.
*/
void apply(List<String> keys);
}
и у нас есть несколько вспомогательных методов для построения операций. На самом деле вам не нужна операция «перемещение», и вы могли бы даже иметь «своп» (или вместо этого), но вот что я сделал:
Operation delete(int index) { ... }
Operation insert(int index, String key) { ... }
Operation move(int from, int to) { ... }
Теперь мы определим специальный класс для хранения прогнозных показателей:
class Counter {
private Map<String, Integer> counts;
Counter(List<String> keys) {
counts = new HashMap<>();
for (String key : keys) {
if (counts.containsKey(key)) {
counts.put(key, counts.get(key) + 1);
} else {
counts.put(key, 1);
}
}
}
public int get(String key) {
if (!counts.containsKey(key)) {
return 0;
}
return counts.get(key);
}
public void dec(String key) {
counts.put(key, counts.get(key) - 1);
}
}
И вспомогательный метод для получения индекса следующего ключа в списке:
int next(List<String> list, int start, String key) {
for (int i = start; i < list.size(); i++) {
if (list.get(i).equals(key)) {
return i;
}
}
throw new RuntimeException("next index not found for " + key);
}
Теперь мы готовы выполнить преобразование:
List<Operation> transform(List<String> from, List<String> to) {
List<Operation> operations = new ArrayList<>();
// make our own copy of the first, that we can mutate
from = new ArrayList<>(from);
// maintain lookahead counts
Counter fromCounts = new Counter(from);
Counter toCounts = new Counter(to);
// do all our deletes first
for (int i = 0; i < from.size(); i++) {
String current = from.get(i);
if (fromCounts.get(current) > toCounts.get(current)) {
Operation op = delete(i);
operations.add(op);
op.apply(from);
fromCounts.dec(current);
i--;
}
}
// then one more iteration for the inserts and moves
for (int i = 0; i < to.size(); i++) {
String current = to.get(i);
if (from.size() > i && from.get(i).equals(current)) {
fromCounts.dec(current);
continue;
}
if (fromCounts.get(current) > 0) {
Operation op = move(next(from, i + 1, current), i);
operations.add(op);
op.apply(from);
fromCounts.dec(current);
} else {
Operation op = insert(i, current);
operations.add(op);
op.apply(from);
}
}
return operations;
}
Немного сложно разобраться, но в основном вы делаете удаления, чтобы вы знали, для каждого ключа вы вставляете или перемещаете. Затем вы снова просматриваете список и, если его достаточно, перемещаете один из той части списка, которую вы еще не видели, иначе вставьте. К тому времени, как вы доберетесь до конца, все выстроится в линию.