按行和列排序元组

Question

我有一堆元组需要根据以下规则插入到二维矩阵中：

1. 如果元组的第一个元素大于或等于前一个元组的第一个元素，则该元组可以放在另一个元组右边（在同一行中）。
2. 如果元组的第二个元素大于或等于前一个元组的第二个元素，则该元组可以放在另一个元组下方（在同一列中）。

这是一个可接受解决方案的示例：

(1,2) (2,1) (4,5)  
(8,6) (9,2) (9,8)

换句话说，按列排序元组的第二个元素，按行排序元组的第一个元素。我知道这些规则不一定总是100％满足，但我需要考虑一种算法来最小化违反规则的次数。

谢谢。

- user3396592

---

你有行数和列数的要求吗？否则你可以把它们都放在一行里。 - shapiro yaacov

不，肯定有多于1行/列。至少每个维度都有5个。 - user3396592

Answer 1

我们绝对可以完全避免行或列的违规，但同时避免两者取决于数据而不是算法的礼貌。

以下是我的想法。

假设一个 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)

- Sumeet

---

抱歉，我应该澄清一下 - 在排序之前和之后，元组必须保持不变，即元素不能混合。 - user3396592

@user3396592 我从来没有打算混合这些元素。请告诉我在哪里混合了这些元素，给予建议。 - Sumeet

@user3396592 对于元组的第一个和第二个元素，元组保持不变。 - Sumeet

可以...你能通过一个3x4的例子来解释吗？ - user3396592

@user3396592 我更新了我的回答。 - Sumeet