Combination of set of numbers

[zeroblank]

i have 2 numbers x and y
x=10
y=01
how can i generate all combination of these two numbers in six fields
ex. xxxxxx,xxxxxy,xxxxyx,xxxxyy,....etc so on so forth ?

[lastchance]

One option is to do it recursively.

Say:
vector<string> generate ( N )
where if N is 1 this just has 2 elements "x" and "y", and if N is greater than 1 it calls the function for N-1 elements and, for each, concatenates x or y.

It would make sense to test it with a number less than 6 to start with.

[zeroblank]

hmm .. i had an algorithmic way to solve it out {permutation over generated possible number of Xs and Ys in each set} but it would have taken me so much time to write it it and organize it .. so i used Linux to generate x and y in 6 field using the crunch command then inserting them into c++ ... replacing each x with 10 and y with 01

[lastchance]

Ah well! Here is the code that I wrote before making the suggestion. I doubt that it's very efficient, but it has, at least, the benefit of being mercifully short.

For your case, enter 6 when prompted for N. (Or try different values for different field widths.) Obviously, you can change "x" and "y" to any other elements or sequences that you want to permute.

#include <iostream>
#include <vector>
#include <string>
using namespace std;


vector<string> generate( int n )
{
   vector <string> v;
   if ( n == 1 )
   {
      v.push_back( "x" );
      v.push_back( "y" );
   }
   else
   {
      vector<string> w = generate( n - 1 );
      for ( int i = 0; i < w.size(); i++ )
      {
         v.push_back( w[i] + "x" );
         v.push_back( w[i] + "y" );
      }
   }
   return v;
}



int main()
{
   int N;
   cout << "Input N: ";   cin >> N;
   vector<string> v = generate( N );
   for ( int i = 0; i < v.size(); i++ ) cout << v[i] << endl;
}

[zeroblank]

i would really appreciate it if u had a link to a page or a book that fully covers how recursion works ... and some problems over it would be lovely <3

[Tenma]

http://www.learncpp.com/cpp-tutorial/7-11-recursion/

[lastchance]

i would really appreciate it if u had a link to a page or a book that fully covers how recursion works ... and some
problems over it would be lovely

"Recursion" just means a function calling itself, usually with (as here) a smaller parameter, so that (a) the problem gets "smaller" and (b) eventually "stops"!

The classic example is the factorial function: factorial(N) = N x (N-1) x (N-2) x ... x 2 x 1
which can be written as factorial(N) = N x factorial(N-1)
Eventually you will get down to factorial(1), which is just 1. So your function often has the form:
if (bottom number)
// set value for bottom number
else
// call same function with a smaller parameter

My program is of this type. It is quite common. If you want a problem to start with, I would try coding factorial(N). Another good problem is factoring into primes: once you have extracted one prime factor the other factor will be smaller than the original number, so recursion must eventually produce the whole prime factorisation - often, conveniently, in ascending order.


Recursion can also be used for mathematical problems that can be solved by iteration or proved by induction - you may be familiar with these techniques.

[JLBorges]

Since there are only two possible values for each field, a particular arrangement can be represented as a distinct sequence of bits; as a distinct unsigned integer value.

Spoiler: http://coliru.stacked-crooked.com/a/77127825cd3a1d9f

[lastchance]

Hmmm

Or one could extend the function to more than two possible values for each field ... NOT to be used for nefarious purposes!

#include <iostream>
#include <vector>
#include <string>
using namespace std;


vector<string> generate( int n, string X[], int nx )                 // generate arrangements in width n
{
   unsigned int i, j;
   vector <string> v;

   if ( n == 1 )
   {
      for ( i = 0; i < nx; i++ ) v.push_back( X[i] );
   }
   else
   {
      vector<string> w = generate( n - 1, X, nx );
      for ( j = 0; j < w.size(); j++ )
      {
         for ( i = 0; i < nx; i++ ) v.push_back( w[j] + X[i] );
      }
   }
   return v;
}


int main()
{
   unsigned int N, i;
   const int NUMX = 3; string X[NUMX] = { "x", "y", "z" };           // possible strings - put in what you like

   cout << "Input N: ";   cin >> N;
   vector<string> v = generate( N, X, NUMX );
   for ( i = 0; i < v.size(); i++ ) cout << v[i] << endl;
}

[zeroblank]

thanks a lot last chance for the easy to understand code ^^ and explanation that helped a lot

thanks Tenma for the link

JLBorges Cool man , i think i still have lots of things ahead of me to learn :) .. thnx for sharing the code

[JLBorges]

If there are n possible values for each field,
each arrangement can be represented as a distinct sequence of n-ary digits (digits in a system with radix n);
as a distinct unsigned integer value.

#include <iostream>
#include <initializer_list>
#include <iomanip>

template < typename T > void print_flds( unsigned long long n, std::initializer_list<T> ilist, std::size_t nflds )
{
    std::cout << std::setw(5) << n+1 << ". " ;

    const std::size_t radix = ilist.size() ;
    for( std::size_t i = 0 ; i < nflds ; ++i )
    {
        std::cout << ilist.begin()[n%radix] ;
        n /= radix ;
    }
    std::cout << '\n' ;
}

template < typename T > void print_all( std::initializer_list<T> ilist, std::size_t nflds )
{
    const std::size_t radix = ilist.size() ;
    unsigned long long ubound = 1 ;
    for( std::size_t i = 0 ; i < nflds ; ++i ) ubound *= radix ;

    for( unsigned long long n = 0 ; n < ubound ; ++n ) print_flds( n, ilist, nflds ) ;
}

int main()
{
    print_all( { "red   ", "green ", "blue  " }, 4 ) ;
}

http://coliru.stacked-crooked.com/a/2a5fc1bceba4f1f7