How to resolve the algorithm Power set step by step in the PL/I programming language

Published on 12 May 2024 09:40 PM
#Pl/i

How to resolve the algorithm Power set step by step in the PL/I programming language

Table of Contents

Problem Statement

A   set   is a collection (container) of certain values, without any particular order, and no repeated values. It corresponds with a finite set in mathematics. A set can be implemented as an associative array (partial mapping) in which the value of each key-value pair is ignored. Given a set S, the power set (or powerset) of S, written P(S), or 2S, is the set of all subsets of S.

By using a library or built-in set type, or by defining a set type with necessary operations, write a function with a set S as input that yields the power set 2S of S.

For example, the power set of     {1,2,3,4}     is For a set which contains n elements, the corresponding power set has 2n elements, including the edge cases of empty set. The power set of the empty set is the set which contains itself (20 = 1): And the power set of the set which contains only the empty set, has two subsets, the empty set and the set which contains the empty set (21 = 2):

Extra credit: Demonstrate that your language supports these last two powersets.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Power set step by step in the PL/I programming language

Source code in the pl/i programming language

*process source attributes xref or(!);
 /*--------------------------------------------------------------------
 * 06.01.2014 Walter Pachl  translated from REXX
 *-------------------------------------------------------------------*/
 powerset: Proc Options(main);
 Dcl (hbound,index,left,substr) Builtin;
 Dcl sysprint Print;
 Dcl s(4) Char(5) Var Init('one','two','three','four');
 Dcl ps   Char(1000) Var;
 Dcl (n,chunk,p) Bin Fixed(31);
 n=hbound(s);                      /* number of items in the list.   */
 ps='{} ';                         /* start with a null power set.   */
 Do chunk=1 To n;                  /* loop through the ...     .     */
   ps=ps!!combn(chunk);            /* a CHUNK at a time.             */
   End;
 Do While(ps>'');
   p=index(ps,' ');
   Put Edit(left(ps,p-1))(Skip,a);
   ps=substr(ps,p+1);
   End;

 combn: Proc(y) Returns(Char(1000) Var);
 /*--------------------------------------------------------------------
 * returns the list of subsets with y elements of set s
 *-------------------------------------------------------------------*/
 Dcl (y,base,bbase,ym,p,j,d,u) Bin Fixed(31);
 Dcl (z,l) Char(1000) Var Init('');
 Dcl a(20) Bin Fixed(31) Init((20)0);
 Dcl i Bin Fixed(31);
 base=hbound(s)+1;
 bbase=base-y;
 ym=y-1;
 Do p=1 To y;
   a(p)=p;
   End;
 Do j=1 By 1;
   l='';
   Do d=1 To y;
     u=a(d);
     l=l!!','!!s(u);
     End;
   z=z!!'{'!!substr(l,2)!!'} ';
   a(y)=a(y)+1;
   If a(y)=base Then
     If combu(ym) Then
       Leave;
   End;
 /* Put Edit('combn',y,z)(Skip,a,f(2),x(1),a); */
 Return(z);

 combu: Proc(d) Recursive Returns(Bin Fixed(31));
 Dcl (d,u) Bin Fixed(31);
 If d=0 Then
   Return(1);
 p=a(d);
 Do u=d To y;
   a(u)=p+1;
   If a(u)=bbase+u Then
     Return(combu(u-1));
   p=a(u);
   End;
 Return(0);
 End;
 End;

 End;

You may also check:How to resolve the algorithm Multisplit step by step in the VBScript programming language
You may also check:How to resolve the algorithm Set consolidation step by step in the F# programming language
You may also check:How to resolve the algorithm Hello world/Line printer step by step in the Phix programming language
You may also check:How to resolve the algorithm Loops/N plus one half step by step in the Groovy programming language
You may also check:How to resolve the algorithm Scope modifiers step by step in the PARI/GP programming language