Combinations/permutations algorithm in C++

Discussion in 'C++' started by jose luis fernandez diaz, Apr 13, 2004.

  1. 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.
    jose luis fernandez diaz, Apr 13, 2004
    #1
    1. Advertising

  2. jose luis fernandez diaz

    Leor Zolman Guest

    On 13 Apr 2004 03:44:18 -0700, (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
    Leor Zolman, Apr 13, 2004
    #2
    1. Advertising

  3. jose luis fernandez diaz

    Alex Vinokur Guest

    "jose luis fernandez diaz" <> wrote in message
    news:...
    > 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 news://news.individual.net/c5go0v$u6c$
    or
    news://news.wplus.net/c5go0v$u6c$
    via NNTP server>

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


    --
    Alex Vinokur
    mailto:
    http://mathforum.org/library/view/10978.html
    Alex Vinokur, Apr 13, 2004
    #3
  4. "jose luis fernandez diaz" <> wrote in
    message news:...
    > 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
    Ioannis Vranos, Apr 13, 2004
    #4
  5. 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
    Bernd Strieder, Apr 13, 2004
    #5
  6. You are right. Your solution is simple, elegant and smart.

    Regards,
    Jose Luis.

    Leor Zolman <> wrote in message news:<>...
    > On 13 Apr 2004 03:44:18 -0700, (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
    jose luis fernandez diaz, Apr 13, 2004
    #6
  7. jose luis fernandez diaz

    Leor Zolman Guest

    On 13 Apr 2004 10:42:16 -0700, (jose luis
    fernandez diaz) wrote:

    >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

    --
    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
    Leor Zolman, Apr 13, 2004
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Alex Vinokur
    Replies:
    2
    Views:
    2,781
    Alex Vinokur
    May 13, 2004
  2. Jeff Kish

    permutations and combinations

    Jeff Kish, Mar 7, 2005, in forum: C++
    Replies:
    9
    Views:
    2,265
    DHOLLINGSWORTH2
    Mar 11, 2005
  3. Replies:
    6
    Views:
    444
  4. Seth Leija

    Combinations or Permutations

    Seth Leija, Sep 20, 2010, in forum: Python
    Replies:
    4
    Views:
    262
    Raymond Hettinger
    Sep 21, 2010
  5. Peter Ensch
    Replies:
    5
    Views:
    196
Loading...

Share This Page