4
$\begingroup$

(The Goal is to create a program that given an input set, yields an output showing the Power Set of the entered set without using the built-in mathematica function" "When I enter this code into Mathmetica and run it, it ONLY GOES THROUGH THE LOOP ONCE AND ENDS THERE. Not sure what I'm doing wrong.)

MyIterativeSubsets[inlist_] :=
   Module[
    {
    listLength,
    powerSetLength,
    myPowerSet,
    pointer,
    counter,
    currentElement,
    newSet,
    DebugFlag = True
      },
 If[! ListQ[inlist], Return["Please enter a list"], 
  listLength = Length[inlist];
  myPowerSet = {{}};
  pointer = 1;
  If[DebugFlag == True, 
  Print["What was entered"];
  Print[inlist];

  Print["List Length"];
  Print[listLength];

  Print["Power Set is"];
  Print[myPowerSet];
];
While[pointer <= listLength,
    currentElement = inlist[[pointer]];
    powerSetLength = Length[myPowerSet];
    counter = 1;
    newSet = {};
 If[DebugFlag == True,
   Print["Current Element is"];
   Print[currentElement];

   Print["powerSetLength is"];
   Print[powerSetLength];

   Print["Counter is"];
   Print[counter];
  ];
    While[counter <= powerSetLength,
        newSet = 
   Append[newSet, Append[myPowerSet[[counter]], currentElement]];
        myPowerSet = Union[myPowerSet, newSet];
        counter++;
  If[DebugFlag == True,
   Print["New Set is"];
   Print[newSet];

   Print["My Power Set is"];
   Print[myPowerSet];

   Print["Counter is"];
   Print[counter];
   ];
  ];
  Print["This is the current Power Set"];
  Return[myPowerSet]
  pointer++;
  ]
 ]
]
$\endgroup$
9
  • $\begingroup$ You're calling Return in the body of the While. Also you know Subsets is a thing, right? Like it's a function you can use. Generally a procedural implementation of a function will be less efficient. $\endgroup$
    – b3m2a1
    Commented Sep 16, 2017 at 2:05
  • $\begingroup$ Should it be right after the while $\endgroup$ Commented Sep 16, 2017 at 2:06
  • $\begingroup$ You don't need to call Return at all. Just put myPowerSet at the end of the Module. $\endgroup$
    – b3m2a1
    Commented Sep 16, 2017 at 2:06
  • $\begingroup$ See this to get you started on the right path. Mathematica programming is very different from Java or C++ or python (although python to a lesser extent). It'll take some readjustment. $\endgroup$
    – b3m2a1
    Commented Sep 16, 2017 at 2:07
  • 1
    $\begingroup$ Just to back that statement up, the efficient subsets function from my answer is still 16 times slower than the built-in version. $\endgroup$
    – b3m2a1
    Commented Sep 16, 2017 at 6:26

3 Answers 3

5
$\begingroup$

Using m_goldberg's insight and Carl Woll's note on three-argument Pick, here's a one-liner version of this:

subsets[set_List] :=
 Pick[set, #, 1] & /@ IntegerDigits[Range[2^Length[set]] - 1, 2, Length[set]]

We use Pick and use 1 as True, 0 as False in the standard way.

This is then ~13 times slower than Subsets:

subsets[Range[16]] // RepeatedTiming // First

0.17

Subsets[Range[16]] // RepeatedTiming // First

0.013

LegionMammal978 points out that we can just use Tuples[{0,1}, Length[set]]:

subsets[set_List] :=
 Pick[set, #, 1] & /@ Tuples[{0,1}, Length[set]]

With that tweak it's only 10 times slower than Subsets

subsets[Range[16]] // RepeatedTiming // First

0.14

Subsets[Range[16]] // RepeatedTiming // First

0.013
$\endgroup$
4
  • $\begingroup$ I like the 3-arg version of Pick here, i.e., Pick[set, #, 1]& /@ ... $\endgroup$
    – Carl Woll
    Commented Sep 16, 2017 at 5:36
  • $\begingroup$ @CarlWoll Nice! I'll stick that in. $\endgroup$
    – b3m2a1
    Commented Sep 16, 2017 at 5:37
  • $\begingroup$ Wouldn't Tuples[{0, 1}, Length[set]] be clearer and possibly faster than your IntegerDigits solution? $\endgroup$ Commented Sep 16, 2017 at 15:58
  • $\begingroup$ @LegionMammal978 it would indeed. It does feel a bit like it's getting dangerously close to just using Subsets, though. I'll put it in as a second answer. $\endgroup$
    – b3m2a1
    Commented Sep 16, 2017 at 17:23
4
$\begingroup$

The following fixes up the syntax of your code, but the logic is still wrong.

MyIterativeSubsets[inlist_] :=
  Module[
      {listLength, powerSetLength, myPowerSet, pointer, counter, 
       currentElement, newSet, DebugFlag = True},
    If[! ListQ[inlist], Return["Please enter a list"]];
    listLength = Length[inlist];
    myPowerSet = {{}};
    pointer = 1;
    If[DebugFlag == True,
      Print["What was entered ", inlist];
      Print["List Length ", listLength];
      Print["Power Set is", myPowerSet]];
    While[pointer <= listLength,
      currentElement = inlist[[pointer]];
      powerSetLength = Length[myPowerSet];
      counter = 1;
      newSet = {};
      If[DebugFlag == True,
        Print["Current Element is ", currentElement];
        Print[powerSetLength];
        Print["Counter is ", counter]];
      While[counter <= powerSetLength, 
        newSet = 
          Append[newSet, Append[myPowerSet[[counter]], currentElement]];
        myPowerSet = Union[myPowerSet, newSet];
        counter++;
        If[DebugFlag == True,
          Print["New Set is ", newSet];
          Print["My Power Set is ", myPowerSet];
          Print["Counter is ", counter]]];
      pointer++];
    myPowerSet]

Perhaps the rewritten code will help you to debug your logic,

My own logic, when applied to the problem, tells me that finding a power set should involve the power of 2 of the number of elements of the set. Using this insight, I come up with

subsets[set_List] :=
  Module[{n, pwr, templates, rules},
    n = Length[set];
    pwr = 2^n;
    templates = Position[#, 1] & /@ IntegerDigits[Range[pwr] - 1, 2, n];
    rules = Table[{i} -> set[[i]], {i, n}];
    Sort[templates /. rules]]

This is not even close to optimum, but does implement my understanding of a power set in a direct way. It is certainly simpler and more efficient than your approach.

Here are some test cases.

subsets[{}]

{{}}}

subsets[{a}]

{{}, {a}}

subsets[{a, b, c, d}]

{{}, {a}, {b}, {c}, {d}, {a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}, {a, b, c}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}}

$\endgroup$
6
  • $\begingroup$ Your rules could be done with MapIndexed[Rule[#2, #]&,set] $\endgroup$
    – b3m2a1
    Commented Sep 16, 2017 at 4:34
  • $\begingroup$ @b3m2a1. Sure, but I wanted to keep things simple. I thought the OP would be more comfortable with Table. Maybe I am, too :-) $\endgroup$
    – m_goldberg
    Commented Sep 16, 2017 at 4:37
  • $\begingroup$ Makes sense. By the way, I liked the insight. Very clever. $\endgroup$
    – b3m2a1
    Commented Sep 16, 2017 at 4:38
  • $\begingroup$ @b3m2a1. I considered using Pick as you did, but I also considered the OP's demonstrated level of Mathematica knowledge. I was not interested in playing code golf with this problem. $\endgroup$
    – m_goldberg
    Commented Sep 16, 2017 at 4:40
  • $\begingroup$ Again, very reasonable. I thought the code-golf-y implementation kinda fun, so I posted that as an answer, too. $\endgroup$
    – b3m2a1
    Commented Sep 16, 2017 at 4:41
1
$\begingroup$

Rather than try to debug your code I thought I'd have a fresh go at the problem (I'm happy to delete if it's deemed off-topic).

As mentioned in the comments, you should check out AppendTo and look into how Modules and Functions work. There are any number of ways to build this function. I stayed away from any of the obvious functions (like, say, Subsets), and also from indexed approaches such as Table, While and the like.

powerset[list_] := 
  Join @@ NestList[
    With[{subsetlist = #}, 
      DeleteDuplicatesBy[Sort] @ Flatten[
        With[{le = #}, 
          If[MemberQ[#, le], Nothing, Join[{le}, #]] & /@ subsetlist
        ] & /@ list,
      1]] &, 
  {{}}, Length[list]];

Then

testlist = RandomSample[Alphabet[], 14];
powerset[testlist] == Subsets[testlist]

(* True *)

It's not terribly efficient -- in particular, it seems like there should be an easy way to avoid DeleteDuplicatesBy, but I couldn't think of anything that didn't involve indexing.

$\endgroup$

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