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]

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

 

[Alex Vinokur]

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);
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.begin(), res1_vect.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 or
via NNTP server>

 

[Ioannis Vranos]

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,

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

 

[jose luis fernandez diaz]

You are right. Your solution is simple, elegant and smart.

Regards,
Jose Luis.

 

[Leor Zolman]

You are right. Your solution is simple, elegant and smart.

Thanks. I did overlook one simple fact that Bernd got right in his post:
the generic template definition can be omitted, yielding the compile-time
diagnostic I was pining for (sans the custom wording of my run-time error
message, for sure, but that's no great loss) without requiring any fancy
library support whatsoever. I.e., we no longer need the RTTI header:

template<typename T>
double toDouble(const T &t);

-leor