7
$\begingroup$

I know that Subsets[list] gives the power set of list and Subsets[list,{k}] gives all subsets containing exactly $k$ elements.

They all give all the subsets at once. I want to output them iteratively.

I saw that Wolfram has a package called Lazy. I installed it according to the instructions. However, when I tried to run the code below, it didn't work.

Enter image description here

Needs["Wolfram`Lazy`"]
LazySubsets[{1, 2, 3}]

It will output as it is.

Or when I enter the following code, it even throws an error.

LazySubsets[{1, 2}]

Lazy::undef: function LazyMap is undefined for the argument LazySubsets[2].

Lazy::undef: function LazyJoin is undefined for the argument LazyMap[LazyPrepend[#1, 1]&, LazySubsets[2]].

I am not quite sure how to use this function either.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
13
$\begingroup$

The package doesn't seem to be well-documented, so I have to guess. If I guess it right, those Lazy* functions are supposed to work only on LazyList[…]. Following this conjecture, I find the following 3 solutions:

LazySubsets[LazyRange[2]]
% // Normal

enter image description here

LazySubsets[Lazy@Range[2]]
% // Normal

enter image description here

LazySubsets[ToLazyList@{1, 2}]
% // Normal

enter image description here

Normals in code sample above have generated the subsets all at once. To obtain the subset one by one, Part ([[]]) / LazyPart seems to be the tool. The following code sample finds the first subset of Range[10] whose sum equals 12:

lazylist = LazySubsets@LazyRange@10;
Catch@Do[With[{l = Normal@lazylist[[i]]}, 
              If[12 == Total@l, Throw@l]], 
      {i, ∞}] // AbsoluteTiming
(* {16.5285, {1, 2, 3, 6}} *)

Hmm… a bit slow, but it indeed works.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Nice! I would like to know how to iterate the output. It seems that Normal also provides output all at once. For example, if I find a subset of {1,2,3,4,5,6,7,8,9,10} where the product or sum of all elements is 12, then break the iterate-loop. $\endgroup$
    – licheng
    Jun 1 at 12:30
  • 1
    $\begingroup$ @licheng I fail to figure out a way to achieve this, you may consider asking a new question. (But since the function is mentioned only on the page Guide (internal), personally I suspect its functionality may not be complete. ) $\endgroup$
    – xzczd
    Jun 1 at 13:10
  • 1
    $\begingroup$ @licheng Finally, I find a possible solution to obtain the output one by one. Check my update. $\endgroup$
    – xzczd
    Jun 1 at 14:19
  • $\begingroup$ It is indeed feasible, but the speed is discouraging. Let me check some other similar posts. It seems that Mathematica tends to prefer batch output instead of individual output to save memory. $\endgroup$
    – licheng
    Jun 2 at 2:14
  • $\begingroup$ NextSubset in Combinatorica is excellent, but unfortunately, Mathematica hasn't packaged it as an official built-in function. Maple's Iterator package provides a good solution for this. In Python, the itertools or more-itertools libraries also offer rich generator functionality. $\endgroup$
    – licheng
    Jun 2 at 2:19
11
$\begingroup$

I made my own lazy list paclet a few years ago. It implements a fairly efficient lazy version of Tuples based on some old functionality from the deprecated Combinatorica package. It seems like that package also has code that's useful for generating subsets iteratively. You can use NextSubset to step through the subsets at your own pace:

Needs["Combinatorica`"]
NestList[NextSubset[{a, b, c}, #] &, {}, 8]

Let me know if you need any help with the paclet I wrote; the usage is a bit arcane at times, but it can be quite efficient if used correctly.

Edit

As remarked in the comments, Combinatorica has some conflicts with system symbols. As a precaution you can load and use it like this:

Block[{$ContextPath}, Needs["Combinatorica`" -> "CM`"]]
NestList[CM`NextSubset[{a, b, c}, #] &, {}, 8]

The Block will prevent contamination of your context path. You'll still get messages, but I don't think it'll cause any harm. And if you're really paranoid, you can always use

CM`NextSubset // GeneralUtilities`PrintDefinitions

to figure out how it's defined and reverse-engineer it from there.

Edit 2

I honestly forgot the most obvious way to do this: you can use the 3rd argument of Subsets to pick whichever element you want. E.g., get the 20th subset of length 50 from the subsets of Range[100]:

Subsets[Range[100], {50}, {20}]

You can easily iterate over that.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Good! I also noticed your package. Once Combinatorica is loaded, it can conflict with many built-in functions like the Graph function. I'm not sure how to make them coexist peacefully. $\endgroup$
    – licheng
    Jun 1 at 10:59
  • $\begingroup$ I'm not quite sure where the source code for the Wolfram package Lazy is located, so I don't know how to use it either. $\endgroup$
    – licheng
    Jun 1 at 11:01
  • 1
    $\begingroup$ @licheng See the update to my question $\endgroup$
    – Sjoerd Smit
    Jun 1 at 11:10
  • 1
    $\begingroup$ @licheng See my 2nd edit for an even better solution. $\endgroup$
    – Sjoerd Smit
    Jun 2 at 15:22
  • $\begingroup$ Nice answer! However, since I specifically asked about the Lasy library, considering the topic, I did not select your answer as the best. But, in terms of actual effectiveness, your answer is the best. $\endgroup$
    – licheng
    Jun 4 at 2:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.