Creating all possible combinations of points

Question

I want to create all possible combinations of points (0,0),(0,1)...(12345,6789) and then all segments from these points.

The code I have written is simple and with no optimization. Is there any algorithm to generate it in less time?

public static void main(String[] args) {
    int m=12345;
    int n=6789;

    for(int x1=0;x1<=m;x1++)
    {
        for(int y1=0;y1<=n;y1++)
        {
            for(int x2=0;x2<=m;x2++)
            {
                for(int y2=0;y2<=n;y2++)
                {
                    for(int x3=0;x3<=m;x3++)
                    {
                        for(int y3=0;y3<=n;y3++)
                        {
                            for(int x4=0;x4<=m;x4++)
                            {
                                for(int y4=0;y4<=n;y4++)
                                {       
                                    Point p1 = new Point(x1, y1);
                                    Point p2 = new Point(x2, y2);
                                    Point p3 = new Point(x3, y3);
                                    Point p4 = new Point(x4, y4);

                                    Segment s1 = new Segment(p1, p2);
                                    Segment s2 = new Segment(p2, p3);
                                    Segment s3 = new Segment(p3, p4);
                                    Segment s4 = new Segment(p4, p1);

                                    //operate on those segements

                                }
                            }
                        }
                    }
                }
            }
        }
    }
}

Answer 1

Google Guava has a cartesianProduct helper method, I would try to use it instead of the nested loops. I don't think that it will be faster but it would be easier to read an maintain.

Answer 2

Given the large size of the potential result set, the previously suggested iteration mechanism seems appropriate.

I looked at this and thought 'nice challenge', and I looked at your code, and figured there were too many loops. The way I see you doing the work inside the loops also looks cumbersome...

I figured it would be 'neat' to have a generator that created all the segments on an as-needed basis, and did not do the actual work.... then I played with it, and found there were some potential optimizations.

So, the parts of your code that are potential performance problems:

• you re-create Point instances much more than you need to... I can reduce by at least 24 times the amount of point creation you do.
• your problem space is two separate things, you have a combination problem, and also a permutation problem. If you solve them separately, you can pre-calculate the permutations and not have to do them multiple times, then you can just reuse the same points in each permutation.

So, with that in mind, I 'played' with your code. This is not a review of your code, but, rather, it is the result of me solving your problem in a different way. There are pro's and con's to my solution... so, use it with appropriate care. The goal of my 'refactoring' was to hit a usage-model something like:

        for (Segment[] sides : new SegmentGenerator(m, n)) {
            // do something with this set of segments.
        }

One note to consider first.... it is a 'common' model when doing matrix-operations in high-performance computing, to 'flatten' the matrix in to a single dimension. For example, a 3x3 matrix will be flattened in to a single-dimension of 9. The (row,column) indices in the flattened matrix are calculated as follows (row = matrix-row, col = matrix-column, and flat = one-D index)

flat = row * width + col;
row = flat / width;
col = flat % width;

By doing this flattening of the data you can halve the number of loops you need (you only need one loop to access the entire matrix), and you reduce the number of physical arrays (and the memory-separation) of those arrays.

I have employed this type of logic in the solution....

Pro's:

• it precomputes all the Permutations for the number of segments in each result.
• you can easily adjust it to do any number of 'sides', not just 4.
• it exposes things neatly in an Iterable engine, which allows you to do some neat code when using it.
• you can probably use this to 'feed' a parallel process where each thread processes chunks of results.
• it reuses Point instances a lot.... in fact, a huge amount less duplication than your code (I am guessing it is something approximately like m*(X!) times fewer Point instances where m is the width of the matrix, and X is the number of sides. So, for example a 100-wide matrix with 4-sided segments will create (100 * 24), or 2400 times fewer Point instances.... put another way, it will reuse Points 2400 times.

Con's

• the logic is always a bit more complicated when you add the flexibility of an Iterator
• because of the Point re-use, you may have conditions where Point a == Point b whereas in your code no two points are ever identity-equals(==).

Note that you get a lot of duplication of values because you allow overlapping points. This appears to be a requirement of yours. Still, for example, by design, you will get 24 identical results each with the segments: [P(0,0), P(0,0), P(0,0), P(0,0)] If you want to reduce the results to unique solutions only, then it is a relatively trivial adjustment to the way the cursors array is managed.... (relatively).

So, with all those caveats, here is some working code:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;
import java.util.NoSuchElementException;

public class Quadrilaterals implements Iterable<Quadrilaterals.Segment[]> {

    public static final class Point {
        private final int x, y;

        public Point(int x, int y) {
            super();
            this.x = x;
            this.y = y;
        }

        @Override
        public String toString() {
            return String.format("P(%d,%d)", x, y);
        }

    }

    public static final class Segment {
        private final Point a, b;

        public Segment(Point a, Point b) {
            super();
            this.a = a;
            this.b = b;
        }

        @Override
        public String toString() {
            return String.format("S(%s,%s)", a, b);
        }
    }

    // used to initialize a static array of permutations.
    private static final void permuteRecursion(final int[] current,
            final int[] available, final List<int[]> results) {
        if (available.length == 0) {
            results.add(current);
            return;
        }
        for (int i = 0; i < available.length; i++) {
            int[] nextc = Arrays.copyOf(current, current.length + 1);
            nextc[current.length] = available[i];
            int[] nexta = new int[available.length - 1];
            System.arraycopy(available, 0, nexta, 0, i);
            System.arraycopy(available, i + 1, nexta, i, nexta.length - i);

            permuteRecursion(nextc, nexta, results);

        }
    }

    // used to initialize a static array of permutations of `value` size
    // e.g. permute(1) => [ [0] ];
    //      permute(2) => [ [0,1], [1,0] ]
    //      permute(3) => [ [0,1,2], [0,2,1], ... [2,1,0] ]
    private static final int[][] permute(int values) {
        List<int[]> accumulator = new ArrayList<>();
        int[] available = new int[values];
        for (int i = 0; i < values; i++) {
            available[i] = i;
        }
        permuteRecursion(new int[0], available, accumulator);
        return accumulator.toArray(new int[accumulator.size()][]);
    }

    private static final class MyIterator implements Iterator<Segment[]> {

        private static final int SIDES = 4;
        // statically calculated permutations - 1-off saves time.
        private static final int[][] PERMUTES = permute(SIDES);

        private final int limit;
        private final int width;
        private int[] cursors = new int[SIDES];
        private int permcursor = 0;
        private final Point[] current = new Point[SIDES];
        private boolean hasnext = true;

        public MyIterator(int width, int height) {
            this.limit = width * height;
            this.width = width;

            Arrays.fill(current, new Point(0, 0));
            // complicated initialization **before** the first point....

            cursors[cursors.length - 1] = -1;
            permcursor = PERMUTES.length - 1;

            // advance on to the first point.
            advance();
        }

        private void advance() {
            permcursor++;
            if (permcursor >= PERMUTES.length) {
                // run out of permutes for this set of points.
                // generate the next set.
                hasnext = false;
                permcursor = 0;
                for (int i = cursors.length - 1; i >= 0; i--) {
                    if (++cursors[i] == limit) {
                        // by pushing 'reset' in to following cursors we ensure
                        // non-duplicate combinations.
                        // would push different reset for each cursor if we wanted
                        // unique combinations before we permuted.
                        int reset = i > 0 ? (cursors[i - 1] + 1) : limit;
                        for (int j = i; j < cursors.length; j++) {
                            cursors[j] = reset;
                            current[j] = new Point(reset % width, reset / width);
                        }
                    } else {
                        current[i] = new Point(cursors[i] % width, cursors[i] / width);
                        hasnext = true;
                        break;
                    }
                }
                //System.out.println(Arrays.toString(current));
            }
        }

        @Override
        public boolean hasNext() {
            return hasnext;
        }

        @Override
        public Segment[] next() {
            if (!hasnext) {
                throw new NoSuchElementException();
            }
            Segment[] segments = new Segment[SIDES];
            final int[] thisperm = PERMUTES[permcursor];

            for (int i = 0; i < SIDES; i++) {
                segments[i] = new Segment(current[thisperm[i]],
                        current[thisperm[(i + 1) % SIDES]]);
            }
            advance();
            return segments;
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException("Cannot remove()");

        }
    }

    private final int width, height;

    public Quadrilaterals(int width, int height) {
        super();
        this.width = width;
        this.height = height;
    }

    public int getWidth() {
        return width;
    }

    public int getHeight() {
        return height;
    }

    @Override
    public Iterator<Segment[]> iterator() {
        return new MyIterator(width, height);
    }

    public static void main(String[] args) {
        int m = 12345;
        int n = 6789;


        double expect = Math.pow(m * n, 4) * 24; // possible points, number of points in results, number of permutations.
        System.out.printf("Expect %.0f results \n", expect);
        long cnt = 0;
        long start = System.currentTimeMillis();
        Quadrilaterals quads = new Quadrilaterals(m, n);
        for (Segment[] sides : quads) {
            cnt++;
            if (cnt % 10000000 == 0) {
                long now = System.nanoTime();
                double milli = (now - start) / 1000000.0;
                start = now;
                System.out.printf("Iteration %d (%5.3f%%) at rate %.3f/ms, has value %s\n", cnt, 100.0 * (cnt / expect), 10000000 / milli, Arrays.toString(sides));
            }
        }
        System.out.println("There are " + cnt + " quads");

    }
}

Note that this, on my machine, produces at peak (after JIT warmup, etc.), about 30,000 results per millisecond, or 30million per second.... (and suggests days, even months worth of processing):

Expect 1184128553155440700000000000000000 results 
Iteration 10000000 (0.000%) at rate 0.114/ms, has value [S(P(0,0),P(0,0)), S(P(0,0),P(9281,33)), S(P(9281,33),P(0,0)), S(P(0,0),P(0,0))]
Iteration 20000000 (0.000%) at rate 23688.051/ms, has value [S(P(0,0),P(0,0)), S(P(0,0),P(6218,67)), S(P(6218,67),P(0,0)), S(P(0,0),P(0,0))]
Iteration 30000000 (0.000%) at rate 22102.485/ms, has value [S(P(3154,101),P(0,0)), S(P(0,0),P(0,0)), S(P(0,0),P(0,0)), S(P(0,0),P(3154,101))]
Iteration 40000000 (0.000%) at rate 22001.188/ms, has value [S(P(0,0),P(0,0)), S(P(0,0),P(91,135)), S(P(91,135),P(0,0)), S(P(0,0),P(0,0))]
Iteration 50000000 (0.000%) at rate 22410.292/ms, has value [S(P(0,0),P(0,0)), S(P(0,0),P(9373,168)), S(P(9373,168),P(0,0)), S(P(0,0),P(0,0))]
Iteration 60000000 (0.000%) at rate 22243.928/ms, has value [S(P(6309,202),P(0,0)), S(P(0,0),P(0,0)), S(P(0,0),P(0,0)), S(P(0,0),P(6309,202))]
.....
Iteration 610000000 (0.000%) at rate 29932.909/ms, has value [S(P(0,0),P(0,0)), S(P(0,0),P(10656,2058)), S(P(10656,2058),P(0,0)), S(P(0,0),P(0,0))]
Iteration 620000000 (0.000%) at rate 29639.103/ms, has value [S(P(0,0),P(0,0)), S(P(0,0),P(7593,2092)), S(P(7593,2092),P(0,0)), S(P(0,0),P(0,0))]
Iteration 630000000 (0.000%) at rate 30097.184/ms, has value [S(P(4529,2126),P(0,0)), S(P(0,0),P(0,0)), S(P(0,0),P(0,0)), S(P(0,0),P(4529,2126))]
Iteration 640000000 (0.000%) at rate 29380.848/ms, has value [S(P(0,0),P(0,0)), S(P(0,0),P(1466,2160)), S(P(1466,2160),P(0,0)), S(P(0,0),P(0,0))]
Iteration 650000000 (0.000%) at rate 29757.965/ms, has value [S(P(0,0),P(0,0)), S(P(0,0),P(10748,2193)), S(P(10748,2193),P(0,0)), S(P(0,0),P(0,0))]

Answer 3

Three methods of optimization come to mind.

1. Initialize objects as soon as you have the arguments. Reuse them through the inner loop. Create the first point as soon as you have x1 and y1.
2. Make this multi-threaded. This seems like an obvious candidate for a Hadoop map-reduce approach, depending on the inner loop calculations you are doing.
3. Depending on the context, use mathematics instead. Recall the story about Gauss summing 1+2+3+4+...+100 in a matter of seconds. There may be a far better solution to your problem.
4. Use a language that is more expressive, and which allows the compiler to optimize your problem. Scala has a Stream concept that would be very useful here, only generating the possibilities when they are used (and dynamically managing memory in the process). Haskell could also help you solve this problem better. If you must write imperative code, try Fortran for efficient management of arrays and memory.