0

Есть класс с двумя целочисленными свойствами

public class MyClass
{
    public int Prop1 { get; set; }
    public int Prop2 { get; set; }
}

Есть список экземпляров класса List, отсортированный по второму свойству, например такой

1 1
7 2
2 3
3 4
4 5
2 6
3 7
4 8

Нужно удалить из него как можно меньше элементов так, чтобы не было повторений по первому свойству, чтобы не было повторений по второму свойству, он получился отсортирован не только по второму элементу, но и по первому, чтобы сумма разностей между этими элементами была наименьшей. То есть из списка выше должен получиться список

1 1
2 3
3 4
4 5
4
  • Ну это к математикам, вам нужен алгоритм по сути.
    – VladD
    3 апр 2016 в 11:07
  • 1
    Вот есть похожий вопрос - посмотрите его ru.stackoverflow.com/questions/506543/…
    – Mirdin
    4 апр 2016 в 11:34
  • В конечном итоге список должен быть отсортирован сначала по первому свойству, затем, если имеем последовательность равных элементов второго свойства, тогда и по первому свойству? Во втором свойстве могут быть повторения? Почему вдруг удалился элемент 7 2? В первом списке нет семёрок. 9 апр 2016 в 18:18
  • @hedgehogues, 7 2 удалился потому что без семерке в первом свойстве останется больше элементов в конце
    – iRumba
    11 апр 2016 в 4:04

2 ответа 2

0

Решил. Примера кода перед собой нет, но смысл в следующем. Создаем дерево со следующей структурой узлов.

int _index; // Индекс элемента массива
int _level; // Уровень узла в дереве
NodeType _parent; // Родительский узел

конструктор принимает массив элементов, индекс элемента в узле, и уровень текущего узла + 1

Корневой элемент имеет индекс -1. Далее мы создаем потомков из ВСЕХ элементов. Для каждого следующего элемента потомками будут те, которые (по индексу) идут после текущего и оба значения которых больше значений текущего. То есть у элемента 7 2 потомков уже не будет, потому что все первые элементы не больше семерки.

Если потомков нет, то отмечаем узле как лист (добавляем его куда нибудь в массив листов дерева). Далее от листа перемещаемся вверх (по полю _parent) и получаем результирующий массив. Так как в листе у нас есть поле _level, то мы сразу будем знать количество элементов в массиве. Самая длинная цепочка будет ответом.

Так же можно оптимизировать алгоритм и отбросить лишние варианты еще на этапе построения дерева. Например, можно добавлять в кэш максимальную длину цепочки (на том этапе, когда мы выясняем, что узел является листомм). И если мы выяснили, что после элемента (конечно же мы проверяем его по индексу, а не по значению) "2 6" у нас следует 2 элемента, то дойдя до того места, где у нас встречается этот элемент, мы сравниваем его уровень + кэшированное количество элементов после него с наибольшей на данный момент цепочкой, и если кэшированное значение больше, то отбрасываем этот вариант сразу. Есть возможность и еще сократить время действия алгоритма, но я их приводить уже не буду.

10
  • Э... как-то все слишком сложно. 11 апр 2016 в 5:19
  • Можно сделать все то же самое - но без дерева :) 11 апр 2016 в 5:21
  • @PavelMayorov, можно, да.... алгоритм будет примерно таким же, как алгоритм проверки регулярок... то есть сначала двигаемся вперед, потом назад, потом вперед, потом назад... ну вы поняли ) А в моем случае требуется не просто найти первый правильный ответ, а выбрать один единственный, удовлетворяющий и другим условиям. И без дерево это все будет нечитабельно. И при добавлении новых условий отбора придется менять в нескольких местах код, а значит его надо будет заново переваривать )
    – iRumba
    11 апр 2016 в 8:34
  • Ничего подобного. Задача сводится к динамическому программированию, притом все подзадачи - жадные. И это при любом числе условий. 11 апр 2016 в 8:36
  • Иными словами, там просто два вложенных цикла. 11 апр 2016 в 8:36
0
    struct SequenceData {
        public int prevIndex;
        public int length;
        public int cost;
    }

    // ...
    // MyClass[] data = ...;

    Func<MyClass, MyClass, bool> canExtend = (a, b) => a.Prop1 < b.Prop1 && a.Prop2 < b.Prop2;
    Func<SequenceData, SequenceData, bool> compare = (a, b) => a.length > b.length || a.length == b.length && a.cost < b.cost;

    var seq = new SequenceData[data.Length];
    SequenceData best;
    for (int i = 0; i < data.Length; i++)
    {
        best = new SequenceData { prevIndex = -1, length = 0, cost = 0 };

        for (var j = 0; j < i; j++)
            if (canExtend(data[j], data[i]) && compare(seq[j], best))
            {
                best = seq[j];
                best.prevIndex = j;
            }

        best.length++;
        best.cost += Math.Abs(data[i].Prop1 - data[i].Prop2);
        seq[i] = best;
    }

    best = new SequenceData { prevIndex = -1, length = 0, cost = 0 };
    for (var i = 0; i < data.Length; i++)
        if (compare(seq[i], best))
        {
            best = seq[i];
            best.prevIndex = i;
        }

    var result = new MyClass[best.length];
    for (int i = best.prevIndex, j = best.length - 1; i >= 0; i = seq[i].prevIndex, j--)
        result[j] = data[i];

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.