Thread: Sets Problem

  1. #1
    Registered User
    Join Date
    Apr 2008
    Posts
    3

    Sets Problem

    How do you write a recursive algorithm for finding all the subsets of a given number:
    i.e if 2 is entered it should give
    1,2,12
    and if it is 3
    1,2,3,12,13,23,123

    It has to be recursive and has you are allowed to use only 1 iteration. I know how do do this non-recursively but I'm not sure how to do it recursively.

    BTW this is a console application.

    Thanks for your help!

  2. #2
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    What's your best attempt?

    What do you think you should recurse on? What should be your stopping point?

  3. #3
    Registered User
    Join Date
    Apr 2008
    Posts
    3
    I realized you have to recurse on size-1 and then iterate each with a number in front. i.e.
    for an input of size 5, the size 2 array will be:

    12
    13
    14
    15
    23
    24
    25
    34
    35
    45

    the size 3 array will be:

    123
    124
    125
    134
    135
    145
    234
    235
    245
    345

    The only changes are the numbers in bold, but I cant exactly figure out how to write the algorithm. The stopping point is going to be size one.
    Last edited by inevitable; 04-03-2008 at 10:01 AM.

  4. #4
    Registered User nepper271's Avatar
    Join Date
    Jan 2008
    Location
    Brazil
    Posts
    50
    I believe you should do your recursion as:
    1 - The subsets of n are all subsets of n - 1, and all subsets of n - 1, each increased by the element n.
    ex:
    Code:
    P(2) = { O, {1}, {2}, {1,2} }
    P(3) = { O, {1} , {2} , {3} , {1,2} , {1,3} , {2,3} , {1,2,3} }
     = { O, {1}, {2}, {1,2} } U { OU{3}, {1}U{3}, {2}U{3} , {1,2}U{3} }
    where O is the empty set, and U is the union operator. See that we have a set of sets.

  5. #5
    Registered User
    Join Date
    Apr 2008
    Posts
    3
    This uses a different recursive strategy. I need one that refers to it's previous set size rather than the previous n.
    Last edited by inevitable; 04-03-2008 at 12:24 PM.

  6. #6
    3735928559
    Join Date
    Mar 2008
    Location
    RTP
    Posts
    838
    Quote Originally Posted by inevitable View Post
    This uses a different recursive strategy. I need one that refers to it's previous set size rather than the previous n.
    not sure if it's exactly what you're looking for here, but to compute all possible combinations of X length words of values [1,Y-1], count from 0->(X^Y) in base y.

    here's something i c&p'd out of an old PHP project.

    Code:
    $test_base = 9;
    $steps_x = 5;
    $steps_y = pow($test_base,$steps_x);
    for($i=0;$i<$steps_y;$i++)
    {
    	$row = base_convert($i,10,$test_base);
    	print($row);
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. A question related to strcmp
    By meili100 in forum C++ Programming
    Replies: 6
    Last Post: 07-07-2007, 02:51 PM
  2. WS_POPUP, continuation of old problem
    By blurrymadness in forum Windows Programming
    Replies: 1
    Last Post: 04-20-2007, 06:54 PM
  3. Problem with RPC and scanf
    By Ricardo_R5 in forum C Programming
    Replies: 11
    Last Post: 01-08-2007, 06:15 PM
  4. RE: client/server shared memory problem
    By hampycalc in forum C Programming
    Replies: 0
    Last Post: 03-10-2006, 02:26 PM
  5. Laptop Problem
    By Boomba in forum Tech Board
    Replies: 1
    Last Post: 03-07-2006, 06:24 PM