Сгладить неровный массив по ссылке значений

#c# #arrays #algorithm

#c# #массивы #алгоритм

Вопрос:

Учитывая неровный массив целых чисел, например:

 var arr = new int[11][] {
    new int[] { 0, 7 },
    new int[] { 1 },
    new int[] { 2, 5, 6 },
    new int[] { 3 },
    new int[] { 4 },
    new int[] { 5, 6 },
    new int[] { 6 },
    new int[] { 7, 9 },
    new int[] { 8, 10 },
    new int[] { 9 },
    new int[] { 10 }
};

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

 { 0, 7, 9, 1, 2, 5, 6, 3, 4, 8, 10 }

В этом конкретном примере { 0, 7 } и { 7, 9 } будут объединены, поскольку они имеют общий номер, 7 связывающий их. Также удаляются следующие дубликаты, такие как { 5, 6 } , { 6 } и т.д.

Не уверен, имеет ли это достаточный смысл, но я тоже ломаю голову 🙂 Я надеюсь, что можно избежать слишком большого количества обратных ссылок и нескольких вложенных циклов, если это возможно, возможно, с использованием LINQ / PLINQ или какой-либо разумной манипуляции со строками на месте.

1. Что, если { 0, 7 } и { 7, 9 } и { 7, 10 } существует в массиве?

2. Есть ли у вас неэффективный алгоритм для этого?

3. Вопрос не совсем четко определен. Слишком много случаев, когда совершенно не очевидно, что должно произойти. В вашем примере вы, кажется, подразумеваете, что подмассивы могут быть переставлены по желанию для получения «более коротких» результатов. Что, если есть несколько способов изменить порядок? Какой из них следует выбрать? Что, если некоторые механизмы дают более короткие результаты, чем другие?

Ответ №1:

Ваш примерный результат может быть найден в результате топологической сортировки DAG (направленный ациклический граф), где пары ваших подмассивов образуют ребра графа

{2,5,6} сформировать направленные ребра (дуги) 2->5 и 5-> 6.

Сортировка топоса также обнаружит возможные противоречия (циклы), такие как {2,3}, {3,5}, {5,2}