Question: Procedures for One-to-One Correspondence

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.

Please Wait...