Suppose I have several sorted lists of positive numbers, like so for example:
double[] a1 = new double[]{0.70, 0.20, 0.10}; double[] a2 = new double[]{0.80, 0.10, 0.05, 0.05}; double[] a3 = new double[]{0.60, 0.15, 0.14, 0.10, 0.01};
I want to iterate Cartesian product of these arrays in the order of decreasing product of entries, like so:
0000: Combo[product=3.36e-01, vals=[0.70, 0.80, 0.60], indexes=[0, 0, 0]] 0001: Combo[product=9.60e-02, vals=[0.20, 0.80, 0.60], indexes=[1, 0, 0]] 0002: Combo[product=8.40e-02, vals=[0.70, 0.80, 0.15], indexes=[0, 0, 1]] 0003: Combo[product=7.84e-02, vals=[0.70, 0.80, 0.14], indexes=[0, 0, 2]] 0004: Combo[product=5.60e-02, vals=[0.70, 0.80, 0.10], indexes=[0, 0, 3]] 0005: Combo[product=4.80e-02, vals=[0.10, 0.80, 0.60], indexes=[2, 0, 0]] ...
E.g. in the example above the first entry is obvious (as arrays are sorted) and it is a combination of the first values: [0.70, 0.80, 0.60] with product 0.70*0.80*0.60 = 3.36e-01 and corresponding value indexes in arrays a1, a2, a3 are [0, 0, 0]. Now the second entry is less obvious, should we change 0.70 to 0.20? Or 0.60 to 0.15? Or 0.80 to 0.10? The second should be [0.20, 0.80, 0.60]with product 9.60e-02, indexes [1, 0, 0].
Here is a program in java to generate/print them: https://repl.it/repls/FilthyGreatRotation (all the logic is in printWholeCartesianProduct() method)
This program generates them in lexicographic order and then sorts the whole set by product.
Question: Is there an easy way to actually generate the combos in correct order in the first place?
The reason for this: I don’t have the lists in the first place, only iterators over some sorted collections of numbers. Possibly veeery long, length not known ahead of time, but it is known that the numbers in each iterator are sorted.
MVCE to play with (same as in https://repl.it link above):
import java.text.DecimalFormat; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.StringJoiner; import java.util.function.Consumer; import java.util.stream.Collectors; public class Main { public static void main(String[] args) { List<List<Double>> data = createData(); printWholeCartesianProduct(data); } public static List<List<Double>> createData() { double[] a1 = new double[]{0.70, 0.20, 0.10}; double[] a2 = new double[]{0.80, 0.10, 0.05, 0.05}; double[] a3 = new double[]{0.60, 0.15, 0.14, 0.10, 0.01}; return createData(a1, a2, a3); } public static void printWholeCartesianProduct(List<List<Double>> data) { final DecimalFormat df = new DecimalFormat("0.00"); // print input data String matrix = data.stream() .map(l -> l.stream().map(df::format).collect(Collectors.joining(", "))) .map(row -> "[" + row + "]") .collect(Collectors.joining("\n")); System.out.println("Input data:\n" + matrix); // collect combos as they are generated final List<Combo> combos = new ArrayList<>(); Consumer<int[]> callback = indexes -> { double[] v = new double[indexes.length]; double prod = 1; for (int i = 0; i < indexes.length; i++) { List<Double> col = data.get(i); int index = indexes[i]; v[i] = col.get(index); prod *= v[i]; } combos.add(new Combo(prod, v, indexes.clone())); }; // generate combos int[] c = new int[data.size()]; int ptr = c.length - 1; while (ptr >= 0) { callback.accept(c); c[ptr]++; // increment if (c[ptr] == data.get(ptr).size()) { // carry do { ptr--; } while(ptr >= 0 && c[ptr] == data.get(ptr).size() - 1); if (ptr < 0) { break; } c[ptr]++; // zero out while (++ptr <= c.length - 1) { c[ptr] = 0; } ptr = c.length - 1; } } // cheating - sort after generation and print result combos.sort((o1, o2) -> Double.compare(o2.product, o1.product)); StringBuilder sb = new StringBuilder(); double totalP = 0; for (int i = 0; i < combos.size(); i++) { sb.append(String.format("%04d: ", i)).append(combos.get(i)).append("\n"); totalP += combos.get(i).product; } System.out.printf("Cartesian product in descending product (total p=%.3e):\n%s", totalP, sb.toString()); } public static List<Double> asList(double[] a) { return Arrays.stream(a).boxed().collect(Collectors.toList()); } public static List<List<Double>> createData(double[]... arrays) { final List<List<Double>> vals = new ArrayList<>(); Arrays.stream(arrays).forEachOrdered(a -> vals.add(asList(a))); return vals; } static class Combo { final double product; final double[] vals; final int[] indexes; Combo(double product, double[] vals, int[] indexes) { this.product = product; this.vals = vals; this.indexes = indexes; } @Override public String toString() { return new StringJoiner(", ", Combo.class.getSimpleName() + "[", "]") .add("product=" + String.format("%.2e", product)) .add("vals=[" + Arrays.stream(vals).boxed().map(v -> String.format("%.2f", v)).collect( Collectors.joining(", ")) + "]") .add("indexes=" + Arrays.toString(indexes)) .toString(); } } } ```
