CODEWITHSUNDEEP
javaalgorithmperformancejava-stream
szymonszymon
szymonszymon

Reputation: 35

Create all possible combinations of elements

I need to create all possible combinations of some kind of Key, that is composed from X (in my case, 8), equally important elements. So i came up with code like this:

final LinkedList<Key> keys = new LinkedList();

firstElementCreator.getApplicableElements() // All creators return a Set of elements
          .forEach( first -> secondElementCreator.getApplicableElements()
           .forEach( second -> thirdElementCreator.getApplicableElements()
            // ... more creators
           .forEach( X -> keys.add( new Key( first, second, third, ..., X ) ) ) ) ) ) ) ) );

return keys;

and it's working, but there is X nested forEach and i have feeling that i'm missing out an easier/better/more elegant solution. Any suggestions? Thanks in advance!

Upvotes: 0

Views: 635

Answers (3)

Holger
Holger

Reputation: 298233

The canonical solution is to use flatMap. However, the tricky part is to create the Key object from the multiple input levels.

The straight-forward approach is to do the evaluation in the innermost function, where every value is in scope

final List<Key> keys = firstElementCreator.getApplicableElements().stream()
  .flatMap(first -> secondElementCreator.getApplicableElements().stream()
    .flatMap(second -> thirdElementCreator.getApplicableElements().stream()
      // ... more creators
      .map( X -> new Key( first, second, third, ..., X ) ) ) )
  .collect(Collectors.toList());

but this soon becomes impractical with deep nesting

A solution without deep nesting requires elements to hold intermediate compound values. E.g. if we define Key as

class Key {
    String[] data;
    Key(String... arg) {
        data=arg;
    }
    public Key add(String next) {
        int pos = data.length;
        String[] newData=Arrays.copyOf(data, pos+1);
        newData[pos]=next;
        return new Key(newData);
    }

    @Override
    public String toString() {
        return "Key("+Arrays.toString(data)+')';
    }
}

(assuming String as element type), we can use

final List<Key> keys =
    firstElementCreator.getApplicableElements().stream().map(Key::new)
      .flatMap(e -> secondElementCreator.getApplicableElements().stream().map(e::add))
      .flatMap(e -> thirdElementCreator.getApplicableElements().stream().map(e::add))
      // ... more creators
      .collect(Collectors.toList());

Note that these flatMap steps are now on the same level, i.e. not nested anymore. Also, all these steps are identical, only differing in the actual creator, which leads to the general solution supporting an arbitrary number of Creator instances.

List<Key> keys = Stream.of(firstElementCreator, secondElementCreator, thirdElementCreator
                           /* , and, some, more, if you like */)
    .map(creator -> (Function<Key,Stream<Key>>)
                    key -> creator.getApplicableElements().stream().map(key::add))
    .reduce(Stream::of, (f1,f2) -> key -> f1.apply(key).flatMap(f2))
    .apply(new Key())
    .collect(Collectors.toList());

Here, every creator is mapping to the identical stream-producing function of the previous solution, then all are reduced to a single function combining each function with a flatMap step to the next one, and finally the resulting function is executed to get a stream, which is then collected to a List.

Upvotes: 1

Matt Timmermans
Matt Timmermans

Reputation: 59194

Since the number of input sets is fixed (it has to match the number of arguments in the Key constructor), your solution is actually not bad.

It's more efficient and easier to read without the lambdas, though, like:

for (Element first : firstElementCreator.getApplicableElements()) {
    for (Element second : secondElementCreator.getApplicableElements()) {
        for (Element third : thirdElementCreator.getApplicableElements()) {
            keys.add(new Key(first, second, third));
        }
    }
}

Upvotes: 1

123-xyz
123-xyz

Reputation: 637

Is it Cartesian Product? Many libraries provide the API, for example: Sets and Lists in Guava:

List<ApplicableElements> elementsList = Lists.newArrayList(firstElementCreator, secondElementCreator...).stream()
        .map(c -> c.getApplicableElements()).collect(toList());

List<Key> keys = Lists.cartesianProduct(elementsList).stream()
        .map(l -> new Key(l.get(0), l.get(1), l.get(2), l.get(3), l.get(4), l.get(5), l.get(6), l.get(7))).collect(toList());

Upvotes: 1

Related Questions