Algorithmus zum Generieren aller Punkte in einem N-dimensionalen Raum, die eine gegebene Menge von Bedingungen erfüllen

Question

Ich habe dieses interessante Problem vor ein paar Wochen kennengelernt: Gegeben sei ein n-dimensionaler Raum und ein "step size" -Wert zwischen (0,1 ], erzeugen alle Punkte, die die folgenden Bedingungen erfüllen:

• der Wert jeder Dimension eines Punktes ist ein Vielfaches der „Schrittweite“
• der Wert jeder Dimension eines Punktes im Bereich zwischen 0 und 1 Ein 2D-Punkt (x, y) sollte beispielsweise 0 = < x, y < = 1
• Die Summe der Werte erfüllen alle Dimensionen muss gleich 1 (aktualisiert)

Beispiel

Input:
stepsize = 0,5 und numDimensions = 3 (dh 3D-Raum)

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

Da wir alle möglichen Punkte finden müssen, dachte ich an eine rekursive Lösung. Hier ist mein 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(" "); 
     } 
    } 
} 

Dies scheint richtig zu funktionieren für ein paar Testfälle, die ich versuchte. Beispiel Ausgabe für (stepsize = 0,5f und 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,

Ich habe ein paar Fragen:

1. Ist mein Ansatz dieses Problem richtig zu lösen?
2. Was ist die genaue zeitliche Komplexität meiner Lösung? Ich behauptete, dass es exponentiell war, aber nicht in der Lage war, die zeitliche Komplexität in Bezug auf Anzahl der Dimensionen/Schrittgröße/Anzahl der Punkte korrekt zu artikulieren. Was wäre der beste Ansatz, um Zeitkomplexitäten für das obige Problem und für rekursive Algorithmen wie diese im Allgemeinen zu begründen?
3. Wenn mein Verständnis der exponentiellen Zeitkomplexität korrekt ist, gibt es einen effizienteren Algorithmus, um dieses spezielle Problem zu lösen?

---

EDIT vermisste ich eine dritte Einschränkung: Summe aller Werte einer Dimension auf 1,0 summieren müssen (Entschuldigt, ich diese früher vergessen zu erwähnen).

Answer 1

Ein Freund vorgesehen, um eine gute Lösung für dieses Problem. Wie einige Leute hier in ihren Antworten erwähnt haben, ist es ein Problem, das darauf hinausläuft, alle Möglichkeiten zu erzeugen, eine ganze Zahl 'm' als eine Summe von 'k' nichtnegativen ganzen Zahlen zu schreiben. Hier ist eine link Detaillierung dieses Problems.

Mit Andys Feedback zur Arbeit mit Ganzzahlen, hier ist der aktualisierte Java-Code mit einigen Kommentaren. Bitte das nicht die Java-Anpassung der Lösung von meinem Freund zur Verfügung gestellt ist:

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()); 
} 

1. mein Ansatz stellte sich heraus (und meine Original-Code) falsch war, da ich nicht alle Punkte wurde die Berechnung korrekt - tat der Code nicht Berechnungspunkte, die unterschiedliche Schritte hatten, Beispiel: [0.0 0.2 0.8 0.0].
2. Zeit Komplexität: (wie in der Mathematik Austausch link erwähnt): Es ist gleich der Anzahl der möglichen Punkte, die gegeben ist: C (n + k-1, k-1) wobei n = (1/stepSize) und k = numDimensions. Ein Beispiel: für stepSize = 0,2 (== 5 als eine ganze Zahl) und numDimensions = 4, die Anzahl der möglichen Punkte ist .

Answer 2

1. Ist mein Ansatz zur Lösung dieses Problems korrekt?

Ich habe auf den Code nicht gesucht, aber Ihr Beispiel Ausgabe mehrere Punkte fehlen. Es sollte 27 sein.

Beachten Sie, dass die Verwendung einer for-Schleife mit Fließkommazahlen aufgrund des akkumulierten Fehlers in der Schleifenvariablen zu Problemen führen kann.Es ist besser, eine Schleife auf ganze Zahlen, und teilt sich dann in der Schleife:

for (int i = 0; i <= 9; ++i) { 
    System.out.println(i/9.0); 
} 

anstelle von

for (double i = 0; i <= 1; i += 1.0/9.0) { 
    System.out.println(i); 
} 

(Compare the output of the two - Mitteilung Ungenauigkeiten im zweiten Fall sowie Druck eine weniger Linie)

3. Gibt es einen effizienteren Algorithmus, um dieses spezielle Problem zu lösen?

Es gibt 1 + 1/stepSize Werte für jede Koordinate; Es gibt numDimensions Koordinaten. Daher sollte es (1 + 1/stepSize)^numDimensions eindeutige Punkte in diesem Raum geben. Die optimale Komplexität der Iteration durch alle Punkte ist O((1 + 1/stepSize)^numDimensions).

Answer 3

Sie haben V = ValuesCount = 1 + 1/stepSize mögliche Werte für jede Dimension und nD Dimensionen. Es gibt V Punkte in 1D, V * V Punkte in 2D, V^3 in 3D, V^nD Punkte im nD-dimensionalen Raum.

Beachten Sie, dass Sie alle Punkte erzeugen können Koordinaten in einfachem for-Zyklus

for k = 0..V^nD - 1 
     represent k in V-ary number system 
     m-th digit of k is coordinate of the k-th point in m-th dimension 
    (divide by (V-1) to normalize to range 0..1) 

Beispiel für V = 3, nD = 3 Fall:

k = 15(dec) = 120(trinary) 
    first (right) digit is 0, second is 2, third is 1 
    coordinates (0.0, 1.0, 0.5) 

Answer 4

Jetzt, nach bearbeiten, ist dies absolut anderes Problem.

Diese kombinatorische Aufgabe Erzeugung aller Partitionen der Zahl N zu N + 1 Teile, wenn die Reihenfolge der Teile wichtig ist (Zusammensetzungen). Delphi-Code (teile die Werte durch N, um deine 'Koordinaten' zu erhalten).

Beachten Sie, dass es C (2n, n) solche Zusammensetzungen gibt (C (6,3) = 20), wobei C - Anzahl der Kombinationen.

var 
    Cmp: array of Integer; 
    N, NP, first, nonzero: Integer; 
begin 
    N := 3; 
    NP := N + 1; 
    SetLength(Cmp, NP); //zero filled 
    Cmp[N] := N; 
    #output Cmp array 
    while Cmp[0] <> N do begin 
    first := Cmp[0]; 
    Cmp[0] := 0; 
    nonzero := 1; 
    while Cmp[nonzero] = 0 do 
     Inc(nonzero); 
    Dec(Cmp[nonzero]); 
    Cmp[nonzero - 1] := first + 1; 
    #output Cmp array 
    end; 

Ausgang für N = 2 und N = 3

0 0 2 
0 1 1 
1 0 1 
0 2 0 
1 1 0 
2 0 0 

0 0 0 3 
0 0 1 2 
0 1 0 2 
1 0 0 2 
0 0 2 1 
0 1 1 1 
1 0 1 1 
0 2 0 1 
1 1 0 1 
2 0 0 1 
0 0 3 0 
0 1 2 0 
1 0 2 0 
0 2 1 0 
1 1 1 0 
2 0 1 0 
0 3 0 0 
1 2 0 0 
2 1 0 0 
3 0 0 0