Traversal of an n-dimensional space

Go To StackoverFlow.com

7

I'm trying to write an algorithm that will let me iterate over all desired points within an n-dimensional space to find the minimum of a function f(x) where x is a vector of size n.

Obviously, searching a 2-d or 3-d space is fairly straightforward, you can simply do:

for(int i = 0; i < x; i++) {
    for(int j = 0; j < y; j++) {
        //and so on for however many dimensions you want

Unfortunately, for my problem, the dimensionality of the space is not fixed (I'm writing a generalised minimum finder for many functions in a statistical program) and so I'd have to write loops for each value of n I want to use - which might ultimately be rather large.

I've been trying to get my head around how I could do this using recursion but can't quite see the solution - although I'm sure there is one there.

The solution doesn't have to be recursive, but it must be general and efficient (the inner most line in that nested loop is going to get called an awful lot...).

The way I'm representing the volume to search is a 2d array of double:

double[][] space = new double[2][4];

This would represent a 4d space with the minimum and maximum bound in each dimension in position 0 or 1 of the array, respectively. Eg:

dim         0   1   2   3
    min(0):-10  5  10  -0.5
    max(1): 10 55  99   0.2

Any ideas?

2012-04-05 22:29
by Chilly
I'm not actually new, I just lost my account from ages ago : - Chilly 2012-04-05 22:32
How do you handle the range with decimals, i.e., -0.5 to 0.2? Also, what data will you need in the inner loop to process it? An array of points - mellamokb 2012-04-05 22:32
However, I don't think my brain works very well with recursion (lack of practice, probably) so haven't tried anything yet - just been staring at my garage wall trying to visualise it - Chilly 2012-04-05 22:32
You wouldn't necessarily need recursion. You could use an array of search indices - mellamokb 2012-04-05 22:33
You may draw some inspiration from e.g. this question, as it's an equivalent problem: http://stackoverflow.com/questions/8804852/generate-all-tuples-with-c-better-way-than-nested-loops (I'm shamelessly promoting it because I have the accepted answer there...) There's a recursive and an iterative solution presented - Oliver Charlesworth 2012-04-05 22:33
mellamokb: I use a resolution function generate the step sizes I need for each dimension. I wouldnt actually be using int i = 0; i < 10; i++ I'd be using double i = 0; i < 0.44; i+=0.00 - Chilly 2012-04-05 22:33
@OliCharlesworth : that solution you posted looks promising. I'll have to come back to it in the morning, though, very tired right now from coding this thing up all day! Cheers - Chilly 2012-04-05 22:44
Depending on what kinds of functions you are using, there may be some calculus knowledge that can decrease the space size you need to search, such as finding the minima and maxima of the derivative of your main function - mellamokb 2012-04-05 23:07
I've already written a simulated annealer for the weirder functions, this one is for use with more well behaved functions - Chilly 2012-04-06 08:38


5

Here is the general idea:

interface Callback {
   void visit(int[] p); // n-dimensional point
}

// bounds[] - each number the limits iteration on i'th axis from 0 to bounds[i]
// current - current dimension
// callback - point
void visit(int[] bounds, int currentDimension, int[] p, Callback c) {
   for (int i = 0; i < bounds[currentDimension]; i++) {
        p[currentDimension] = i;
        if (currentDimension == p.length - 1) c.visit(p);
        else visit(bounds, currentDimension + 1, p, c);
   }
}

/// now visiting
visit(new int[] {10, 10, 10}, 0, new int[3], new Callback() {
   public void visit(int[] p) {
        System.out.println(Arrays.toString(p));
   }
});
2012-04-05 22:36
by Eugene Retunsky
That should be currentDimension + 1, not currentDimension++, then it works perfectly. Otherwise + - mellamokb 2012-04-05 22:42
I take that back. There are a few miscellaneous issues with this solution that I've taken the liberty to fix via editing, hope it's ok - mellamokb 2012-04-05 23:17
This is probably about the best you can get. Your solution takes about 50 ms average for me to run from {0,0,0,0} to {50,50,50,50}: http://ideone.com/oxJDe. I have made it ever-so-slightly faster (about 40 ms) by getting rid of the recursion here: http://ideone.com/uJ4j - mellamokb 2012-04-05 23:35
Thanks for fixing my solution. Just typed in a couple of minutes while was running away :) Yes, if I initially typed currentDimension++ that was obvious mistake. Also it should have been == p.lenght -1 - Eugene Retunsky 2012-04-06 00:18
Nice for integer indexes, but gets a bit tricky with real ones - Chilly 2012-04-06 08:26
Ah, but its easy to map a real index onto a fixed integer range. This is excellent - Chilly 2012-04-06 08:34


2

I'd stick with reucrsion, and use Object as a parameter, with an extra parameter of dim, and cast it when you reach a depth of 1 to the relevant array [in my example, it is an int[]]

public static int getMin(Object arr, int dim) {
    int min = Integer.MAX_VALUE;
    //stop clause, it is 1-dimensional array - finding a min is trivial
    if (dim == 1) { 
        for (int x : ((int[])arr)) {
            min = Math.min(min,x);
        }
    //else: find min among all elements in an array of one less dimenstion.
    } else { 
        for (Object o : ((Object[])arr)) { 
            min = Math.min(min,getMin(o,dim-1));
        }
    }
    return min;
}

example:

public static void main(String[] args) {
    int[][][] arr = { { {5,4},{2}, {35} } , { {2, 1} , {0} } , {{1}}};
    System.out.println(getMin(arr, 3));
}

will produce:

0

The advantage of this approach is no need for any processing of the array - you just send it as it is, and send the dimension as a parameter.
The downside - is type [un]safety, since we dynamically cast the Object to an array.

2012-04-05 22:38
by amit


1

Another option is to iterate from 0 to x*y*z*... like you do when converting a number between binary and decimal representations. This is a non-recursive solution, so you won't run into performance issues.

ndims = n;
spacesize = product(vector_sizes)
int coords[n];

for (i = 0; i < spacesize; i++) {
    k = i;
    for (j = 0; j < ndims; j++ ) {
         coords[j] = k % vector_sizes[j];
         k /= vector_sizes[j];
    }
    // do something with this element / these coords
}
2012-04-05 22:45
by j13r
This is a non-recursive solution, so you won't run into performance issues. That's not really a relevant statement. The recursive solutions are actually probably more efficient because they don't have to keep repopulating the inner array, and the recursion level is never more deep than the number of dimensions. Plus, your solution is going to have trouble with rounding errors since the values are all doubles - mellamokb 2012-04-05 22:46
You will call spacesize many functions (the full tree), and with that pass the coords (p in Eugenes solution) either by copying or by pointer. You will do more work - j13r 2012-04-05 22:51
There will not be rounding errors if you have coords[j] = stepfunction(k, vector_sizes[j]) and double coords - j13r 2012-04-05 22:54
For example, I did some profiling of your solution against @Eugene's solution. Running from {0,0,0,0} to {50,50,50,50}, your solution takes about 650 ms, while @Eugene's takes around 50 ms. And in case you don't believe me, take a look at http://ideone.com/oxJDe and http://ideone.com/nUdrl, which are my working implementations of both solutions with outputs and timings - mellamokb 2012-04-05 23:12
Interesting. I didn't expect that - j13r 2012-04-06 00:00


1

n-dimensional arrays can be flattened into one-dimensional arrays. What you need is to do the math for these things:

  • Calculate the size of the unidimensional array needed.
  • Figure out the formulas needed to translate back from the n-dimensional index to the unidimensional one.

This is what I'd do:

  • Represent n-dimensional array sizes and indexes as int[]. So, the size of a 5x7x13x4 4-dimensional array represented as the 4-element array `{ 5, 7, 13, 4 }'.
  • An n-dimensional array is represented as a unidimensional array whose size is the product of the sizes of each of the dimensions. So a 5x7x13x4 array would be represented as a flat array of size 1,820.
  • An n-dimensional index is translated into a unique index in the flat array by multiplication and addition. So, the index <3, 2, 6, 0> into the 5x7x13x4 array is translated as 3 + 2*5 + 6*5*7 + 0*5*7*13 == 223. To access that 4-dimensional index, access index 223 in the flat array.
  • You can also translate backwards from flat array indexes to n-dimensional indexes. I'll leave that one as an exercise (but it's basically doing n modulo calculations).
2012-04-05 23:04
by Luis Casillas
java supports jagged arrays. Won't it fail for these? [i.e: {{1,2,3},{1}} - amit 2012-04-05 23:17
@amit: I was going to comment on your answer. The OP isn't looking for jagged arrays. They're looking to search the entire n-dimensional grid space - mellamokb 2012-04-05 23:22
Then this solution fits. IMO, you should add an explicit indication for it, for future readers - amit 2012-04-05 23:25


0

Isn't the function just:

Function loopDimension(int dimensionNumber)
    If there is no more dimension, stop;
    for(loop through this dimension){
         loopDimension(dimensionNumber + 1);
    }
2012-04-05 22:35
by Alderath


0

This runs through a List of List of values (Integers) and picks the minimum of each List:

import java.util.*;
/**
    MultiDimMin

    @author Stefan Wagner
    @date Fr 6. Apr 00:37:22 CEST 2012

*/
public class MultiDimMin
{
    public static void main (String args[])
    {
        List <List <Integer>> values = new ArrayList <List <Integer>> ();
        Random r = new Random ();
        for (int i = 0; i < 5; ++i)
        {   
            List<Integer> vals = new ArrayList <Integer> ();            
            for (int j = 0; j < 25; ++j)
            {   
                vals.add (100 - r.nextInt (200));   
            }
            values.add (vals);
        }
        showAll (values);
        List<Integer> res = multiDimMin (values);
        show (res);
    }

    public static int minof (List <Integer> in)
    {
        int res = in.get (0);
        for (int v : in)
            if (res > v) res = v;
        return res;
    }

    public static List<Integer> multiDimMin (List <List <Integer>> in)
    {
        List<Integer> mins = new ArrayList <Integer> ();
        for (List<Integer> li : in) 
            mins.add (minof (li));
        return mins; 
    }

    public static void showAll (List< List <Integer>> lili)
    {
        for (List <Integer> li : lili) {
            show (li);
            System.out.println ();
        }
    }   

    public static void show (List <Integer> li)
    {
        for (Integer i: li) {
            System.out.print (" " + i);
        }
        System.out.println ();
    }   
}
2012-04-05 23:06
by user unknown
Ads