將數字映射到N維網格/數組

例如，假設我有一個3維網格/數組，其軸線從1運行到1000（或等效地從0到999）。這個數組有1000^3個元素。將數字映射到N維網格/數組

我想使用Java以確定性的方式將範圍從0到1000^3的單個整數映射到此數組。最好該解決方案將適用於任何尺寸N.

這裏有這樣的功能的僞codish例如：

public Vector<int> nthElement(Vector<int> dims, int n)

所以，如果我這樣稱呼它nthElement([1000, 1000, 1000], 0)它將返回[0, 0, 0]而nthElement([1000, 1000, 1000], 1001)將返回的東西如[999, 1, 0]。

解決方案應該是N維，而不是3，如我的例子。

來源

2010-12-23 lhahne

我認爲1001應該是[0,2,1]，爲什麼999， 1,0？ – 2010-12-23 12:08:54

@Saeed只要它是確定性的，元素的具體順序並不重要。我認爲前1000個數字會映射到[0,0,0]到[999,0,0]，因此1001會是[999,1,0]，但正如我所說，順序並不重要。 – lhahne 2010-12-23 12:12:37

如果[999,0,0]爲1000，則[0,1,0]將爲1001;）。 – 2010-12-23 12:27:32

檢查這個

List<Integer> nthElement(List<Integer> dims, int n){ 
    List<Integer> res = new ArrayList<Integer>(dims.size()); 
    for(Integer cur : dims){ 
     if(n <= 0){ 
      res.add(0); 
     } else { 
      n -= cur; 
      res.add(n >= 0 ? cur -1 : cur + n); 
     } 
    } 
    return res; 
}

UPD使用

的例子

//create list with 3 dimensions using Guava 
    List<Integer> dims = ImmutableList.of(1000, 1000, 1000); 
    //or with standard JDK 
    //List<Integer> dims = new ArrayList<Integer>(3);dims.add(1000);dims.add(1000);dims.add(1000); 

    System.out.println(nthElement(dims, 0)); 
    System.out.println(nthElement(dims, 1000)); 
    System.out.println(nthElement(dims, 1001)); 
    System.out.println(nthElement(dims, 2001));

將打印

[0, 0, 0] 
    [999, 0, 0] 
    [999, 1, 0] 
    [999, 999, 1]

來源

2010-12-23 12:22:18

這是正確的映射算法：

map([X, Y, Z, T, ...], N) = [ 
    N mod X, 
    N div X mod Y, 
    N div X div Y mod Z, 
    N div X div Y div Z (mod ...)? 
    ... 
]

或遞歸

map([X, Y, Z, T, ...], N) = [N mod X, map([Y, Z, T, ...], N div X)]

其中A DIV B爲地板（A/B）。

來源

2010-12-23 12:10:30

聽起來不錯，但它很容易延伸到更高的尺寸？ – lhahne 2010-12-23 12:14:30

你可能要找的是Cantor pairing function。它是爲NxN定義的，因此您可以將它用於任意大的尺寸。正如在維基百科頁面中提到的，它可以歸納爲一個維數n的數組，在你的情況n = 3的情況下工作得很好。

上面的頁面也解釋了反轉函數，所以你可以從給定的數字得到你的座標，這正是你想要的nthElement。

當然，康託只定義了一種可能的方式來走過一個二維的領域。還有其他可能的散步，但這是最流行的方式。

編輯：我應該提到，如果你的數組有矩形尺寸，Cantor配對函數會假設最大類型的維度。所以相關的數字不再在你的數組中。 F.ex.一個大小爲1000x2的數組將被視爲一個1000x1000數組，並且與您實際數組中的條目相對應的數字只會是數字0..1000 * 1000的非連續列表。但是，如果你的三個維度總是相同，那麼這個點可以完全忽略。

回覆評論：逐行和康託配對只是不同的方式來遍歷矩陣空間。 Cantor配對的一個優點是它是根據自然數定義的，因此如果您的矩陣尺寸沒有確切的值，或者您的矩陣隨時間增長，也是適用的。

來源

2010-12-23 12:12:48 Frank

你可以這樣做：

a = Number % (1000 * 1000) 
b = (Number/1000) % 1000 
c = Number/(1000 * 1000)

這是一個映射（唯一的），你可以簡單地做反向

音符2/3 = 0不是。6666

來源

2010-12-23 12:13:33

將數字映射到N維網格/數組

回答

相關問題