Sorting Row-Wise and Column-Wise Sets
I have a bunch of tuples that I want to insert into a 2D matrix according to the following rules:
- A tuple can go to the right of another tuple (on the same line) if the first element of the tuple is greater than or equal to the first element of the previous tuple.
- A tuple can go under a tuple (in the same column) if the second element in the tuple is greater than or equal to the second element of the previous tuple.
This is an example of an acceptable solution:
(1,2) (2,1) (4,5) (8,6) (9,2) (9,8)
In other words, by column, tuples are sorted by the second element in the tuple and by row by the first element. I understand that these rules may not always be 100% satisfied, but I need to think about an algorithm that minimizes the number of rule violations.
Thanks in advance.
source to share
We can completely avoid any column violations or , but avoiding both at the same time depends on the politeness of the data, not the algorithm .
Here's what I came up with.
Suppose a 2-dimensional array of size nX2n.
Step 1 . Sorting all tuples based on the first element, lets call it TUP_1.
Step 2 . Sorting all tuples based on the second element, lets call it TUP_2.
Step 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.
}
Note . The above algorithm due to condition
a < b < c would always avoid any violation in row.
However, it would completely avoid breaking the column if
the elements from TUP_2 are always picked in order without any skipping.
If it is not, there is a chance that column violations could occur.
An example . Suppose a 3X4 matrix
Let the input contain the following tuples.
(12,6) (12,1) (2,1) (11,1) (8,6) and (4,5).
Sorting, tuples based on first element will give TUP_1
(2,1) (4,5) (8,6) (11,1) (12,1) and (12,6).
Sorting tuples based on the second element will give TUP_2
(2,1) (11,1) (12,1) (4,5) (8,6) (12,6).
Performing step 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)
Hence the 3X4 matrix:
(2,1),(11,1) (12,1),(12,6) (4,5),(8,6)
source to share