用於矩陣排序

這個問題的所有解決方案如下這樣：How to sort a 2D Matrix 用於矩陣排序

在前面的問題，OP被詢問如何矩陣排序如行和列進行排序（M [i] [j] < = M [i + 1] [j]和M [i] [j] < = M [i] [j + 1]）。我的答案很簡單：按照一維排列的方式對行進行排序，並對列進行排序。然後我意識到解決方案不是唯一的解決方案。

我的問題是：什麼算法可以給我們這個問題的所有解決方案？一個顯而易見的解決方案將是一個回溯算法，但我敢肯定，我們可以做的更好......對於同一陣列的解決方案

例子：

和：

和：

和：

等...

來源

2013-07-06 Maxime Chéramy

這將是走回頭路了一代人最有效的解決方案，但因爲有許多方法，我提出如下算法（它是僞C++）

int mat[n][m] = {-1}; // initialize all cells with -1 
int sortedArray[n * m]; // the sorted array of all numbers, increasing order 

void generateAllSolutions(set<pair<int, int> > front, int depth) { 
    if (depth == n * m) { 
     printMatrix(); 
     return; 
    } 

    for (pair<int, int> cell : front) { 
     mat[cell.first][cell.second] = sortedArray[depth]; 
     newFront = front; 
     newFront.remove(cell); 
     if (cell.first < n - 1 && 
       (cell.second == 0 || mat[cell.first + 1][cell.second - 1] != -1)) { 
      newFront.add(<cell.first + 1, cell.second>); 
     } 
     if (cell.second < m - 1 && 
       (cell.first == 0 || mat[cell.first - 1][cell.second + 1] != -1)) 
      newFront.add(<cell.first, cell.second + 1>); 
     } 
     generateAllSolutions(newFront, depth + 1); 
     mat[cell.first][cell.second] = -1; // backing the track 
    } 
} 

void solve() { 
    set<pair<int, int> > front = {<0, 0>}; // front initialized to upper left cell 
    generateAllSolutions(front, 0); 
}

我正在做的是保持所有可能的候選人的所有單元的「前面」，以用於下一個最小的數字。這些基本上都是其上層和左邊鄰居已經填充了較小數字的所有單元格。

由於我提出的算法可以優化使用所有解決方案中所有單元數量大小的操作，因此這應該是您的任務在性能方面最佳的解決方案。

我不知道是否有任何聰明解決方案，如果你的目標僅在計算所有可能的解決方案（I可以立即設備大小O（分鐘（米^Ñ，正^米））中的溶液

來源

2013-07-06 09:52:18

如果元素全部不同，我相信你可以使用[鉤子長度公式]（http://en.wikipedia.org/wiki/Hook-length_formula#Dimension_of_a_representation）來計算解決方案，但我不知道如何當你有重複的條目時將其擴展到這種情況。 –

一些修剪改進回溯算法的：

注意的是，例如在5 4排序矩陣M，

M[0][0]是最小的所有元素的設置S和M[4][3]是最大值。

M[0][1]和M[1][0]是兩個最小S - ({M[0][0]}∪{M[4][3]})，而

M[3][3]和M[4][2]是兩個最大在它。

只有2 * 2的情況。

類似地，M[1][1]是最小值，M[3][2]是S - {M[0][0],M[4][3],M[0][1] , M[1][0],M[3][3] , M[4][2]}中的最大值，這是確定的。

來源

2013-07-06 09:52:46 vvy

用於矩陣排序

回答

相關問題