Hello Developer, Hope you guys are doing great. Today at Tutorial Guruji Official website, we are sharing the answer of Algorithm to generate all points in an N-dimensional space satisfying a given set of constraints without wasting too much if your time.
The question is published on by Tutorial Guruji team.
The question is published on by Tutorial Guruji team.
I encountered this interesting problem a few weeks ago: Given an n-dimensional space and a “step size” value that lies between (0,1], generate all points that satisfy the following constraints:
- The value of each dimension of a point is a multiple of the “step size”
- The value of each dimension of a point ranges between 0 and 1 inclusive. For example, a 2D point (x,y) should satisfy 0=<x,y<= 1
- The sum of values of all dimensions must be equal to 1 (Updated)
Example
Input:
stepSize = 0.5 and numDimensions = 3 (i.e., 3D space)
Output:
0.0, 0.0, 1.0
0.0, 0.5, 0.5
0.0, 1.0, 0.0
0.5, 0.0, 0.5
0.5, 0.5, 0.0
1.0, 0.0, 0.0
Since we need to find all possible points, I thought of a recursive solution. Here is my code:
class PointEnumeration {
static class Point {
List<Float> dimensions; //a list of float where index i is the (i+1)'th dimension
Point(Point p) {
this.dimensions = new ArrayList<>();
this.dimensions.addAll(p.dimensions);
}
Point(int size) {
this.dimensions = new ArrayList<>();
for(int i = 0; i < size; i++){
//Initialize all dimensions to 0.0f
this.dimensions.add(0.0f);
}
}
void incr(int pos, float i) {
float val = dimensions.get(pos);
dimensions.set(pos, val + i);
}
void set(int pos, float i) {
dimensions.set(pos, i);
}
float get(int pos){
return dimensions.get(pos);
}
}
static List<Point> findPoints(float stepSize, int numDim) {
if (stepSize > 1) {
return new ArrayList<>();
}
List<Point> res = new ArrayList<>();
for(float i = stepSize; i <= 1; i+=stepSize) {
findPointsHelper(i, numDim, 1.0f, 0, new Point(numDim), res);
}
return res;
}
static void findPointsHelper(float stepSize, int numDim, float sum, int start, Point curr, List<Point> res) {
if (sum == 0.0) {
res.add(new Point(curr));
return;
}
for (int i = start; i < numDim; i++) {
float temp = sum;
float val = curr.get(i);
curr.incr(i, stepSize);
findPointsHelper(stepSize, numDim, sum - stepSize, i + 1, curr, res);
curr.set(i, val);
sum = temp;
}
}
public static void main(String[] args) {
List<Point> res = findPoints(0.25f, 4); //Tried 1.0f, 3 and 0.5f, 3 as well
for (Point p : res) {
for (Float coord : p.dimensions) {
System.out.print(String.valueOf(coord) + ", ");
}
System.out.println(" ");
}
}
}
This seems to work correctly for a few test cases that I tried. Example output for (stepSize=0.5f and numDimensions=3):
0.5, 0.5, 0.0,
0.5, 0.0, 0.5,
0.0, 0.5, 0.5,
1.0, 0.0, 0.0,
0.0, 1.0, 0.0,
0.0, 0.0, 1.0,
I have a few questions:
- Is my approach to solving this problem correct?
- What is the exact time complexity of my solution? I claimed that it was exponential but was unable to correctly articulate the time complexity in terms of number of dimensions/step size/number of points. What would be the best approach to reason about time complexities for the above problem and for recursive algorithms like these in general?
- If my understanding of the time complexity being exponential is correct, is there a more efficient algorithm to solve this particular problem?
EDIT I missed a third constraint: Sum of all values of a dimension must sum to 1.0 (Apologies, I forgot to mention this earlier).
Answer
A friend of mine provided a great solution to this problem. As some people here, mentioned in their answers, it is a problem that boils down to generating all the ways of writing a integer ‘m’ as a sum of ‘k’ non-negative integers. Here is a link detailing this problem.
Incorporating Andy’s feedback of working with integers, here is the updated java code with some comments. Please not this is the java adaptation of the solution provided by my friend:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class PointEnumeration {
static class Point {
//a list of integer where index i is the (i+1)'th dimension
List<Integer> dimensions;
Point(int step, int numDim){
this.dimensions = new ArrayList<>();
for(int i = 0; i < numDim; i++) {
this.dimensions.add(step);
}
}
Point(int step, Point p){
this.dimensions = new ArrayList<>();
this.dimensions.add(step);
this.dimensions.addAll(p.dimensions);
}
int get(int pos) {
return dimensions.get(pos);
}
}
private static List<Point> findPoints(int steps, int numDim){
if(numDim == 1){
//Only one dimension, add the `steps` to the only dimension
return Arrays.asList(new Point(steps, 1));
}
List<Point> result = new ArrayList<>();
if(steps == 0){
//Nothing left, create a point with all zeroes
return Arrays.asList(new Point(0, numDim));
}
//Iterate on the steps
for(int i = 0; i <= steps; i++){
//Recurse on the remaining steps and
//reduce the dimension by 1 (since this dimension will
// be handled in the next for-each loop)
List<Point> remaining = findPoints(steps-i, numDim-1);
for (Point point : remaining) {
//Append the i'th step to the remaining point
Point complete = new Point(i, point);
//This is a complete point for the i'th step
// and current dimension
result.add(complete);
}
}
return result;
}
public static void main(String[] args) {
float stepSize = 0.2f;
int numDim = 4;
int steps = (int) Math.ceil(1.0 / stepSize);
List<Point> res = findPoints(steps, numDim);
for (Point p : res) {
for (int coord : p.dimensions) {
//Convert integer steps to float value
System.out.print(String.valueOf(coord <= 0 ? 0.0f : (coord / (float) steps)) + ", ");
}
System.out.println(" ");
}
System.out.println("Total number of points =" + res.size());
}
- Turns out my approach (and my original code) was wrong, as I was not computing all points correctly – the code did not compute points that had steps different from each other, example: [0.0 0.2 0.8 0.0].
- Time complexity: (as mentioned in the math exchange link): Its equal to the number of possible points that is given by: C(n+k-1, k-1) where n = (1/stepSize) and k = numDimensions. An example: for stepSize = 0.2 (== 5 as an integer), and numDimensions = 4, the number of points possible is 56.
We are here to answer your question about Algorithm to generate all points in an N-dimensional space satisfying a given set of constraints - If you find the proper solution, please don't forgot to share this with your team members.