Efficiently generate triplet combinations

Given a set of triplets S, where for every triplet s \in S it holds that s[1] >= s[2] >= s[3], where s[i] is the ith element of triplet s. For any s,t,v \in S, let function F(s,t,v) generate a new triplet: F(s,t,v)=(max{s[1],t[1],v[1]} ,max{s[2],t[2],v[2]}, max{s[3],t[3],v[3]}). Goal: generate set T={F(s,t,v) | s,t,v \in S} efficiently.

Two examples:

S = [(9,4,3),(8,6,2),(6,6,4)]
T = [(9,4,3),(8,6,2),(6,6,4),(9,6,3),(9,6,4),(8,6,4)]
S = [(9,4,3),(8,6,2),(6,5,4)]
T = [(9,4,3), (9,6,3), b(9,5,4), b(9,6,4), b(8,6,2), b(8,6,4), b(6,5,4)]

Below is a simple, but relatively inefficient implementation that accomplishes the above. This code runs in O(n^3) with |S|=n. The question is: how to implement this more efficiently? This would involve coming up with an efficient data structure that holds a sorted version of S. For instance, we can observe that F(s,t,v)=s if t[1],v[1] <= s[1], t[2],v[2] <= s[2], t[3],v[3] <= s[3]. So if we pick triple s=(x,y,z), then we only need to iterate over triples (x',y',z') having x' <= x and y' >= y and z' >= z.
Note: in my application |S| is large, e.g. 100000 triples.

public class TripleGen {
public static void main(String[] args) {
int[][] ds = new int[][]{{9, 4, 3}, {8, 6, 2}, {6, 5, 4}};
List<Triple> l = Triple.toList(ds);
System.out.println(gen(l));
}
public static Set<Tripple> gen(List<Triple> S) {
Set<Triple> T = new HashSet<>();
for (int i = 0; i < S.size(); i++) {
for (int j = i; j < S.size(); j++) {
for (int k = j; k < S.size(); k++) {
int l = Math.max(S.get(i).x, Math.max(S.get(j).x, S.get(k).x));
int w = Math.max(S.get(i).y, Math.max(S.get(j).y, S.get(k).y));
int h = Math.max(S.get(i).z, Math.max(S.get(j).z, S.get(k).z));
T.add(new Triple(l, w, h));
}
}
}
return T;
}
}
public final class Triple {
public final int x;
public final int y;
public final int z;
public Triple(int x, int y, int z) {
this.x = x;
this.y = y;
this.z = z;
}
public static List<Triple> toList(int[][] ds) {
List<Triple> l = new ArrayList<>(ds.length);
for (int[] d : ds)
l.add(new Triple(d[0], d[1], d[2]));
return l;
}
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Triple t = (Triple) o;
return x == t.x &&
y == t.y &&
z == t.z;
}
public int hashCode() {
return Objects.hash(x, y, z);
}
public String toString() {
return "(" + x + "," + y + "," + z+")";
}
}

I doubt that there’s much to be gained. I present my attempt.

• Consider function F2(s, t) that makes a similar combination of just two triplets. Now F(s, t, v) can be written as F2(s, F2(t, v)), and there may be a performance gain in calculating it in this way reusing the result of F2(t, v) for different s's.
• A slight improvement may be made by estimating the capacity of the result HashSet so no extensions and rehashing will be needed underway.

In code:

public static Set<Triple> gen(List<Triple> s) {
// Deduplicate s
s = new ArrayList<>(new HashSet<>(s));
int n = s.size();
// Combine pairs of triplets first
int maxSizeOfT2 = (n * n - 1) / 2;
int capacityForT2 = (maxSizeOfT2 * 4 + 2) / 3;
Set<Triple> t2AsSet = new HashSet<>(capacityForT2);
// For the pairs only pair two *different* triples
for (int i = 0; i < s.size(); i++) {
for (int j = i + 1; j < s.size(); j++) {
Triple newTriplet = f2(s.get(i), s.get(j));
t2AsSet.add(newTriplet);
}
}
List<Triple> t2 = new ArrayList<>(t2AsSet);
// For the combinations of three original triplets
// combine every pair with ever original triplet
int maxSizeOfT = (t2AsSet.size() + 1) * (n + 1) - 1;
int capacityForT = (maxSizeOfT * 4 + 2) / 3;
Set<Triple> t = new HashSet<>(capacityForT);
for (int i = 0; i < t2.size(); i++) {
for (int j = 0; j < s.size(); j++) {
Triple newTriplet = f2(t2.get(i), s.get(j));
t.add(newTriplet);
}
}
// Instead of generating F(s, s, s) just add every s to the result
t.addAll(s);
return t;
}

I didn’t make any benchmarking, just some preliminary time measurements. They are not promising. I am varying the number of triplets in the input, and also the range of the numbers in the triplets. When there only small numbers, many duplicates will be filtered out and the result set will be smaller. With a larger range of numbers, clashes happen seldom, and the size of the result set is bigger.

List  Element     Result   Your time      My time     Improvement
size  range        size   milliseconds  milliseconds      %
-----------------------------------------------------------------
3   1–9              6       0.038       0.015         60
3   1–10 000         7       0.046       0.016         66
400   1–9            159    4736        4740              0
400   1–10 000   858 897    1079        1067              1

In the comments you expected that the best case could be improved, and numbers may indicate that that is true. For the worst case there only seems to be a marginal improvement.

As I said in the comments, the size of the result set is O(n^3), so no algorithm to generate it could be faster than O(n^3). What we might hope for would be a smaller constant factor on the n^3.