How to create combinations numbers without repeating in C++

**donbock** · Jul 18 '10, 04:09 AM

How many combinations of 5 numbers can you form from ten distinct numbers? Do you know the formulas for combinations and permutations?

**newb16** · Jul 18 '10, 06:57 PM

Code:

dostuff(set<int> picked, set<int> remaining)
{
  if (size of 'picked' is 5) print its content
    else
  for ('item' in all items in 'remaining' that are greater than the largest item in 'picked')
  {
    dostuff(picked+'item', remaining-'item');
  }
}
...
dostuff(empty set, <1..10> )

So ensuring that i-th element of combination is greater than previous guarantees that they will not repeat.

If numbers were hardcoded from 1 to 10, 'remaining' set may be dropped and number from the greatest in 'picked' to 10 used instead.

Yes, it will be rather slow because each set operation will allocate memory. Bit sets pre-allocated for each recursion step will probably be faster.

**capablanca** · Jul 20 '10, 03:44 AM

Originally posted by donbock

How many combinations of 5 numbers can you form from ten distinct numbers? Do you know the formulas for combinations and permutations?

Hi donbock
This is the formula for combination:

c = n!/(r! * (n - r)!)
c = 10!/(5! * (10 - 5)!)
c = 252 COMBINATIONS WITHOUT REPETITION

I think I do not need to use the formula for permutation. Thanks

**capablanca** · Jul 20 '10, 05:17 AM

Originally posted by newb16

Code:

dostuff(set<int> picked, set<int> remaining)
{
  if (size of 'picked' is 5) print its content
    else
  for ('item' in all items in 'remaining' that are greater than the largest item in 'picked')
  {
    dostuff(picked+'item', remaining-'item');
  }
}
...
dostuff(empty set, <1..10> )

So ensuring that i-th element of combination is greater than previous guarantees that they will not repeat.

If numbers were hardcoded from 1 to 10, 'remaining' set may be dropped and number from the greatest in 'picked' to 10 used instead.

Yes, it will be rather slow because each set operation will allocate memory. Bit sets pre-allocated for each recursion step will probably be faster.

Hi newb16
I appreciate you are trying to help me but I do not get what you reply me can you give me an example in c++. Thanks

**donbock** · Jul 20 '10, 01:42 PM

This problem can be split into three separate tasks:

Acquire ten input values from the user.
Verify the values are valid (all values are distinct).
Generate a list of the "10 choose 5" combinations.

I suggest that you store the ten values in an array, generate the "10 choose 5" list of the values 0-9, and finally use those values to index into the input array to get the user's values. I would start by printing out the 0-9 values, and only replace them with the user inputs after your combination function is working.

As you pointed out earlier, there are 252 combinations; that is 252 lines of output. How do you plan to verify the output is correct and complete? Order is unimportant in combinations, but perhaps there is a certain order that will make verification easier.If this is an assignment, then how will your instructor verify your work? It is worth your while to produce an output that is more easily recognized as correct by the instructor.

**donbock** · Jul 20 '10, 03:38 PM

The "10 choose 5" combinations of the numbers 0-9 are:
0 and all "9 choose 4" combinations of 1-9; and
1 and all "8 choose 4" combinations of 2-9; and
2 and all "7 choose 4" combinations of 3-9; and
3 and all "6 choose 4" combinations of 4-9; and
4 and all "5 choose 4" combinations of 5-9; and
5 and all "4 choose 4" combinations of 6-9.

Similarly,
The "9 choose 4" combinations of 1-9 are:
1 and all "8 choose 3" combinations of 2-9; and
2 and all "7 choose 3" combinations of 3-9; and
3 and all "6 choose 3" combinations of 4-9; and
4 and all "5 choose 3" combinations of 5-9; and
5 and all "4 choose 3" combinations of 6-9; and
6 and all "3 choose 3" combinations of 7-9.

And so on. It might be helpful to think of each combination as being composed of a fixed prefix and a yet-to-be determined suffix sub-combination.

**newb16** · Jul 20 '10, 07:35 PM

Originally posted by capablanca

Hi newb16
I appreciate you are trying to help me but I do not get what you reply me can you give me an example in c++. Thanks

This will be not a reply but a complete debugged and working solution teaching nothing. I suggested to use a recusrive function, where on each iteration generated partial combination is passed, and then either printed if it is of required size, or new level of recursion is launched, adding new numbers to the combination in the following way:
suppose we have number from 1 to 10, and partially generated combination of size 3 - {3,5,6}; Starting from the greater number not included in the set, numbers 7 to 10 are added during 4 iteration of loop.

**capablanca** · Jul 22 '10, 04:20 AM

Originally posted by donbock

This problem can be split into three separate tasks:

Acquire ten input values from the user.
Verify the values are valid (all values are distinct).
Generate a list of the "10 choose 5" combinations.

I suggest that you store the ten values in an array, generate the "10 choose 5" list of the values 0-9, and finally use those values to index into the input array to get the user's values. I would start by printing out the 0-9 values, and only replace them with the user inputs after your combination function is working.

As you pointed out earlier, there are 252 combinations; that is 252 lines of output. How do you plan to verify the output is correct and complete? Order is unimportant in combinations, but perhaps there is a certain order that will make verification easier.If this is an assignment, then how will your instructor verify your work? It is worth your while to produce an output that is more easily recognized as correct by the instructor.

Hi donbock
This is not an assignment. I have 6 months learning C++ by myself
This is what I have created so far:

Code:

#include <iostream>
#include <iomanip>

using namespace std;

int main()
{
    int x=0 ;
    int array[10];

    cout<<"\n   Enter 10 numbers differents: ";

    for(int i=0; i<10; i++)
      {
           cin>>array[i];
           if(array[i]==array[i+1])
            {
              cout<<"\n\n   You just enter a number several times  "
                   "try again\n";
            }
      }
      cout<<endl;
      cout<<setw(80)<<"   Generating All Combination Elements Without" 
                        " Repetition\n";
      cout<<setw(85)<<"============================================"
      "==================\n\n";

      for (int i = 0; i <6; ++i)
       {
        for (int j = i+1; j <7; ++j)
         {
          for (int k = i+2; k <8; ++k)
           {
            for (int l = i+3; l <9; ++l)
             {
              for (int m = i+4; m <10; ++m)
               {
                 ++x;
                 cout<<setw(36)<<x<<")      "<<array[i]<<"     "
                 <<array[j]<<"     "<<array[k]<<"     "
                 <<array[l]<<"     "<<array[m]<<endl;
               }
             }
           }
         }
       }
    cout<<endl<<endl;
    return 0;
}

As you can see the code is wrong:
First, when I enter two numbers that are equals, the message do not appear
Second, I can not get your idea to the code. Can you help me. Thanks

**donbock** · Jul 22 '10, 08:20 AM

To determine if array[i] is a duplicate you need to compare it to all previous array elements, from 0 to i-1. Accessing element i+1 is a mistake in two ways, you're looking at an uninitialized element of the array; and when i=9 you're looking past the end of the array.

Refer to reply #7. The most natural way to solve this problem is through recursion.

I'm not a C++ programmer, but I've heard rumors of nifty dynamic array class templates (vector comes to mind) that would be a very handy way to pass the prefix combination to the recursive function.

I need to step back now that you're moving from general algorithm to specific C++ code. There are many C++ experts who can help you with coding details.

**capablanca** · Jul 30 '10, 11:10 PM

Hi
Is there somebody can help me with my program of how to create combinations numbers without repeating in C++ using iteration (loops), not a recursive function. Thanks

**Junjie** · Jul 31 '10, 03:41 AM

hi capablanca

this code can do .

Code:

#include <iostream>
#include <iomanip>
 
using namespace std;
 
int main()
{
    int x=0 ;
    int array[10];
 
    cout<<"\n   Enter 10 numbers differents: ";
 
    for(int i=0; i<10; i++)
      {
           cin>>array[i];
           if(array[i]==array[i+1])
            {
              cout<<"\n\n   You just enter a number several times  "
                   "try again\n";
            }
      }
      cout<<endl;
      cout<<setw(80)<<"   Generating All Combination Elements Without" 
                        " Repetition\n";
      cout<<setw(85)<<"============================================"
      "==================\n\n";
 
      for (i = 0; i <6; ++i)
       {
        for (int j = [B]i+1[/B]; j <7; ++j)
         {
          for (int k = [B]j+1[/B]; k <8; ++k)
           {
            for (int l = [B]k+1[/B]; l <9; ++l)
             {
              for (int m =[B] l+1[/B]; m <10; ++m)
               {
                 ++x;
                 cout<<setw(36)<<x<<")      "<<array[i]<<"     "
                 <<array[j]<<"     "<<array[k]<<"     "
                 <<array[l]<<"     "<<array[m]<<endl;
               }
             }
           }
         }
       }
    cout<<endl<<endl;
    return 0;
}

**capablanca** · Jul 31 '10, 04:55 AM

Originally posted by Junjie

hi capablanca

this code can do .

Code:

#include <iostream>
#include <iomanip>
 
using namespace std;
 
int main()
{
    int x=0 ;
    int array[10];
 
    cout<<"\n   Enter 10 numbers differents: ";
 
    for(int i=0; i<10; i++)
      {
           cin>>array[i];
           if(array[i]==array[i+1])
            {
              cout<<"\n\n   You just enter a number several times  "
                   "try again\n";
            }
      }
      cout<<endl;
      cout<<setw(80)<<"   Generating All Combination Elements Without" 
                        " Repetition\n";
      cout<<setw(85)<<"============================================"
      "==================\n\n";
 
      for (i = 0; i <6; ++i)
       {
        for (int j = [B]i+1[/B]; j <7; ++j)
         {
          for (int k = [B]j+1[/B]; k <8; ++k)
           {
            for (int l = [B]k+1[/B]; l <9; ++l)
             {
              for (int m =[B] l+1[/B]; m <10; ++m)
               {
                 ++x;
                 cout<<setw(36)<<x<<")      "<<array[i]<<"     "
                 <<array[j]<<"     "<<array[k]<<"     "
                 <<array[l]<<"     "<<array[m]<<endl;
               }
             }
           }
         }
       }
    cout<<endl<<endl;
    return 0;
}

Hi Junjie
The program works Thanks
Can you explain a little bit how the for loops works, once again Thanks

**Junjie** · Jul 31 '10, 06:36 AM

Hi capablanca

You should look carefully writed by donbock:

The "10 choose 5" combinations of the numbers 0-9 are:
0 and all "9 choose 4" combinations of 1-9; and
1 and all "8 choose 4" combinations of 2-9; and
2 and all "7 choose 4" combinations of 3-9; and
3 and all "6 choose 4" combinations of 4-9; and
4 and all "5 choose 4" combinations of 5-9; and
5 and all "4 choose 4" combinations of 6-9.

Similarly,
The "9 choose 4" combinations of 1-9 are:
1 and all "8 choose 3" combinations of 2-9; and
2 and all "7 choose 3" combinations of 3-9; and
3 and all "6 choose 3" combinations of 4-9; and
4 and all "5 choose 3" combinations of 5-9; and
5 and all "4 choose 3" combinations of 6-9; and
6 and all "3 choose 3" combinations of 7-9.

The "8 choose 4" combinations of 2-9 are:
2 and all "7 choose 2" combinations of 3-9:and
3 and all "6 choose 2" combinations of 4-9:and
4 and all "5 choose 2" combinations of 5-9:and
5 and all "4 choose 2" combinations of 6-9:and
6 and all "3 choose 2" combinations of 7-9:and
7 and all "2 choose 2" combinations of 8-9.

if you can understand it,and find it is orderliness.

I just made your code change,and the second for loop of the first number is determined by the first loop,and the first number in the third loop is determined by the second loop,and so on,only six time for per loop.

**jasim88** · Aug 19 '10, 09:51 AM

Can any one tell me how to do that

Code:

#       for (i = 0; i <6; ++i)
#        {
#         for (int j = i+1; j <7; ++j)
#          {
#           for (int k = j+1; k <8; ++k)
#            {
#             for (int l = k+1; l <9; ++l)
#              {
#               for (int m = l+1; m <10; ++m)
#                {
#                  ++x;
#                  cout<<setw(36)<<x<<")      "<<array[i]<<"     "
#                  <<array[j]<<"     "<<array[k]<<"     "
#                  <<array[l]<<"     "<<array[m]<<endl;
#                }
#              }
#            }
#          }
#        }

but with unknown number of loops..

How to create combinations numbers without repeating in C++

How to create combinations numbers without repeating in C++

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment