Skip to content

Instantly share code, notes, and snippets.

@rockdaboot
Created December 3, 2023 17:35
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save rockdaboot/751fef0be82e0b149be75961fa562db6 to your computer and use it in GitHub Desktop.
Save rockdaboot/751fef0be82e0b149be75961fa562db6 to your computer and use it in GitHub Desktop.
Carthesian Product of N lists without allocations using lambda (forEach)
import java.util.List;
import java.util.function.Consumer;
public class Main {
public static void main(String[] args) {
final List<Integer> l1 = List.of(1, 2, 3, 4, 5);
final List<Double> l2 = List.of(1.1, 2.2, 3.3, 4.4, 5.5);
final List<String> l3 = List.of("a", "b", "c", "d", "e");
CarthesianProduct prod = new CarthesianProduct(l1, l2, l3);
prod.forEach(System.out::println);
}
public static class CarthesianProduct {
final private List<?>[] lists;
final private int[] index;
final private Object[] result;
CarthesianProduct(List<?>... lists) {
this.lists = lists;
this.index = new int[lists.length];
this.result = new Object[lists.length];
}
private void init(int length) {
for (int i = 0; i < length; i++) {
index[i] = 0;
result[i] = lists[i].get(0);
}
}
public void forEach(Consumer<List<?>> action) {
// Initialize index and result
init(lists.length);
int pos = 0;
while (pos < lists.length) {
if (index[pos] < lists[pos].size()) {
result[pos] = lists[pos].get(index[pos]);
action.accept(List.of(result));
index[pos]++;
continue;
}
while (pos < lists.length && index[pos]+1 >= lists[pos].size()) {
pos++;
}
if (pos < lists.length) {
index[pos]++;
result[pos] = lists[pos].get(index[pos]);
init(pos);
pos = 0;
}
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment