Custom chunking of Lists Java 8

Question

I have 2 lists.

List<Integer> data = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
List<Integer> partitionHelper = Arrays.asList(1, 3, 4, 5);

I want to distribute the data list into chunks using the partitionHelper. For above example the output should be

List<List<Int>> partition = chunk(data, partitionHelper)
//partition = {{1}, {2,3,4}, {5,6,7,8}, {9,10}}

It can be safely assumed that partitionHelper.sum() >= data.size(). I need an O(n + m) algorithm preferably (where n = partitionHelper.size() and m = data.size())

Any pointers as to how List<List<T>> chunk(List<T>, List<Integer>) function implementation should look?

PS: I am looking for a functional style approach. Not the standard iterative one.

EDIT:

In Scala I would do something like this

def chunkList(data: List[Int], p: List[Int]): List[List[Int]] = {
  def chunk(data: List[Int], p: List[Int], acc: List[List[Int]]): List[List[Int]] =
    if (p.nonEmpty && data.nonEmpty) {
      chunk(data.drop(p.head), p.tail, acc :+ data.take(p.head))
    } else {
      acc
    }
  chunk(data, p, List())
}

> chunkList((1 to 10).toList, List(1,3,4,5))
> res2: List[List[Int]] = List(List(1), List(2, 3, 4), List(5, 6, 7, 8), List(9, 10))

Another Haskell implementation for both foldl and foldr can be found here

What do you mean _I need_? What happened when you tried to solve this yourself? Where did you get blocked? — Sotirios Delimanolis, Jul 07 '17 at 21:41
I am trying to solve it using the map/flatMap constructs of java 8. Cannot wrap my head around how i should proceed. — Apoorv, Jul 07 '17 at 21:43
Possible duplicate of [Partition a Java 8 Stream](https://stackoverflow.com/q/32434592/5221149) — Andreas, Jul 07 '17 at 21:49
@Andreas not really. that question talks about almost equal partitioning of streams. This is about partitioning a list into unequal chunks. — Apoorv, Jul 07 '17 at 21:52
@ApoorvIngle Your question is a variant of the same problem, you just provide difference lengths to each partition. The important part is: *"It's impossible to partition the arbitrary source stream [...], because this will screw up the parallel processing."* --- Your question is an [**XY problem**](https://meta.stackexchange.com/q/66377/351454). If you want to partition a `List`, don't use Streams. Use a loop and `subList()` calls. It will also perform a lot better than any streaming implementation would. — Andreas, Jul 07 '17 at 21:55
Here is a running example of using `subList()`: [IDEONE](http://ideone.com/TYbQU2) — Andreas, Jul 07 '17 at 22:09
@ApoorvIngle I don't know Scala, but to me that looks like a **recursive** function implementation. If that's what you want, why are you asking for a Java Stream implementation? You can do the exact same recursive function in Java. All you have to do is write it. — Andreas, Jul 07 '17 at 22:17
@Andreas i never asked for a stream implementation. I want a functional style implementation :) — Apoorv, Jul 07 '17 at 22:19
@ApoorvIngle What is stopping you from writing a recursive function implementation, aka a functional implementation, in Java? *Hint:* You need to use `subList()` for *O(n)* performance. — Andreas, Jul 07 '17 at 22:24
@ApoorvIngle there is none, not in base Java. Streams are really the only built-in Java approach to "functional style" on collections, and there's no real way to do this with streams. If third-party libraries are game, you might as well just use Guava's `Lists.partition`. — Louis Wasserman, Jul 07 '17 at 22:24
`List> result = new ArrayList<>(partitionHelper.size()); int i = 0; for (int size : partitionHelper) result.add(data.subList(i, Math.min(i += size, data.size())));` — shmosel, Jul 07 '17 at 22:25
@shmosel Thanks for inlining [my IDEONE code](https://stackoverflow.com/questions/44980009/custom-chunking-of-lists-java-8#comment76936025_44980009), minus the overflow handling. — Andreas, Jul 07 '17 at 22:28
@LouisWasserman `Lists.partition` is for (almost) equal chunks. I want the chunk size as a parameter to the function not necessarily equal sizes — Apoorv, Jul 07 '17 at 22:30
@Andreas You're welcome :). The final `if` is unnecessary though. — shmosel, Jul 07 '17 at 22:36
@shmosel Not if there are more values than defined partitions. In case of overflow, all remaining values are added to extra overflow-partition. That's what the final `if` does. — Andreas, Jul 08 '17 at 00:41
@Andreas *It can be safely assumed that `partitionHelper.sum()` >= `data.size()`.* — shmosel, Jul 08 '17 at 00:42
@shmosel The `if` is good defensive programming. It does nothing at all if that assumption truly is guaranteed. Of course, defensive programming would also cover receiving zero or negative partition sizes, so I'm not on fully solid ground with my argument, but being the contrarian I am, I stand firm. ;-) --- *Update*: Actually, `subList()` indirectly guards against negative sizes, so maybe I'm on solid ground. — Andreas, Jul 08 '17 at 00:45
@Andreas If we're disregarding the stated premise, how can you determine that dumping the remainder into a custom partition is more correct than leaving it out or throwing an exception? Either way, defensive programming is an issue you should take up with OP; It doesn't invalidate my solution. — shmosel, Jul 08 '17 at 00:51
There's a reasonable way to do this using arrays and parallel prefix. Using streams is difficult since they lack a prefix/scan/cumulate operation, but it can be done if you stand on your head, e.g. using a stateful mapping function. — Stuart Marks, Jul 08 '17 at 03:39
`public static List> chunkList(List data, List p) { return chunk(data, p, 0); } public static List> chunk(List data, List p, int k) { List> result = new ArrayList<>(); if (p.get(k) >= data.size()) { result.add(data); } else { result.add(data.subList(0, p.get(k))); result.addAll(chunk(data.subList(p.get(k), data.size()), p, k + 1)); } return result; }` — Ashwani, Jul 08 '17 at 05:56
@AshwaniDausodia I understand there are iterative solutions possible. I am looking for a foldLeft version of it in Java if possible. — Apoorv, Jul 09 '17 at 10:09
@ApoorvIngle Java has its own idioms and style of coding. If you try to use haskell/scala idioms in java, it will be asthetically bad and non performative. Also above code is not iterative. It is similar to your scala vesion except it uses index `k` to track current group rather than `head` and `tail` on `p` — Ashwani, Jul 09 '17 at 15:22

score 0 · Answer 1 · answered Jul 12 '17 at 19:23

After translating your Scala code to Java, I ended up with the following code, which is useful only for a small partitionHelper list:

List<List<Integer>> chunk(List<Integer> data, List<Integer> p, List<List<Integer>> acc) {
    if (!p.isEmpty() && !data.isEmpty()) {
        int i = Math.min(p.get(0), data.size());
        acc.add(data.subList(0, i));
        return chunk(data.subList(i, data.size()), p.subList(1, p.size()), acc);
    }
    return acc;
}

List<List<Integer>> chunk(List<Integer> data, List<Integer> p) {
    return chunk(new ArrayList<>(data), p, new ArrayList<>());
}

Indeed, the partitionHelper list must be small, because the stack is being used for recursive calls of the chunk method, and there will be as many recursive calls as elements in the partitionHelper list.

Thanks for your answer, but i am looking for a foldLeft/foldRight kind of an implementation. Please see the Haskell link I have added to the question — Apoorv, Jul 18 '17 at 17:22

Custom chunking of Lists Java 8

1 Answers1