Message Boards Message Boards

9
|
7979 Views
|
2 Replies
|
19 Total Likes
View groups...
Share
Share this post:

How lack of iterators limits the usefulness of combinatorial enumeration

Posted 4 years ago

I would like to share some thoughts about a specific limitation of the Wolfram Language and ask for ideas about how problems of the sort I'll describe below could be handled better.

Mathematica has many functions for discrete mathematics. A common feature of combinatorial objects is that their numbers tends to explode as they get larger. Think e.g Tuples[Range[n], k]—there are $n^k$ of them.

Because of this problem, functions that can return all solutions to some combinatorial problem usually take an argument that limits the number of results. Take e.g. FindCycle or FindClique. They can find at most $n$ cycles/cliques.

But this approach comes with a big limitation: what if I already generated 1000 cliques, but then I realize that I need the 1001st one as well? There is no way to continue the clique generation process. The only option I have is to start from scratch.

Languages like Python use the concept of iterators for this. First, we set up an iterator object, e.g. an iterator of cliques of a given graph. Then we request the first result. We can process it as we like. If we need another result, we can request it too, and so on. It is up to the iterator's user to decide how many results to request, and when to discard the iterator data structure.

Not only can Mathematica not do this, I don't even see how something like this could be efficiently incorporated into the language. Iterators are, by nature, mutable objects. Mutability does not fit into the Wolfram Language well.

In fact, the incremental generation of such objects is so useful, that it is included in some parts of Mathematica too:

  • The 3rd argument of Subsets allows us to request the kth subset. This approach works for subsets because it is easy to directly generate the kth one, without first creating the first k-1st ones. For harder combinatorial problems, this is not going to be possible.

  • Prime appears to work the same way as Subsets: Prime[k] appears to directly give the kth prime. But notice that Prime[k+1] evaluates much faster if Prime[k] has already been computed. Mathematica does in fact maintain some internal state while computing primes, and makes use of it for later computations, just like an "iterator object" would. However, unlike in the case of an iterator object in Python, we have no access to this state. We can't save it, and re-load it in a later session.

Please consider this as a feature request or a suggestion. I am asking to change the paradigm for generating combinatorial objects (of which there may be lots, more than what fits in memory) in the Wolfram Language. While the Wolfram Language does not seem to make it possible for users to implement an efficient iterator, I am sure that it could be done as a built-in, atomic expression.

For a concrete example of how iterators can be used for combinatorial work, see DegreeSequences in SageMath.

I hope I managed to make a good case for why iterators are important for a system that can do discrete mathematics. Any thoughts from other users?

POSTED BY: Szabolcs Horvát
2 Replies

I agree with this—obviously. Also the concept of yield in Pythons is quite nice actually.

To alleviate some of the problems with Tuples and Subsets I created SelectTuples and SelectSubsets: https://resources.wolframcloud.com/FunctionRepository/resources/SelectTuples and https://resources.wolframcloud.com/FunctionRepository/resources/SelectSubsets which might help you in some cases.

Both do not create all of the tuples/subsets at once but rather one-by-one, so the memory footprint is tiny.

EDIT: SelectPermutations is still in development, will come soon…

POSTED BY: Sander Huisman

I completely agree with this. Personally, I think that something along the lines of Haskell-style lazy lists fits best with WL's paradigms. In the past I did an exercise to try an implement this from scratch, though I'm aware that similar functionalities are already hidden in the language. The advantage of lazy lists is that you can capture the stateful part of the iteration in the held tail of the list explicitly. So you can have a function that extracts a few elements from the lazy list and then also returns the tail to allow further extraction of elements.

POSTED BY: Sjoerd Smit
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract