posted 1 month ago

I'm trying to create a class that generates a stream of lists that are unique sublists of a given list. Looks like I need a stream() method but how is the functionality of hasNext() and next() to be implemented?

I've tried googling this but can't seem to find the right search terms to get me to a tutorial or example.

I've tried googling this but can't seem to find the right search terms to get me to a tutorial or example.

You have the right to remain sentient. If you give up the right to remain sentient,

you will be elected to public office.

posted 1 month ago

As I wrote yesterday in a topic, I use a method that, given an ordered subset of size K from a set of size N, generates a list of subsets of size K + 1. I do not generate a Stream of lists, but I hope you will get some idea of how it can be done.

The idea is that given a subset of, say, {1, 3, 6} from the main set {0, 2, 3, ..., 9} (size 10), I create the new series of subsets by creating these subsets: {1, 3, 6, 7}, {1, 3, 6, 8} and {1, 3, 6, 9}.

I do this for all th subsets of length 3, creating all the subsets of lenght 4, et cetera. I use a Map<Integer (the length of the subsets), List<List<Integer>> to store all these lists of lists.

Here is my routine that creates the substes of lenght K + 1, given a subset of length K, and given the overall size of the starting set:

Having a second look: if you leave out the '.collect(toList)' you get a Stream<List<Integer>>

The idea is that given a subset of, say, {1, 3, 6} from the main set {0, 2, 3, ..., 9} (size 10), I create the new series of subsets by creating these subsets: {1, 3, 6, 7}, {1, 3, 6, 8} and {1, 3, 6, 9}.

I do this for all th subsets of length 3, creating all the subsets of lenght 4, et cetera. I use a Map<Integer (the length of the subsets), List<List<Integer>> to store all these lists of lists.

Here is my routine that creates the substes of lenght K + 1, given a subset of length K, and given the overall size of the starting set:

Having a second look: if you leave out the '.collect(toList)' you get a Stream<List<Integer>>

posted 1 month ago

Well done

I have been thinking that I wouldn't try doing that sort of thing with a Stream; it screams, “Recurrrrrrrrrrrrrrrrsion,” to me. It appears to me that you are trying to use the List as a set and create its powerset. I would consider recursion taking a List and removing one element from that List.

I have been thinking that I wouldn't try doing that sort of thing with a Stream; it screams, “Recurrrrrrrrrrrrrrrrsion,” to me. It appears to me that you are trying to use the List as a set and create its powerset. I would consider recursion taking a List and removing one element from that List.

posted 1 month ago

Piet, are you sure that bit about

I mean, if you have:

You end up with

Piet Souris wrote:return IntStream.range(list.isEmpty() ? 0 : Collections.max(list) + 1, size)

Piet, are you sure that bit about

`Collections.max(list) + 1, size`is correct?

I mean, if you have:

You end up with

`IntStream.range(5, 2)`, which gives you nothing.

Piet Souris

Rancher

Posts: 2832

96

posted 1 month ago

- 1

The size is the length of the original set. so having the subset {1, 2, 3, 4} the size would have to be at least 6, which would deliver the new subset (1, 2, 3, 4, 5}.

The idea is that, recursively, I start with subsets of length 0, being a List of just the empty List. Then, generating the subsets of length 1, starting from all the subsets of length 0, I have

IntStream(list.isEmpty? 0 : Collections.max + 1, size), so that if the original set is {0, 1, 2, ..., 9}, then size = 10 and I would get Intstream.range(0, 10), et cetera.

As said, I liked this implementation, but there are many other ways.

Having all the subsets of the List {0, 1, 2, ... N}, it is then easy to map the integers 0...N to the elements of an arbitrary List<T>, so that you can easily generate all subsets of that list, and it doesn't matter if that list contains duplicates or not. Efficient? Never tested for that, but short and easy? Yes.

Edit: the method I supplied ir\s only one of the two methods I use, in the other method the size is determined.

The idea is that, recursively, I start with subsets of length 0, being a List of just the empty List. Then, generating the subsets of length 1, starting from all the subsets of length 0, I have

IntStream(list.isEmpty? 0 : Collections.max + 1, size), so that if the original set is {0, 1, 2, ..., 9}, then size = 10 and I would get Intstream.range(0, 10), et cetera.

As said, I liked this implementation, but there are many other ways.

Having all the subsets of the List {0, 1, 2, ... N}, it is then easy to map the integers 0...N to the elements of an arbitrary List<T>, so that you can easily generate all subsets of that list, and it doesn't matter if that list contains duplicates or not. Efficient? Never tested for that, but short and easy? Yes.

Edit: the method I supplied ir\s only one of the two methods I use, in the other method the size is determined.

posted 1 month ago

- 1

Going back to the original question, I think there *is* a valid use case for using Streams here, rather than Lists, or writing a recursive method. Unlike Lists (or any Collection), a Stream need not contain all elements in memory at once. This can be important for large solutions - e.g. for 30 different elements, there are over a trillion possible combinations. You don't want to try to save those all in memory. Also, streams give you access to extensive additional capabilities, including making things faster with concurrency by simply adding .parallel() to the call.

Here's a way to answer the question as originally asked:

The key part of returning a new Stream is accomplished by:

Note that an earlier version of the code did this instead:

However this was undesirable; it had the effect of recursively creating all the nested streams at once when the stream is first created - leading to excessive memory use. Better to use Suppliers and flatMap to defer the creation of each stream until the code is ready to actually use it.

Here's a way to answer the question as originally asked:

The key part of returning a new Stream is accomplished by:

Note that an earlier version of the code did this instead:

However this was undesirable; it had the effect of recursively creating all the nested streams at once when the stream is first created - leading to excessive memory use. Better to use Suppliers and flatMap to defer the creation of each stream until the code is ready to actually use it.