Mappare un numero a un N dimensionale griglia / array

Question

Consente assumere, per esempio, che ho un 3-dimensionale griglia / array in cui la corsa dell'asse da 1 a 1000 (o equivalentemente 0 a 999). Questa matrice ha 1000 ^ 3 elementi.

Vorrei mappare un singolo intero nell'intervallo da 0 a 1000 ^ 3 a questo array in modo deterministico utilizzando Java. Preferibilmente questa soluzione potrebbe funzionare per qualsiasi dimensione N.

Ecco un esempio di pseudo-codish di tale funzione una:

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

Quindi, se ho lo chiamerei come nthElement([1000, 1000, 1000], 0) che sarebbe tornato [0, 0, 0] mentre nthElement([1000, 1000, 1000], 1001) restituirebbe qualcosa come [999, 1, 0].

La soluzione deve essere per N dimensioni e non per 3 come nel mio esempio.

Answer 1

controllare questo

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 esempi d'uso

    //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));

stamperà

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

Answer 2

Questo è l'algoritmo di mappatura corretta:

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 ...)?
    ...
]

o ricorsiva

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

Dove A div B è al piano (A / B).

Answer 3

Si può fare:

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

Si tratta di una mappatura (unico), e si può semplicemente fare retromarcia

nota 2/3 = 0 non 0,6666

Answer 4

Quello che state cercando è probabilmente il Cantor funzione coppia . Si è definito per NxN, in modo da poterlo utilizzare per arbitrariamente grandi dimensioni. Come accennato nella pagina di wikipedia può essere induttivamente generalizzato a un array di dimensione n, nel tuo caso n = 3 funziona bene.

La pagina di cui sopra spiega anche invertendo la funzione, in modo da poter ottenere le coordinate della matrice dal numero dato, che è esattamente quello che vuoi con nthElement.

Naturalmente, Cantor ha definito un solo modo possibile camminare attraverso un campo bidimensionale. Ci sono altre passeggiate possibili, ma questo è il modo più popolare per farlo.

Edit: Devo dire, che se l'array ha dimensioni rettangolari la funzione coppia Cantor avrebbe assunto dimensioni del più grande tipo. Così i numeri associati non sono più in successione all'interno del vostro array. F.ex. un array di dimensione 1000x2 sarà trattato come una matrice 1000x1000 ed i numeri corrispondenti alle voci nella matrice reale sarebbe solo un elenco non in successione dei numeri 0..1000 * 1000. Se, tuttavia, i tuoi tre dimensioni sono sempre gli stessi, allora questo punto può essere totalmente ignorato.

In risposta al commento: Riga per riga e Cantor abbinamento sono modi diversi solo per camminare attraverso il vostro spazio di matrice. Un vantaggio di Cantor accoppiamento è che si è definito nel corso dei numeri naturali e quindi anche è applicabile se non si dispone di valori esatti per le dimensioni della matrice, o la vostra matrice cresce nel tempo.