需要求助算法通過鋸齒陣列來解決索引

唉！我知道我最終會得到這一點，但在這一點上，我差不多2個小時，仍然陷入困境。需要求助算法通過鋸齒陣列來解決索引

我需要解決針對特定位置的鋸齒陣列的每個「級別」的單獨索引。這很難解釋，但如果你想象一個3級鋸齒陣列[2,3,4]長度。如果你接下來要把它變成一個單一的數組，那麼它的大小就是24個。現在，假設你需要找到這些索引（每個級別的鋸齒形數組一個索引），它將等於單個數組索引22.它會是1,2,1。要弄清楚單個場景並不難，但我想知道算法是如何解決可變深度鋸齒陣列的這些值的。

這是我目前嘗試的一個簡單的代碼示例：

using System; 

class Program 
{ 
    static void Main(string[] args) 
    { 
     // Build up the data and info about level depth 
     int[] levelDepth = new[] { 2, 3, 4 }; 
     int[][][] data = new int[][][] 
     { 
      new int[][] { new int[4], new int[4], new int[4] }, 
      new int[][] { new int[4], new int[4], new int[4] } 
     }; 

     int requestedValue = 22; 
     float temp = requestedValue; 

     // Store the index of each level array to get to the index 
     // for the requested value 
     int[] levelIndexes = new int[3] { 0, 0, 0 }; 

     // The following does not work! 
     int i = levelDepth.Length; 
     while (i > 0) 
     { 
      temp = temp/levelDepth[i - 1]; 
      levelIndexes[i - 1] = (int)Math.Round(temp); 

      i--; 
     } 
    } 
}

它不能正常工作，但它幾乎讓我我需要什麼，但我認爲這只是可遇不可求。我懷疑這是一個以前解決的常見問題，我只是沒有經驗來弄清楚。 :(

此外，在任何人告訴我使用這樣的數組是非常糟糕的或「爲什麼不存儲你的數據是這樣的」 - 上面的描述和代碼是模擬一些解碼器芯片在我們的硬件上的佈局和我需要找出一種方法來解決，以級聯芯片的特定圖形的路徑;上面的例子正好芯片的佈局相匹配，我堅持了下來

來源

2011-08-24 Steve K

您是否需要實際的指標，或者僅僅是實際指標的值？ – drharris

@drharris - 指數 –

您不應該在這裏使用float s。

int[] levelDepth = new[] { 2, 3, 4 }; 
int requestedValue = 22; 
int[] levelIndexes = new int[levelDepth.Length]; 


for (int i = 0; i < levelDepth.Length; i++) 
{ 
    // need to go from { 2, 3, 4 } -> { 3*4, 4, 1 } 
    int f = 1; 
    for (int j = i+1; j < levelDepth.Length; j++)  
    f *= levelDepth[j]; 

    levelIndexes[i] = requestedValue/f; // integer divide 
    requestedValue = requestedValue % f; 
}

來源

2011-08-24 08:24:30

Modulo！ - 這就是我所缺少的（好吧，也許還有更多的部分）您的解決方案運行良好，並將動態處理變化的深度圖，這很重要。我也喜歡我們放棄浮動使用，這也是我的煩惱。 –

只是一個說明，你似乎不需要鋸齒（數組數組）。 'int [,,] data = new int [2,3,4];'會做，然後'GetLength（level）'可以代替'levelDepth []'。 –

該算法是否在教科書中？它解決了我的問題，但我一直在努力尋找一個參考（除了permalinking這個答案）。 – Jon

假設你需要在該點元素的值。（而不是具體的指數），你可以簡單地執行一個類似ruby的flatten，然後直接訪問索引

編輯：對不起，誤會，可能會有所幫助。米的Microsoft Visual C＃NET 2003開發食譜（馬克施密特）：

static int[] GetDimensionIndices(int flatIndex, Array array) 
{ 
    int[] indices = new int[array.Rank]; 
    int p = 1; 
    for(int i = array.Rank - 1; i >= 0; i--) 
    { 
     indices[i] = (((flatIndex/p)) % (array.GetUpperBound(i)+1)); 

     if(i > 0) 
      p *= array.GetUpperBound(i) + 1; 
    } 
    return indices; 
}

來源

2011-08-24 08:05:31 drharris

對不起，我不清楚在第一篇文章;我需要索引 –

我已經用我在書中找到的潛在解決方案更新了我的答案。 – drharris

如果我可以選擇兩個答案，這也是一個有趣的解決方案。感謝您發佈樣本！ –

長度爲2的數組保持長度爲3的陣列，其保持長度的陣列4

因此，第一陣列上的索引會使您的總指數增加3 * 4 = 12。上第二陣列

指數將由4.

第三陣列上索引增量你的總將由1.

所以，22 = 12 * 1 + 4 * 2 + 1 * 1遞增你的總。

在找出這些數字（將levelDepth中的值相乘）之後，可以簡單地使用從最外層數組開始的貪婪算法。

int temp = requestedValue; 
int levelWeight[] = {levelDepth[2]*levelDepth[1], levelDepth[2], 1}; 
for(int i=0;i<3;i++){ 
    while(requestedValue >= levelWeight[i]){ 
     levelIndexes[i]++; 
     requestedValue-=levelWeight[i]; 
    } 
}

來源

2011-08-24 08:09:37 bdares

感謝您的示例。我認爲你錯過了一個溫度遞減（例如temp - = levelWeight [i]）。另外最後一個索引被錯誤地解析爲2而不是1 –

其實，我在最終的索引評論上是不正確的; 2是正確的值 –

需要求助算法通過鋸齒陣列來解決索引

回答

相關問題