Алгоритм/логика для уникальной задачи сортировки матриц ⇐ Python

[Anonymous]

У меня проблема с сортировкой матрицы: каждая строка содержит как минимум два числа, а остальные столбцы имеют значение «Нет». Мне нужно отсортировать эту матрицу так, чтобы:

• Каждый столбец располагался в порядке возрастания, что позволяло использовать значения None между числами.
• Каждое число появляется только один раз в столбце.
• Если две строки имеют перекрывающиеся значения в одном или нескольких столбцах (т. е. они имеют одно и то же число хотя бы в одном столбце и не имеют конфликтующих значений), их следует объединить в одну строку.

Действительные и недопустимые комбинации:

• Действительная комбинация:
  

  Код: Выделить всё

  [1, 2, None, None]

  и [None, 2, 3, None] можно объединить с [1, 2, 3, None], поскольку они имеют общее значение 2 во втором столбце и не имеют противоречивых значений.

[*]Недопустимая комбинация:

• Код: Выделить всё

  [1, 2, None, None]

  и [None, None, 3, 4] нельзя объединять, поскольку ни в одном столбце у них нет общих чисел.

• Код: Выделить всё

  [1, 2, None, None]

  и [2, 2, None, None] невозможно объединить из-за конфликта значений в первом столбце.

К концу этого процесса матрица должна быть отсортирована так, чтобы:

• Каждое число появляется не более одного раза в каждом столбце.
• Каждый столбец располагается в порядке возрастания.
• Если процесс невозможен (например, не существует допустимой комбинации) , функция должна возвращать False.

Пример проблемы:
Рассмотрим следующую матрицу:< /p>

Код: Выделить всё

matrix = [
[1, 2, None, None],
[None, None, 3, 4],
[3, 5, None, None]
]

Теперь я хочу вставить новую строку:

Код: Выделить всё

new_row = [None, 1, 6, None]

Мой текущий подход проверяет разрешенные диапазоны чисел в новой строке. Он обнаруживает:

• Код: Выделить всё

  1

  можно размещать только над первой строкой.

• Код: Выделить всё

  6

  может быть размещен только после второй или третьей строки.
  Поскольку допустимые диапазоны для 1 и 6 не пересекаются, алгоритм приходит к выводу, что вставка новой строки невозможна. Однако мы можем увидеть это, изменив матрицу на:

  Код: Выделить всё

  [
  [None, None, 3, 4],
  [1, 2, None, None],
  [3, 5, None, None]
  ]
  
  

Вопросы:

• Как я могу улучшить логику вставки строки или сортировки матрицы, чтобы она надежно обрабатывала эти случаи?
• Есть ли какие-либо математические концепции или алгоритмы, которые можно было бы применить к этой проблеме и помочь мне оптимизировать или упростить решение? В частности, меня интересует, как идентифицировать и обобщать «отдельные» разделы матрицы, как показано в примере, где два левых столбца независимы от двух правых столбцов.

В моем нынешнем подходе я предполагаю, что нам дана отсортированная матрица и новая строка, которую необходимо вставить, соблюдая при этом следующие правила:

• Каждый столбец остается в порядке возрастания.
• Числа могут появляться в каждом столбце только один раз.
• Если какие-либо числа перекрываются в строке, они должны оставаться в той же строке.

Вот как работает этот подход:

• Проверьте, появились ли числа в новой строке в соответствующих столбцах:
  • Для каждого числа в новой строке алгоритм выполняет поиск, появлялось ли это число уже в соответствующем столбце матрицы.
  • Если число появилось в своем столбце, то номер новой строки должен быть вставлен в ту же строку, что и та, где ранее появлялось число.
• Обрабатывать случаи где числа раньше не появлялись:
  • Если ни одно из чисел в новой строке ранее не появлялось в своих столбцах, алгоритм:
    
    Определяет разрешенный диапазон для каждого вставляемого числа (т. е. позиции, в которых число может быть размещено, сохраняя возрастающий порядок в столбце).
    Находит перекрытие разрешенных диапазонов для всех чисел в новой строке.
  • Если есть допустимое перекрытие, новую строку можно вставить в первую доступную позицию в этом перекрывающемся диапазоне.
• Вернуть false, если действительная позиция не найдена:
  • Если нет перекрываются в разрешенных диапазонах чисел, алгоритм приходит к выводу, что вставить строку без нарушения правил невозможно, и возвращает False.

Подробнее здесь: https://stackoverflow.com/questions/790 ... ng-problem