Question: PowerSet and RandSet Commands for Sets

Hey everyone,

Got another Symbolic question here that I have no idea how to begin. Please help again.


Note that if i is an integer then convert(i,base, 2) will convert i to a binary list (the binary representation of i in reverse order). Then you may use list_to_set to convert  this list to a set. Note that if i runs from 0 to 2^n-1 then list_to_set(convert(i,base,2) )  will run through all subsets of {1, 2, . . ., n}. 

(a) Use this idea to make your own procedure PowerSet which will given n,  produce the powerset of {1, 2, . . . , n}. Show by several examples that your procedure works. For your examples you should get nops(PowerSet(n)) = 2^(n). Check that this is the case.
(b) Use this idea to make a procedure RandSet which given n produces a random subset of {1, 2, . . . , n}. [Use rand to produce a random integer in the range 0..2^n-1 and then convert it to a subset of {1, 2, . . . , n}.]  Do NOT use PowerSet or powerset. Show by examples that it works for small n such as 5, 10, and 20 as well as for large n such as 100. It will even work for n = 1000, but the output will be rather large. On average a random subset of {1,2,...,n} will contain n/2 elements.

Again, please help me with this and thank you in advance. Your assistance is appreciated.

Please Wait...