Question

Write a recursive algorithm S(C,D,m,n) with the following requirements:
1) C is an array with m elements stored in positions C[1,...,m]
2) D is an array with n elements stored in positions D[1,...,n]
3) S outputs all the sets Y such that each Y contains all the elements found in array D and each contains a distinct subset of C.
4) There is a function print(X,z) which outputs the set X containing all elements in X[1,...z]. It outputs the empty set if z=0.

Answer 1

1) In what language?
2) Where's your attempt? Why would anyone just do your homework for you?

Answer 2

1) No specific Language
2) I never ask others to do my homework for me, NEVER! I just had no idea how to start.

Approach:
To find S(C,D,m,n), suppose we know how to find S(C,D,m-1,n), then, S(C,D,m,n) = copying the S(C,D,m-1,n), and then copying S(C,D,m-1,n) again with the mth element attached in each element. Finally, append D to each element to that array.
E.g.
Given C={a,b} , D={c,d}
Assume we know the the power set of C={a}, i.e. \(\phi\), and {a}
Then copy the power set twice, i.e. \(\phi\), {a}, \(\phi\), and {a}
And for each element in the second copy, add b to it, i.e. \(\phi\), {a}, \(\phi, b\), and {a, b}, which is the same as \(\phi\), {a}, \(b\), and {a, b}. Finally appended D to each element.

Answer 3

Btw, when we say algorithm, I don't think we need to use a specific language. Using pseudo code would be sufficient.

Answer 4

What does 'contains a distinct subset' mean?

Answer 5

Is Y a set of sets? And it must contain a set that is a subset of C?

Answer 6

Tips
1. where/what is your y and z?
2. what is your ending statement?

Answer 7

@wio
Y is a set of subsets.
E.g.
C={1,2} D={a,b}
S(C,D,2,2) outputs: {{a,b},{1,a,b},{2,a,b},{1,2,a,b}}

@R-
1) Not sure what you mean by 'y'., but for z, that would be the number of elements from the 1st element of an array to be output
2) Ending statement (the base case, I suppose) would be the printing the array D.

Answer 8

So all you really need to do is get the power set of C, and then union all the sets with the elements of D

Answer 9

Yes, basically, it is.

Answer 10

Why use recursion?

Answer 11

Because we are learning recursion, so our teacher wanted us to practice solving problems using recursion.

Answer 12

I suppose you can use recursion to get the power set.

Answer 13

Uhg, not separating this out into two distinct recognizable tasks is a bit obnoxious, but oh well.