我有一堆元组,我想根据以下规则插入到二维矩阵中:
- 如果元组的第一个元素大于或等于前一个元组中的第一个元素,则该元组可以位于另一个元组(在同一行中)的右侧。
- 如果元组中的第二个元素大于或等于前一个元组中的第二个元素,则元组可以位于元组之下(在同一列中)。
这是一个可接受的解决方案示例:
(1,2) (2,1) (4,5)
(8,6) (9,2) (9,8)
换句话说,元组按列按元组中的第二个元素排序,按行按第一个元素排序。我意识到这些规则不能总是 100% 得到满足,但我需要想出一种算法来最大限度地减少违反规则的次数。
提前致谢。
最佳答案
我们绝对可以完全避免行或列违规,但同时避免两者取决于数据的礼貌而不是算法。
这是我想出的。
让我们假设一个维度为 nX2n 的二维数组。
第 1 步:根据第一个元素对所有元组进行排序,我们称之为 TUP_1。
第 2 步:根据第二个元素对所有元组进行排序,我们称之为 TUP_2。
第 3 步:
i=0
while(i<n)
{
Pick first n tuples(unmarked) from TUP_2 which are at Positions a,b,c......
in TUP_1 such that a < b < c and so on.
Mark the picked tuples.
fill the ith row with:
first element from tuples in even positions.
second element from tuples in odd positions.
increment i.
}
注意:以上算法由于条件
a < b < c would always avoid any violation in row.
但是,如果
the elements from TUP_2 are always picked in order without any skipping.
如果不是,则可能会发生列违规。
示例:让我们假设 3X4 矩阵
让输入包含以下元组。
(12,6) (12,1) (2,1) (11,1) (8,6) and (4,5).
排序,基于第一个元素的元组将给出 TUP_1
(2,1) (4,5) (8,6) (11,1) (12,1) and (12,6).
根据第二个元素对元组进行排序将得到 TUP_2
(2,1) (11,1) (12,1) (4,5) (8,6) (12,6).
现在执行第3步
(2,1) and (11,1) get picked up from TUP_2 because the tuples are at position
1 and 4 in TUP_1 and 1 < 4 and first row is filled as.
(2,1),(11,1)
(12,1) and (12,6) get picked up from TUP_2 because the tuples are at position
5 and 6 in TUP_1 and 5 < 6 and second row is filled as.
(12,1),(12,6)
(4,5) and (8,6) get picked up from TUP_2 because the tuples are at position
2 and 3 in TUP_1 and 2 < 3 and third row is filled as.
(4,5),(8,6)
因此,3X4 矩阵是:
(2,1),(11,1)
(12,1),(12,6)
(4,5),(8,6)
关于arrays - 按行和按列对元组进行排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31564984/