C++ Newbie needs helps for printing combinations of integers

Question

Suppose I am given:

1. A range of integers iRange (i.e. from 1 up to iRange) and
2. A desired number of combinations

I want to find the number of all possible combinations and print out all these combinations.

For example:

Given: iRange = 5 and n = 3

Then the number of combinations is iRange! / ((iRange!-n!)*n!) = 5! / (5-3)! * 3! = 10 combinations, and the output is:

123 - 124 - 125 - 134 - 135 - 145 - 234 - 235 - 245 - 345

Another example:

Given: iRange = 4 and n = 2

Then the number of combinations is iRange! / ((iRange!-n!)*n!) = 4! / (4-2)! * 2! = 6 combinations, and the output is:

12 - 13 - 14 - 23 - 24 - 34

My attempt so far is:

#include <iostream>
using namespace std;

int iRange= 0;
int iN=0;

int fact(int n)
{
    if ( n<1)
        return 1;
    else
    return fact(n-1)*n;
}

void print_combinations(int n, int iMxM)
{
    int iBigSetFact=fact(iMxM);
    int iDiffFact=fact(iMxM-n);
    int iSmallSetFact=fact(n);
    int iNoTotComb = (iBigSetFact/(iDiffFact*iSmallSetFact));
    cout<<"The number of possible combinations is: "<<iNoTotComb<<endl;
    cout<<" and these combinations are the following: "<<endl;


    int i, j, k;
    for (i = 0; i < iMxM - 1; i++)
    {
        for (j = i + 1; j < iMxM ; j++)
        {
            //for (k = j + 1; k < iMxM; k++)
                cout<<i+1<<j+1<<endl;
        }
    }
}

int main()
{
    cout<<"Please give the range (max) within which the combinations are to be found: "<<endl;
    cin>>iRange;
    cout<<"Please give the desired number of combinations: "<<endl; 
    cin>>iN;
    print_combinations(iN,iRange);
    return 0;   
}

My problem: The part of my code related to the printing of the combinations works only for n = 2, iRange = 4 and I can't make it work in general, i.e., for any n and iRange.

Himself

Couple points - please state your request in the form of a question. Also, think about what you're asking. I believe what you are looking for is a permutation algorithm (iRange P n), which is all combinations of 'n' numbers selected from 'iRange' values. – Akerley

In your example output: 123 - 124 - 125 - 134 - 135 - 142 - 145 - 234 - 245 - 345, you have 124 and 142, which looks like a permutation. A combination should get you: 123 - 124 - 125 - 134 - 135 - 145 - 234 - 235 - 245 - 345. – Ribbonfish

what I am asking for is help/ideas/guidance for changing the for loops so that my code works for any values of n and iRange, and produce thus output like in the examples. I think that maybe the for loops should be replaced by another recursive function, or thansform the present function to a recursive one. But i cannot think of a base case for the reursion. – Himself

@Mike DeSimone thanks i just corrected it. – Himself

The first hit for next_combination in Google is a decent read: sites.google.com/site/hannuhelminen/next_combination – Wunder

MANYYYYYYYY THANKS TO ALL OF U!!!!!!! @Orpha & @Mike De Simone your answers gave me a good insight to the algorithm design needed. @Alex & Harry your answers gave me nice solutions to my problem. @J.F. Sebastian thanks for giving me info for further reading. I kind of prefer harrys because of simplicity. Thanks a lot all of u again – Himself

Answer 1

Here is your code edited :D :D with a recursive solution:

#include <iostream>

int iRange=0;   
int iN=0;           //Number of items taken from iRange, for which u want to print out the combinations
int iTotalCombs=0;
int* pTheRange;
int* pTempRange;

int find_factorial(int n)
{
    if ( n<1)
        return 1;
    else
    return find_factorial(n-1)*n;
}

//--->Here is another solution:
void print_out_combinations(int *P, int K, int n_i) 
{
    if (K == 0)
    {
        for (int j =iN;j>0;j--)
        std::cout<<P[j]<<" ";
        std::cout<<std::endl;
    }
    else
        for (int i = n_i; i < iRange; i++) 
        {
            P[K] = pTheRange[i];
            print_out_combinations(P, K-1, i+1);
        }
}
//Here ends the solution...

int main() 
{
    std::cout<<"Give the set of items -iRange- = ";
    std::cin>>iRange;
    std::cout<<"Give the items # -iN- of iRange for which the combinations will be created = ";
    std::cin>>iN;

    pTheRange = new int[iRange];
    for (int i = 0;i<iRange;i++)
    {
        pTheRange[i]=i+1;
    }
    pTempRange = new int[iN];

    iTotalCombs = (find_factorial(iRange)/(find_factorial(iRange-iN)*find_factorial(iN)));

    std::cout<<"The number of possible combinations is: "<<iTotalCombs<<std::endl;
    std::cout<<"i.e.the combinations of "<<iN<<" elements drawn from a set of size "<<iRange<<" are: "<<std::endl;
    print_out_combinations(pTempRange, iN, 0);
    return 0;
}

Cotter

Answer 2

Your solution will only ever work for n=2. Think about using an array (combs) with n ints, then the loop will tick up the last item in the array. When that item reaches max update then comb[n-2] item and set the last item to the previous value +1.

Basically working like a clock but you need logic to find what to uptick and what the next minimum value is.

Orpha

Answer 3

Looks like a good problem for recursion.

Define a function f(prefix, iMin, iMax, n), that prints all combinations of n digits in the range [iMin, iMax] and returns the total number of combinations. For n = 1, it should print every digit from iMin to iMax and return iMax - iMin + 1.

For your iRange = 5 and n = 3 case, you call f("", 1, 5, 3). The output should be 123 - 124 - 125 - 134 - 135 - 145 - 234 - 235 - 245 - 345.

Notice that the first group of outputs are simply 1 prefixed onto the outputs of f("", 2, 5, 2), i.e. f("1", 2, 5, 2), followed by f("2", 3, 5, 2) and f("3", 4, 5, 2). See how you would do that with a loop. Between this, the case for n = 1 above, and traps for bad inputs (best if they print nothing and return 0, it should simplify your loop), you should be able to write f().

I'm stopping short because this looks like a homework assignment. Is this enough to get you started?

EDIT: Just for giggles, I wrote a Python version. Python has an easier time throwing around sets and lists of things and staying legible.

#!/usr/bin/env python

def Combos(items, n):
    if n <= 0 or len(items) == 0:
        return []
    if n == 1:
        return [[x] for x in items]
    result = []
    for k in range(len(items) - n + 1):
        for s in Combos(items[k+1:], n - 1):
            result.append([items[k]] + s)
    return result

comb = Combos([str(x) for x in range(1, 6)], 3)
print len(comb), " - ".join(["".join(c) for c in comb])

Note that Combos() doesn't care about the types of the items in the items list.

Ribbonfish

Thanks I am going to give it a try and let u know. its no homework, i am learning c++ coding using a book. I am trying to code sth bigger, and this is just a small part. I want to go through the rows of an mxm 2D maze but not "one at a time" but taking "subsets" of the maze rows i.e. i want to "scan" the maze rows considering some "empty/non interesting" rows. My idea for this was to create combinations o fthe rows subsets and scan these subsets then. Maybe was wrong idea and there is a better alternative :d – Himself

I think maze pathing is a classic recursion problem. Good luck. – Ribbonfish

Answer 4

Here's an example of a plain recursive solution. I believe there exists a more optimal implementation if you replace recursion with cycles. It could be your homework :)

#include <stdio.h>

const int iRange = 9;
const int n = 4;


// A more efficient way to calculate binomial coefficient, in my opinion
int Cnm(int n, int m)
{
    int i;
    int result = 1;

    for (i = m + 1; i <= n; ++i)
        result *= i;

    for (i = n - m; i > 1; --i)
        result /= i;

    return result;
}


print_digits(int *digits)
{
    int i;
    for (i = 0; i < n; ++i) {
        printf("%d", digits[i]);
    }
    printf("\n");
}

void plus_one(int *digits, int index)
{
    int i;

    // Increment current digit
    ++digits[index];

    // If it is the leftmost digit, run to the right, setup all the others
    if (index == 0) {
        for (i = 1; i < n; ++i)
            digits[i] = digits[i-1] + 1;
    }
    // step back by one digit recursively
    else if (digits[index] > iRange) {
        plus_one(digits, index - 1);
    }
    // otherwise run to the right, setting up other digits, and break the recursion once a digit exceeds iRange
    else {
        for (i = index + 1; i < n; ++i) {
            digits[i] = digits[i-1] + 1;

            if (digits[i] > iRange) {
                plus_one(digits, i - 1);
                break;
            }
        }
    }
}

int main()
{
    int i;
    int digits[n];

    for (i = 0; i < n; ++i) {
        digits[i] = i + 1;
    }

    printf("%d\n\n", Cnm(iRange, n));

    // *** This loop has been updated ***
    while (digits[0] <= iRange - n + 1) {
        print_digits(digits);
        plus_one(digits, n - 1);
    }

    return 0;
}

Freelance

thanks for your answer. i tried your code and it compiles however gives wrongs results: e.g. for: const int iRange = 5; const int n = 2; Output---> 10 13 14 15 23 24 25 34 35 45 one solution is missing i think – Himself

Sorry, I messed up with the main loop. Its logic is now fixed - once the first digit becomes equal to (iRange - n + 1), it's the last time the digits are printed, because the following call to plus_one() will increment every digit. – Freelance

Answer 5

This is my C++ function with different interface (based on sts::set) but performing the same task:

typedef std::set<int> NumbersSet;
typedef std::set<NumbersSet> CombinationsSet;

CombinationsSet MakeCombinations(const NumbersSet& numbers, int count)
{
  CombinationsSet result;

  if (!count) throw std::exception();

  if (count == numbers.size())
  {
    result.insert(NumbersSet(numbers.begin(), numbers.end()));
    return result;
  }

  // combinations with 1 element
  if (!(count - 1) || (numbers.size() <= 1))
  {
    for (auto number = numbers.begin(); number != numbers.end(); ++number)
    {
      NumbersSet single_combination;
      single_combination.insert(*number);
      result.insert(single_combination);
    }
    return result;
  }

  // Combinations with (count - 1) without current number
  int first_num = *numbers.begin();
  NumbersSet truncated_numbers = numbers;
  truncated_numbers.erase(first_num);
  CombinationsSet subcombinations = MakeCombinations(truncated_numbers, count - 1);

  for (auto subcombination = subcombinations.begin(); subcombination != subcombinations.end(); ++subcombination)
  {
    NumbersSet cmb = *subcombination;
    // Add current number
    cmb.insert(first_num);
    result.insert(cmb);
  }

  // Combinations with (count) without current number
  subcombinations = MakeCombinations(truncated_numbers, count);
  result.insert(subcombinations.begin(), subcombinations.end());

  return result;
}

Unpeg

Answer 6

I created a next_combination() function similar to next_permutation(), but valid input is required to make it work

//nums should always be in ascending order

    vector <int> next_combination(vector<int>nums, int max){
    int size = nums.size();
    
    if(nums[size-1]+1<=max){
        nums[size-1]++;
        return nums;
    }else{
        if(nums[0] == max - (size -1)){
            nums[0] = -1;
            return nums; 
        }
        
        int pos;
        int negate = -1;
        for(int i = size-2; i>=0; i--){
            if(nums[i]+1 <= max + negate){
                pos = i;
                break;
            }
            negate --;
        }
        nums[pos]++;
        pos++;
        while(pos<size){
            nums[pos] = nums[pos-1]+1;
            pos++;
        }
    }
    return nums;
}

Nereid