5

I'm trying to print out all possibilities of nCr, which are the combinations when order doesn't matter. So 5C1 there are 5 possibilities: 1 , 2, 3, 4, 5. 5C2 there are 10 possibilities: 1 2, 1 3, 1 4, 1 5, 2 3, 2 4, 2 5, 3 4, 3 5, 4 5.

I made functions that print what I want for r = 2, r = 3, and r = 4, and I sort of see the pattern, but I cant seem to make a working method for variable r:

public void printCombinationsChoose2(int n, int k) //for when k = 2
{
    for (int a = 1; a < n; a++)
    {
        for (int b = a + 1; b <= n; b++)
        {
            System.out.println("" + a + " " + b);
        }
    }
}

public void printCombinationsChoose3(int n, int k) //for when k = 3
{
    for (int a = 1; a < n - 1; a++)
    {
        for (int b = a + 1; b < n; b++)
        {
            for (int c = b + 1; c <= n; c++)
            {
                System.out.println("" + a + " " + b + " " + c);
            }
        }
    }
}

public void printCombinationsChoose4(int n, int k) //for when k = 4
{
    for (int a = 1; a < n - 2; a++)
    {
        for (int b = a + 1; b < n - 1; b++)
        {
            for (int c = b + 1; c < n; c++)
            {
                for (int d = c + 1; d <= n; d++)
                {
                    System.out.println("" + a + " " + b + " " + c + " " + d);
                }
            }
        }
    }
}

public void printCombinations(int n, int k) //Doesn't work
{
    int[] nums = new int[k];
    for (int i = 1; i <= nums.length; i++)
        nums[i - 1] = i;

    int count = 1;

    while (count <= k)
    {
        for (int a = nums[k - count]; a <= n; a++)
        {
            nums[k - count] = a;

            for (int i = 0; i < nums.length; i++)
                System.out.print("" + nums[i] + " ");
            System.out.println();
        }
        count++;
    }
}

So I think the layout of my last method is right, but I'm just not doing the right things, because when I call printCominbations(5, 2), it prints

1 2 
1 3 
1 4 
1 5 
1 5 
2 5 
3 5 
4 5 
5 5

when it should be what I said earlier for 5C2.

Edit The last example was bad. This is a better one to illustrate what it's doing wrong: printCombinations(5, 3) gives this:

1 2 3 
1 2 4 
1 2 5 
1 2 5 
1 3 5 
1 4 5 
1 5 5 
1 5 5 
2 5 5 
3 5 5 
4 5 5 
5 5 5

How do I get it to be:

1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
Pat Needham
  • 5,698
  • 7
  • 43
  • 63
  • Refer to [Permutation Algorithm][1] [1]: http://stackoverflow.com/questions/3346249/java-permutation-algorithm – MoveFast Oct 02 '11 at 14:09
  • That only works for when your r is 2. In my example that doesn't work, the r = 2, but I want it to work for any r – Pat Needham Oct 02 '11 at 14:20

5 Answers5

7

How about this:

public class Test {

    public static void main(final String[] args) {
        print_nCr(7, 4);
    }

    public static final void print_nCr(final int n, final int r) {
        int[] res = new int[r];
        for (int i = 0; i < res.length; i++) {
            res[i] = i + 1;
        }
        boolean done = false;
        while (!done) {
            System.out.println(Arrays.toString(res));
            done = getNext(res, n, r);
        }
    }

    /////////

    public static final boolean getNext(final int[] num, final int n, final int r) {
        int target = r - 1;
        num[target]++;
        if (num[target] > ((n - (r - target)) + 1)) {
            // Carry the One
            while (num[target] > ((n - (r - target)))) {
                target--;
                if (target < 0) {
                    break;
                }
            }
            if (target < 0) {
                return true;
            }
            num[target]++;
            for (int i = target + 1; i < num.length; i++) {
                num[i] = num[i - 1] + 1;
            }
        }
        return false;
    }
}

The key to this solution for me was to look at the problem as a numbering system and you want to increase a number by one and every time you reach an upper bound, you just carry the excess to the left one and ... You just need to implement the increasing algorithm correctly...

pbaris
  • 4,525
  • 5
  • 37
  • 61
Mostafa Zeinali
  • 2,456
  • 2
  • 15
  • 23
4

The first point where your code deviates from the expectation is here:

...
1 2 5 
1 2 5    <-- first bad output
1 3 5
...

So ask yourself three things:

  • What should have happened in that line of code with the given state of the variables?

  • Why doesn't do my code exactly that?

  • What must be changed to achieve that?

The answer for the first part is like this:

  • It should have incremented the 2 to 3 and it should have set the following numbers to 4, 5, ... similar to the initialisation of nums.

The second and third part is your part again.

BTW: When you come back because you need more help, please explain in detail what you have deduced so far and clean up and shorten the question quite a bit.

A.H.
  • 63,967
  • 15
  • 92
  • 126
  • Your advice, to do something similar to the initialization of `nums`, made it work. All I did was put another for loop at the beginning of the while loop which sets `nums[i] = nums[i - 1] + 1` where i starts at `k - (count - 1)` and runs while it is less than k, incrementing i by 1 each time. – Pat Needham Oct 02 '11 at 20:05
  • Either you have changed something else too, since the changes alone still give wrong result for the (5,3) case. – A.H. Oct 02 '11 at 20:35
  • You're right. I was calling printCombinationsChoose3(), not printCombinations(). When I tried the latter one, I got wrong results – Pat Needham Oct 03 '11 at 00:22
1

I have done it in c++

#include <iostream>

using namespace std;
#define ARR_LIMIT 100
int arr[ARR_LIMIT];

void _ncr(int N,int R, int n,int r , int start )
{
    if(r>0)
    {
        for(int i = start ; i <= start + (n-r); i++)
        {
            arr[R-r] = i;
            _ncr(N,R,N-i, r-1, i+1 );
        }
    }
    else
    {
        for(int i=0;i<R;i++)
        {
            cout << arr[i] << " ";
            if(i==R-1)
                cout<<"\n";
        }
    }

}

void ncr(int n,int r)
{
    //Error checking of parameters
    bool error = false;
    if( n < 1)
    {
        error = true;
        cout<< "ERROR : n should be greater 0 \n";
    }
    if( r < 1)
    {
        error = true;
        cout<< "ERROR : r should be greater 0 \n";
    }
    if(r > n)
    {
        error = true;
        cout<< "ERROR : n should be greater than or equal to r \n";
    }
    // end of Error checking of parameters
    if(error)
        return;
    else
        _ncr(n,r,n,r,1);
}

int main()
{
    int n,r;
    cout << "Enter n : ";
    cin >> n;
    cout << "Enter r : ";
    cin >> r;
    ncr(n,r);
    return 0;
}
user2114956
  • 11
  • 3
1

OK... What is the solution when we know we need loops, but not the number of them?? RECURSION... You need to use a recursive implementation. Have this in mind: ANYTIME, you need loops but the number of the nested loops can only be known at runtime, based on the specific parameters of the problem, you should use recursive methods... I'll give you some time to try it yourself, I'll be back to give you the final implementation...

Mostafa Zeinali
  • 2,456
  • 2
  • 15
  • 23
  • 2
    Recursion is not the only way to solve this problem. It is an easy solution, yes. But problems as simple as that should not be solved with the biggest hammer available but with the smallest hammer suitable. – A.H. Oct 02 '11 at 18:13
  • Yes sir... You are absolutely right... So I tried to implement it without Recursion and did so... See below: – Mostafa Zeinali Oct 03 '11 at 06:49
0

The layout of function printCombination() seems wrong. The while loop will iterate two times, for count = 1 and count = 2.

When count = 1, only values in nums[0][here] will change, since in this case k - count = 1. Hence,
1,2
1,3
1,4 and
1,5.

And when count = 2, only values in nums[here][1] will change, since here k - count = 0. Hence
1,5
2,5
3,5
4,5 and
5,5

KK.
  • 783
  • 8
  • 20