独特矩阵排序问题的算法/逻辑

Question

我有一个矩阵排序问题，其中每行至少包含两个数字，其余列是

None

。我需要对这个矩阵进行排序：

• 每列均按递增顺序排列，数字之间允许有

  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

  。

问题示例：

考虑以下矩阵：

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]
  ]
  
  

问题：

• 如何改进插入行或对矩阵进行排序的逻辑，以便它能够可靠地处理这些情况？
• 是否有任何数学概念或算法可以应用于这个问题并帮助我优化或简化解决方案？具体来说，我对如何识别和概括矩阵的“独立”部分感兴趣，如示例所示，其中左侧两列独立于右侧两列。

在我当前的方法中，我假设我们得到一个排序矩阵和一个需要插入的新行，同时保持以下规则：

• 每列保持递增顺序。
• 数字在每列中只能出现一次。
• 如果任何数字在一行中重叠，它们必须保持在同一行。

该方法的工作原理如下：

1. 检查新行中的数字是否出现在各自的列中:

   • 对于新行中的每个数字，算法会搜索该数字是否已出现在矩阵中相应的列中。
   • 如果某个数字已出现在其列中，则新行的数字必须插入到与先前出现该数字的行相同的行中。

2. 处理之前没有数字出现的情况:

   • 如果新行中的数字都没有出现在之前的列中，则算法：
     • 确定要插入的每个数字的允许范围（即在保持列中递增顺序的同时可以放置数字的位置）。
     • 查找新行中所有数字的允许范围的重叠。
     • 如果存在有效重叠，则可以将新行插入到该重叠范围内的第一个可用位置。

3. 如果没有找到有效位置则返回 false:

   • 如果数字的允许范围内没有重叠，则算法得出结论，在不违反规则的情况下不可能插入行并返回

     False

     。

Answer 1

我认为尝试将其视为一个矩阵不会做出任何贡献，而是将其视为项目的集合，每个项目都有一个数字列表。

该算法分为 3 个连续的步骤

1. 根据您的“有效组合”组合任何可以组合的物品
2. 对项目进行排序。根据对数字列表中第一项进行排序的比较，如果第一个数字为“无”，则移至数字列表中的第二项......，如果没有重叠，则您不在乎
3. 检查每个列是否已同时排序，如果有错误则返回false。

算法结束后，如果需要，您可以再次构建矩阵。