Hey everyone,

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

Question: 

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.

Hi all,

First-time poster here. Got a question for Symbolic Computations and don't know how to do it. Please help me out.

Here is the question: 

There is a one-to-one correspondence between subsets of {1, 2, . . . , n} and binary lists of length n, that is, lists L = [x1, x2 , . . . , xn] where x1, x2, . . . , xn are elements of the set {0,1}.  The correspondence is given by associating to the set S the list L where xi = 1 if i is in S and 0 if not. For example, the set {1,3,5} corresponds to the list [1,0,1,0,1,0,0] if n = 7.

(a) Write a procedure list_to_set whose input is a binary list and whose output is the corresponding set. E. g., list_to_set([1,0,1,0,1]) will return the set {1,3,5}. Note that nops(L) is the length of a list.

(b) Write a procedure set_to_list whose input is a pair S,n where S is a subset of {1, 2, . . . , n} and n is a positive integer and whose output is the binary list of length n corresponding to the set S. E. g., if n = 5 then set_to_list({1,3,5},5) will return [1,0,1,0,1].

(c) Show by a few tests that each procedure works. Then apply set_to_list to each set in the powerset of {1, 2, 3, 4} to form all binary lists of length 4. Make a program to print out a table of the following form. (But the order need not be the same as that started below.)

   [0,0,0,0] <-->  {  }
   [1,0,0 0] <--> { 1 }
   [0,1,0,0] <--> { 2 } 
    ........
    etc

Some extra commas in the output is okay. You may obtain the power set of the set {1,2,...,n} by the command powerset(n); but you must first load the package combinat.

Please let me know if there are any questions. Thank you in advance.