Suppose, I have an n-dimensional array of integers (for n=1 it's a vector, for n=2 it's a rectangular matrix, for n=3 it's a parallelepiped, etc). I need to reorder elements of the array so that elements in each row, column, etc are in a non-decreasing order.
假设，我有一个n维整数数组（对于n = 1，它是一个向量，对于n = 2，它是一个矩形矩阵，对于n = 3，它是一个平行六面体等）。我需要重新排序数组的元素，以便每行，列等中的元素处于非递减顺序。
- Is it possible for any input array?
- 是否可以输入任何数组？
-
Is the required ordering unique for any input array?I just realized that the answer for this question in general is no, e.g. for square matrices. - 所需的排序是否对任何输入数组都是唯一的？我刚刚意识到这个问题的答案一般是否定的，例如对于方形矩阵。
- Is the required ordering unique for any input array that has different lengths in all dimensions?
- 对于在所有维度上具有不同长度的任何输入数组，所需的排序是唯一的吗？
- What is the fastest algorithm to produce the required ordering?
- 生成所需订购的最快算法是什么？
2 个解决方案
#1
3
Is it possible for any input array?
是否可以输入任何数组？
Yes, if we will look on the array as a single dimension array, with the same number of elements, and then sort it, by traversing it back to the original n-dimensions array, it remains sorted, since for each i1,....,i_k,...,i_m: for all i_k < i_k':
是的，如果我们将数组视为单维数组，具有相同数量的元素，然后对其进行排序，通过将其遍历回原始的n维数组，它将保持排序，因为对于每个i1，... ..，i_k，...，i_m：对于所有i_k
i_1 + n1*i_2 + n2^2*i_3 + .... (n_k-1)^(k-1)(i_k) + ... < i_1 + n1*i_2 + n2^2*i_3 + .... (n_k-1)^(k-1)(i_k') + ...
Thus (the array is ordered):
arr[i_1 + n1*i_2 + n2^2*i_3 + .... (n_k-1)^(k-1)(i_k) + ...] < arr[ i_1 + n1*i_2 + n2^2*i_3 + .... (n_k-1)^(k-1)(i_k') + ...]
Thus (back to original array):
arr[i_1][i_2]...[i_k]... < arr[i_1][i_2]...[i_k']...
As for the 2nd question:
至于第二个问题：
Is the required ordering unique for any input array that has different lengths in all dimensions?
对于在所有维度上具有不同长度的任何输入数组，所需的排序是唯一的吗？
No:
没有：
1 1 1 3
3 4 1 4
5 6 5 6
What is the fastest algorithm to produce the required ordering?
生成所需订购的最快算法是什么？
One solution is suggested already: regard it is a big long array and sort it. Complexity is O(n_1*n_2*...*n_m*log(n_1*n_2*...*n_m))
My gut says if you could do it faster, you could sory faster then O(nlogn), but I have no proof for this claim, so it might be wrong.
已经提出了一种解决方案：认为它是一个很大的长阵列并对其进行排序。复杂性是O（n_1 * n_2 * ... * n_m * log（n_1 * n_2 * ... * n_m））我的直觉说如果你能做得更快，你可以比O（nlogn）更快，但我有没有证据证明这种说法，所以可能是错的。
#2
1
Let me elaborate more about Alptigin Jalayr's idea.
让我详细说明Alptigin Jalayr的想法。
Suppose we have rows sorted, so for the following data, we have a <= b and c <= d.
假设我们对行进行了排序，因此对于以下数据，我们有一个<= b和c <= d。
. .
..., a, ..., b, ...
. .
..., c, ..., d, ...
. .
When a is greater than c, i.e. c <a, then swap of them gives us c < b since a <= b, and a <=d since b <= d (if b > d, we swap b and d as well). In a word, sorting rows first and then columns next can give you the desired matrix.
当a大于c时，即c d，我们也交换b和d ）。总之，首先排序行然后排序下一行可以为您提供所需的矩阵。 ，那么它们的交换给出c>
#1
3
Is it possible for any input array?
是否可以输入任何数组？
Yes, if we will look on the array as a single dimension array, with the same number of elements, and then sort it, by traversing it back to the original n-dimensions array, it remains sorted, since for each i1,....,i_k,...,i_m: for all i_k < i_k':
是的，如果我们将数组视为单维数组，具有相同数量的元素，然后对其进行排序，通过将其遍历回原始的n维数组，它将保持排序，因为对于每个i1，... ..，i_k，...，i_m：对于所有i_k
i_1 + n1*i_2 + n2^2*i_3 + .... (n_k-1)^(k-1)(i_k) + ... < i_1 + n1*i_2 + n2^2*i_3 + .... (n_k-1)^(k-1)(i_k') + ...
Thus (the array is ordered):
arr[i_1 + n1*i_2 + n2^2*i_3 + .... (n_k-1)^(k-1)(i_k) + ...] < arr[ i_1 + n1*i_2 + n2^2*i_3 + .... (n_k-1)^(k-1)(i_k') + ...]
Thus (back to original array):
arr[i_1][i_2]...[i_k]... < arr[i_1][i_2]...[i_k']...
As for the 2nd question:
至于第二个问题：
Is the required ordering unique for any input array that has different lengths in all dimensions?
对于在所有维度上具有不同长度的任何输入数组，所需的排序是唯一的吗？
No:
没有：
1 1 1 3
3 4 1 4
5 6 5 6
What is the fastest algorithm to produce the required ordering?
生成所需订购的最快算法是什么？
One solution is suggested already: regard it is a big long array and sort it. Complexity is O(n_1*n_2*...*n_m*log(n_1*n_2*...*n_m))
My gut says if you could do it faster, you could sory faster then O(nlogn), but I have no proof for this claim, so it might be wrong.
已经提出了一种解决方案：认为它是一个很大的长阵列并对其进行排序。复杂性是O（n_1 * n_2 * ... * n_m * log（n_1 * n_2 * ... * n_m））我的直觉说如果你能做得更快，你可以比O（nlogn）更快，但我有没有证据证明这种说法，所以可能是错的。
#2
1
Let me elaborate more about Alptigin Jalayr's idea.
让我详细说明Alptigin Jalayr的想法。
Suppose we have rows sorted, so for the following data, we have a <= b and c <= d.
假设我们对行进行了排序，因此对于以下数据，我们有一个<= b和c <= d。
. .
..., a, ..., b, ...
. .
..., c, ..., d, ...
. .
When a is greater than c, i.e. c <a, then swap of them gives us c < b since a <= b, and a <=d since b <= d (if b > d, we swap b and d as well). In a word, sorting rows first and then columns next can give you the desired matrix.
当a大于c时，即c d，我们也交换b和d ）。总之，首先排序行然后排序下一行可以为您提供所需的矩阵。 ，那么它们的交换给出c>