Thread: Unique combinations of groups in C++ w/ recursion

  1. #1
    Registered User
    Join Date
    Apr 2010
    Posts
    2

    Unique combinations of groups in C++ w/ recursion

    <sigh> I wrote a long post for probably half an hour and then because it logged me out the whole thing got eaten. I spent about 5 hours today trying to work through this problem and look for some examples that I could understand to help me grasp it, with no success.

    I am looking for a simple, elegant solution to recursive function that takes n, the total amount of people, and k, the number of people per group. Then it displays all the unique combination's of groups. For example, n = 5, k = 3...
    543
    542
    541
    532
    531
    521
    432
    431
    421
    321

    The problem describes dividing up the problem by the functions calling itself twice with (n - 1, k - 1) and (n - 1, k). My code, which doesn't work, that I will post below, is using a string to store the numbers, I am open to suggestions but I do not want a solution involving a bunch of libraries. I am fairly sure, given the context of the problem, that it shouldn't be to overly complex. The problem describes the base case as being when K or n = 0 or when k > n.

    At this point I am looking for any advice or tips on this. If you do post a working example, I am not going to copy it because I actually want to learn this stuff, and I've had plenty of opportunities to copy complicated versions I couldn't make sense of.

    Code:
    include <iostream>
    
    using namespace std;
    
    string output = "";
    
    int showTeams (long n, long k, string p)
    {
        if (k == 0 || n == 0 || k > n)
        {
            output += p + " ";
            return 0;
        }
        else
        {
            showTeams(n - 1, k - 1, p+= static_cast<char>(n+48));
            showTeams(n - 1, k, p);
        }
    
    }
    
    int main()
    {
    
    showTeams(5,3, "");
    cout << output << endl;
    
    }

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Step 1: Since your first recursive call changes p, you must change the order of your two recursive calls, because the second one really really needs to use the original p.

    Step 2: Some of your combos are short because you're not quite paying enough attention to the difference between k > n (where the combo just can't happen) and n = 0 or k = 0 (where you're out of symbols so you're done). If you don't print the combo in the k > n case, then you will eliminate all those short combinations.

  3. #3
    Registered User
    Join Date
    Apr 2010
    Posts
    2
    Quote Originally Posted by tabstop View Post
    Step 1: Since your first recursive call changes p, you must change the order of your two recursive calls, because the second one really really needs to use the original p.

    Step 2: Some of your combos are short because you're not quite paying enough attention to the difference between k > n (where the combo just can't happen) and n = 0 or k = 0 (where you're out of symbols so you're done). If you don't print the combo in the k > n case, then you will eliminate all those short combinations.
    It helps to have someone else take a look, it seems obvious now but I didn't think of it at the time. So far its improved but still needs work I'll be working on it a lot tomorrow. Thanks!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. recursion? combinations of numbers
    By ominub in forum C Programming
    Replies: 2
    Last Post: 10-02-2009, 03:36 PM
  2. Template Recursion Pickle
    By SevenThunders in forum C++ Programming
    Replies: 20
    Last Post: 02-05-2009, 09:45 PM
  3. creating combinations of array values - recursion??
    By johndirect in forum C Programming
    Replies: 2
    Last Post: 11-20-2008, 12:49 PM
  4. unique pointer issue
    By George2 in forum C++ Programming
    Replies: 11
    Last Post: 02-14-2008, 11:25 PM
  5. a simple recursion question
    By tetra in forum C++ Programming
    Replies: 6
    Last Post: 10-27-2002, 10:56 AM