How to create combinations numbers without repeating in C++

[capablanca]

Hi
How to create a program that ask to the user enter 10 numbers and the program can form all the combinations of 5 numbers without repeating. Thanks for any advice.

[donbock]

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

[newb16]

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]

@donbock
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]

@newb16
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]

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]

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]

@capablanca
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]

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

#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]

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]

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]

hi capablanca

this code can do .

#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 = 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;
               }
             }
           }
         }
       }
    cout<<endl<<endl;
    return 0;
}

[capablanca]

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

[Junjie]

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]

Can any one tell me how to do that

#       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..

[newb16]

Using recursion for example - each loop uses the variable of the outer loop as starting value and set of already known part of the combination generated in all outer loops.