Tag: cross

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