How to combine list elements and find the price of largest combination

Question

I have a class that holds details of a particular item like the following:

Detail.class

Long detailsId;
Integer price;
List<Long> stackableDetails;

/*getters and setters*/

Now, I have a sample dataset like the following:

    DetailId    Price    StackableDetails
------------------------------------------
    1011        4$       1012, 1014
    1012        6$       1011,1013
    1013        10$      1012
    1014        8$       1011

This data set maps to List sampleDetails. Now, based on the stackableDetails information, I have to combine the details and pick the combination having the max price from it.

For eg,
In the data set available, the possible combinations would be
1011,1012,1014 - 4+6+8 = 18$
1012,1011,1013 - 6+4+10 = 20$
1013,1012 - 10+6 = 16$
1014,1011 - 8+4 = 12$

Now the combination of details 1012,1011,1013 yields 20$, so I fetch this combination and add this in my result list. How can I achieve this in java8.

Any help appreciated. Thanks!

Can you clarify how you want to make the combinations and how you pick the "best" combination? — Robin Topper, May 02 '17 at 09:29
combinations would be based on values in StackableDetails and the best combination is picked on highest sum of the price values. — , May 02 '17 at 09:34
You've not given enough information to determine if it is a perfect duplicate, but the information [here](http://stackoverflow.com/questions/29910312/algorithm-to-get-all-the-combinations-of-size-n-from-an-array-java) should help you — Robin Topper, May 02 '17 at 09:41
The only solution I have on the top of my head is to make a first pass and store all the detailId, price in a map. In the second pass, iterate through the list of stackabledetails this time, and generate the sum by pulling the price from the map each time. I am not sure if this would work, any suggestions from your end? — , May 02 '17 at 09:46
I can't determine whether your question is exactly the same as the one I linked, but it is at least very similar and should help you find a solution to your problem. — Robin Topper, May 02 '17 at 09:58

Eugene · Accepted Answer · 2017-05-03T04:53:59.277

1

Well, first it's a bit misleading. In your question you say pick the combination having the least price from it, but then later (and your comments) you actually provide the samples that yields the max result.

Assuming you need the max result, you could use this:

 long maxPrice = list
            .stream()
            .map(d -> Stream.concat(Stream.of(d.getDetailsId()), d.getStackableDetails().stream()))
            .map(s -> s.reduce(0L, (left, right) -> left +
                    list.stream()
                            .filter(dt -> dt.getDetailsId().equals(right))
                            .findAny()
                            .get()
                            .getPrice()))
            .max(Comparator.naturalOrder())
            .orElse(0L);

    System.out.println(maxPrice); // 20

EDIT

Well you want to compare by max price, but output set the make this price. The only thing I could come up with is to put them into a TreeMap, but that is not very readable IMHO. Also, there is the case when you have entries that collide - they have the same max price. This example simply takes the last one in encounter order.

  List<Long> highest = list
            .stream()
            .map(d -> Stream.concat(Stream.of(d.getDetailsId()), d.getStackableDetails().stream()).collect(Collectors.toList()))
            .collect(Collectors.toMap(s -> s.stream().reduce(0L,
                    (left, right) -> left + list.stream().filter(dt -> dt.getDetailsId().equals(right)).findAny().get().getPrice()),
                    s -> s.stream().collect(Collectors.toList()),
                    (left, right) -> right,
                    TreeMap::new))
            .lastEntry().getValue();

EDIT2

  Map<List<Long>, Long> map = list
            .stream()
            .map(d -> Stream.concat(Stream.of(d.getDetailsId()), d.getStackableDetails().stream()).collect(Collectors.toList()))
            .collect(Collectors.toMap(
                    s -> s.stream().collect(Collectors.toList()),
                    s -> s.stream().reduce(0L,
                            (left, right) -> left + list.stream().filter(dt -> dt.getDetailsId().equals(right)).findAny().get().getPrice()),
                    (left, right) -> right));

edited May 03 '17 at 04:53

answered May 02 '17 at 11:24

Eugene

117,005
15
201
306

thanks for pointing it out, I have corrected the same. Thanks much for this solution, if I were to get the corresponding detail elements combination (and store in a result list) instead of the sum of the combination. How can I go about doing this? – May 02 '17 at 11:47
1

@liksar you want the result to be `1012,1011,1013` instead of 20? – Eugene May 02 '17 at 11:57
I would like the result to be held in a List bestDetails. So bestDetails would have 3 Detail objects corresponding to the DetailIds - 1012, 1011, 1013 – May 02 '17 at 12:02
1

@liksar let's take your example with `four details`. What exactly do you want to get from this? A single detail where price is `max`, a List of details sorted? etc? Could you be more verbose? – Eugene May 02 '17 at 12:07
Suppose 4 details correspond to 4 Detail objects in a list rawDetails. list rawDetails = Arrays.asList(new Detail(1011L, 4, Arrays.asList(1012L,1014L)), new Detail(1012L, 6, Arrays.asList(1011L,1013L)), new Detail(1013L, 10, Arrays.asList(1012L)), new Detail(1014L, 8, Arrays.asList(1011L))); Now this is my initial raw list, after I apply your logic for find the combination that yields me the maximum, I would like to store the objects with the detailIds 1012, 1011, 1013 in a List resultset. Please let me know if I am unclear somewhere – May 02 '17 at 12:20
I would like to save the entire map into a Map,Integer> map = new HashMap<>(); I tried removing the .lastEntry().getValue() and changing TreeMap into Hashmap. But I am getting compile time errors. Please guide me – May 03 '17 at 03:49
1

@liksar see EDIT2. This is the last edit I make here, please post your questions as new ones. You would not only make it clearer, but also might help others. – Eugene May 03 '17 at 04:55
Like you suggested, since I have more queries on this, so I have created a new question, that can be found here: http://stackoverflow.com/questions/43757538/how-to-convert-type-of-stream – May 03 '17 at 10:32
@liksar Please update your question reflecting what you actually needed. For example I only read your question and the first solution of Eugene and so I posted only an adapted solution for that specific problem. The comments here however contain further information, which lead to a completely different solution. Or, as you did, post new questions, if the question you asked is already complete and answered, but doesn't really satisfy what you really wanted to achieve. – Roland May 04 '17 at 09:00

score 1 · Answer 2 · edited May 23 '17 at 12:26

Looking at Eugenes answer I thought that should work also a bit shorter... Here is another variant using flatMap and mapToDouble and the DoubleStream's sum and max:

double maxPrice = details.stream()
    .mapToDouble(detail -> Stream.concat(Stream.of(detail.getDetailsId()),
                                         detail.getStackableDetails().stream())
      .flatMap(detailId -> details.stream()
        .filter(candidateDetail -> detailId.equals(candidateDetail.getDetailsId())))
      .map(Detail::getPrice)
      .mapToDouble(value -> /* your transformation function */ (double) value)
      .sum()
    )
    .max()
    .orElse(0.0);

I wonder, why you might only sum up the details and its immediate stackable details. It sounds like a recursive problem to me, but on the other side, you probably know, what you need :-)

Regarding your other question: you may just want to replace the transformation step into the following:

.mapToDouble(Double::parseDouble)

Note that you can exchange double/mapToDouble, etc. to whatever suits you the most. sum() however is only available to the three primitive streams: IntStream, LongStream and DoubleStream.

How to combine list elements and find the price of largest combination

2 Answers2

Linked