Thread: Printing combination results to 'container'

Background: To print combinations of r from n (i.e nCr) not to console but to a 'container' (here array) for further manipulation

Problem: The code for printing to console works fine but when I want to send output to array it is printing the same (non-combination) row throughout. Suggestions on how to correct this and also any hints on how to use a STL container for this task would be most welcome

Code:

Code:

#include <iostream>#include <algorithm>
#include <vector>


using std::cin; using std::cout; using std::endl; using std::vector;using std::prev_permutation; 
int NchooseR( int n, int r ); // returns the number of possible combinations; 
void print_combos(int(**result), int x, int r); // intended to print the 2D array of possible combinations; 


int main(){
    int n, r;
    cin >> n >> r;
    int x = NchooseR(n,r);
   
    int ** result = new int*[x];// allocates memory for each row starting from the first element, number of rows equal to x = NchooseR(n,r);
    for (int i = 0; i < x; i++) {
     result [i] = new int[r]; // for each row starting from its first element, allocates memory according to the size of cols = r; 
    }


   vector<bool> v(n);
   fill(v.begin(), v.end() - n + r, true);
   
   do {
       for (int i = 0; i < n; ++i) {
           if (v[i]) { // to print to console the equivalent code here is {cout << (i+1) << " ";} and it works fine; 
               for (int j = 0; j < x; j++){
                   for (int t = 0; t < r; t++){
                       *(result[j]+t)=(i+1);
                   }
               }
            }
       }
    } while (prev_permutation(v.begin(), v.end()));//this creates a "selection array" (v), where we place r selectors, then we create all permutations
                    // of these selectors, and print the corresponding set member if it is selected in the current permutation of v
    
    for (int i = 0; i < x; i++){
    print_combos(&result[i], 1, r);    // each pointer to pointer is a pointer to the first element of each row  
                                            // which is itself a pointer; the matrix is printed one row at a time;
    }
    for (int i = 0; i < x; i++) {    // freeing allocated memory of result;
           delete [] result[i]    ;
      }                                     
    delete [] result;            
}


int NchooseR( int n, int r ){
    if (r > n) return 0;
    if (r * 2 > n) r = n-r;
    if (r == 0) return 1;


    int result = n;
    for( int i = 2; i <= r; ++i ) {
        result *= (n-i+1);
        result /= i;
    }
    return result;
}
void print_combos(int(**result), int x, int r){
    for (int i = 0; i < x; i++) {
        for (int j = 0; j < r; j++)
        {
            cout<< *(result[i]+j);
        }
        cout<<endl;
    }
}

Thank you

PS: Full disclosure - the print-to-console version of the code comes from the following link and it's also niggling me whether I've misunderstood it completely vis-a-vis trying to extend it to send output to array: http://stackoverflow.com/questions/9...binations-in-c

I think you are better off using a one-dimensional vector (called p from now on) and pushing back i + 1 where v[i] is set.

When you need to access the selected combinations you can use p[i * r + j], where i < x, x == NchooseR(n, r) and j < r. This enables you to use a inner loop and outer loop like a 2D array structure without all the confusion you are apparently having.

Code:

void print_combos(vector<int>& p, int n, int r)
{
   int x = NchooseR(n, r);
   for (int i = 0; i < x; i++) {
      for (int j = 0; j < r; j++) {
         cout << p[i * r + j] << " ";
      }
      cout << endl;
   }
}

I wasn't trying to say that the print function was the problem. These were my instructions on making p:

I think you are better off using a one-dimensional vector (called p from now on) and pushing back i + 1 where v[i] is set.

I do not know how suggesting that you use a one-dimensional vector translates into "a vector of sets" like you thought I said.

These were my instructions on using p:

When you need to access the selected combinations you can use p[i * r + j], where i < x, x == NchooseR(n, r) and j < r. This enables you to use a inner loop and outer loop like a 2D array structure without all the confusion you are apparently having.

Then I gave you a concrete example of use, using the print_combos function.

I feel like you weren't listening to me. It is very unfortunate that you weren't able to use my advice.

There is yet another way to make the results matrix that works like this:

Code:

#include <iostream>
#include <algorithm>
#include <vector>


using namespace std;
// the entire program uses std components, no use listing all of the ones we use


int NchooseR( int n, int r );
void print_combos(int(**result), int x, int r);


int main() {
    int n = 4, r = 2;


    std::vector<bool> v(n);
    std::fill(v.begin() + n - r, v.end(), true);
    
    int x = NchooseR(n, r);
    int **result = new int*[x];
    for (int k = 0; k < x; ++k) {
        result[k] = new int[r];
    }


    int j = 0, k = 0;
    do {
        for (int i = 0; i < n; ++i) {
            if (v[i]) {
                result[j][k++] = i + 1; 
                // why you insist on using the more complicated *(result[j]+k) i will never know
            }
        }
        k = 0, ++j;
    } while (next_permutation(v.begin(), v.end()));
    
    print_combos(result, x, r);


    for (int k = 0; k < x; ++k) {
        delete[] result[k];
    }
    delete[] result;
    return 0;
}


int NchooseR( int n, int r ){
    if (r > n) return 0;
    if (r * 2 > n) r = n-r;
    if (r == 0) return 1;
    int result = n;
    for( int i = 2; i <= r; ++i ) {
        result *= (n-i+1);
        result /= i;
    }
    return result;
}


void print_combos(int(**result), int x, int r){
    for (int i = 0; i < x; i++) {
        for (int j = 0; j < r; j++)
        {
            cout<< result[i][j] << " ";
        }
        cout<<endl;
    }
}

If you ask me a flat array is just easier to manage.

Sorry, I'd conflated my OP request for hints about using STL container for this with part of the comments in #2 ".. where v[i] is set" to go down the set-vector/vector-set route. However the clincher in #4 is the astute reworking of the print-to-console code for the print-to-container case and I can't thank or commend you enough for this.

Based upon your direction, I've reworked the code to print to a vector of vector directly, instead of an array, so that we can use STL algorithms straight-off.

My final goal for nCr is n = 51 and c = 6 (which comes to 1.8 million+ combinations) followed by a random_shuffle() of the vector of vectors. Is there anything I can do to speed up the calculations from here on? Also, am I right in assuming that the memory management of the vector of vector and it's component vectors is handled automatically by the program or do I need to do something about that?

Once again, many many thanks for your help. Regards

Code:

#include <iostream>
#include <algorithm>
#include <vector>
#include <ctime>        // std::time
#include <cstdlib>      // std::rand, std::srand
using namespace std;
int NchooseR( int n, int r );
typedef vector<vector<int> > vecvec; 
void print_combos(vecvec result, int x, int r);


int main() {
    int n = 31, r = 3;
     int x = NchooseR(n, r);
     vector<bool> v(n);
    fill(v.begin() + n - r, v.end(), true);
     
  vecvec result(x,vector<int>(r));
     int j = 0, k = 0;
    do {
        for (int i = 0; i < n; ++i) {
            if (v[i]) {
                result[j][k++] = i + 1; 
             }
        }
        k = 0, ++j;
    } while (next_permutation(v.begin(), v.end()));
     
   print_combos(result, x, r);
   
   cout<<endl<<endl;
 
srand(time(NULL));
random_shuffle(result.begin(),result.end());


    for (int j = 0; j < r; j++){
        cout<<result[0][j]<<"\t";
    }
}
int NchooseR( int n, int r ){
    if (r > n) return 0;
    if (r * 2 > n) r = n-r;
    if (r == 0) return 1;
    int result = n;
    for( int i = 2; i <= r; ++i ) {
        result *= (n-i+1);
        result /= i;
    }
    return result;
}
void print_combos(vecvec result, int x, int r){
    for (int i = 0; i < x; i++) {
        for (int j = 0; j < r; j++)
        {
            cout<< result[i][j] << " ";
        }
        cout<<endl;
    }
}