Combinations/permutations algorithm in C++

[jose luis fernandez diaz]

Hi,

I want to write a function of four parameters. Each parameter can be
of type long, double or string. For example:

f(long, long, long, long);
f(long, long, long, double);
f(long, long, long, const string &);
f(long, long, double, long);
f(long, long, string, long);
f(long, long, double, double);
f(long, long, double, string);
f(long, long, string, long);

. . .

I would like write this code automaticaly. I know the next_permutation
STL algorithm, but I think that it is not useful in this case.

Any idea ?

Thanks,
Jose Luis.

[Leor Zolman]

On 13 Apr 2004 03:44:18 -0700, jo**********************@yahoo.es (jose luis
fernandez diaz) wrote:

Hi,

I want to write a function of four parameters. Each parameter can be
of type long, double or string. For example:

f(long, long, long, long);
f(long, long, long, double);
f(long, long, long, const string &);
f(long, long, double, long);
f(long, long, string, long);
f(long, long, double, double);
f(long, long, double, string);
f(long, long, string, long);

. . .

I would like write this code automaticaly. I know the next_permutation
STL algorithm, but I think that it is not useful in this case.

Any idea ?

Sounds like you're thinking in terms of applying an STL algorithm to the
process of /code generation/, as in having something create the source code
for all those functions for you, with the right adjustments for the
different parameter ordering?

I suppose it might be possible to do something in terms of writing a C++
program that uses next_permutation for something like that, but I'm not
sure that's your best solution.

When I looked at your problem, I asked myself "What does he /do/ in those
functions"? IOW, are you converting all the arguments to a single
"standard" type for use within the function? If you are, and that type is
the same across all the functions (say, double in order to be able to
represent all the possible "values" supplied as arguments, more or less),
then you can do something like this with templates:

#include <iostream>
#include <string>
#include <typeinfo>
#include <cstdlib>
using namespace std;

template<typename T>
double toDouble(const T &t)
{
cerr << "Invalid type supplied to toDouble: " <<
typeid(t).name() << endl;
return 99999.9999; // I did this as a quick-and-dirty /
// example, but it would be much better to
// do something different with compile-time
// assertions
}

template<>
inline double toDouble(const double &d) { return d; }

template<>
inline double toDouble(const long &d) { return d; }

template<>
inline double toDouble(const std::string &d)
{ return std::atof(d.c_str()); }

// and so on, for each type you wish to support...

// This version of f just returns the sum, as a double:
template<typename T1, typename T2, typename T3, typename T4>
double f(T1 v1, T2 v2, T3 v3, T4 v4)
{
return toDouble(v1) + toDouble(v2) + toDouble(v3) + toDouble(v4);
}
int main()
{
cout << f(1L,2L,3L,4L) << endl << endl;
cout << f(1.0,2L,3L,string("4.5")) << endl << endl;
cout << f(1.5,2L,3,string("4.5")) << endl << endl;
cout << f('a', 2L, 35.7, 4.3) << endl << endl;
cout << f("abc", 2L, 3.5f, 45.5) << endl << endl;
return 0;
}
Output:
10

10.5

Invalid type supplied to toDouble: int
100008

Invalid type supplied to toDouble: char
100042

Invalid type supplied to toDouble: const char *
Invalid type supplied to toDouble: float
200047
-leor

--
Leor Zolman --- BD Software --- www.bdsoft.com
On-Site Training in C/C++, Java, Perl and Unix
C++ users: download BD Software's free STL Error Message Decryptor at:
www.bdsoft.com/tools/stlfilt.html

[Alex Vinokur]

"jose luis fernandez diaz" <jo**********************@yahoo.es> wrote in message
news:c2**************************@posting.google.c om...

Hi,

I want to write a function of four parameters. Each parameter can be
of type long, double or string. For example:

f(long, long, long, long);
f(long, long, long, double);
f(long, long, long, const string &);
f(long, long, double, long);
f(long, long, string, long);
f(long, long, double, double);
f(long, long, double, string);
f(long, long, string, long);

. . .

I would like write this code automaticaly. I know the next_permutation
STL algorithm, but I think that it is not useful in this case.

Any idea ?

Thanks,
Jose Luis.

Something like this : (?)

--------- permut.cpp ---------
#include <cassert>
#include <string>
#include <vector>
#include <iostream>
#include <sstream>
#include <iterator>
using namespace std;

template<typename T>
vector<vector<T> > get_permut (size_t n, const vector<T>& abt_i)
{
vector<vector<T> > ret_vect;

if (n > 1)
{
vector<vector<T> > prev_vect (get_permut (n - 1, abt_i));
for (size_t i = 0; i < prev_vect.size(); i++)
{
for (size_t j = 0; j < abt_i.size(); j++)
{
vector<T> tmp_vect (prev_vect[i]);
tmp_vect.push_back (abt_i[j]);
ret_vect.push_back (tmp_vect);
}
}
}
else
{
for (size_t j = 0; j < abt_i.size(); j++)
{
vector<T> tmp_vect (1, abt_i[j]);
ret_vect.push_back (tmp_vect);
}
}

return ret_vect;
}
int main (int argc, char** argv)
{
const bool condition_argc = (argc == 2);
if (!condition_argc)
{
cout << endl
<< " USAGE : "
<< argv[0]
<< " <size of permutation>"
<< endl;
return 1;
}

assert (condition_argc);

vector<string> abt1;
abt1.push_back ("long");
abt1.push_back ("double");
abt1.push_back ("string");
abt1.push_back ("const string&");
vector<vector<string> > res1_vect (get_permut (atoi(argv[1]), abt1));
for (size_t i = 0; i < res1_vect.size(); i++)
{
ostringstream oss;
copy (res1_vect[i].begin(), res1_vect[i].end(), ostream_iterator<string>(oss, ", "));
cout << "f(" << oss.str().substr (0, oss.str().size() - 2) << ");" << endl;
}

return 0;
}

------------------------------

--------- Compilation & Run ---------

$ g++ permut.cpp

$ a
USAGE : a <size of permutation>

$ a 4
<See news://news.individual.net/c5**********@news.wplus.net
or
news://news.wplus.net/c5**********@news.wplus.net
via NNTP server>

-------------------------------------
--
Alex Vinokur
mailto:al****@connect.to
http://mathforum.org/library/view/10978.html

[Ioannis Vranos]

"jose luis fernandez diaz" <jo**********************@yahoo.es> wrote in
message news:c2**************************@posting.google.c om...

Hi,

I want to write a function of four parameters. Each parameter can be
of type long, double or string. For example:

f(long, long, long, long);
f(long, long, long, double);
f(long, long, long, const string &);
f(long, long, double, long);
f(long, long, string, long);
f(long, long, double, double);
f(long, long, double, string);
f(long, long, string, long);

. . .

I would like write this code automaticaly. I know the next_permutation
STL algorithm, but I think that it is not useful in this case.

Any idea ?

template<class A, class B, class C, class D>
void f(A a, B b, C c, D d)
{
// ...
}
template<>
void f(long a, long b, long c, const string &d)
{
// ...
}


Ioannis Vranos

[Bernd Strieder]

Hello,

jose luis fernandez diaz wrote:

I want to write a function of four parameters. Each parameter can be
of type long, double or string. For example:

Let the compiler generate it for you on the fly via templates. This
looks a bit complicated at first, but templates are invaluable to get
the desired effect of compile-time polymorphism.

// handling parameter 1

template <class T>
handle_param_1 (T); // default, may not be used

template <>
handle_param_1 (long l)
{
// what to do, when parameter 1 is long
}

template <>
handle_param_1 (double d)
{
// what to do, when parameter 1 is double
}

// handling parameter 2

template <class T>
handle_param_2 (T); // default, may not be used

template <>
handle_param_2 (long l)
{
// what to do, when parameter 2 is long
}

template <>
handle_param_2 (double d)
{
// what to do, when parameter 2 is double
}

// handling more parameters same way

// ...

template <class P1, class P2>
void f(P1 p1, P2 p2)
{
handle_param_1(p1);
handle_param_2(p2);
}

// Now f(long,double), f(long,long), f(double,long), f(double,double),
// all have a defined meaning

If you want to learn more about C++ templates, consider the book about
templates from Vandewoorde and Josuttis.

Bernd Strieder