Suche algorithmus

zeusosc

Hi ich suche ein algorithmus für folgende permutationen:
(latex funktioniert hier leider net)
(1,3)=x_1*x_2*x_3
(2,3)=x_1*x_2 +x_1*x_3 + x_2*x_3
(3,3)=x_1+x_2+x_3

(1,4)=x_1*x_2*x_3*x_4
(2,4)=x_1*x_2*x_3 + x_1*x_2*x_4 + x_1*x_3*x_4 + x_2*x_3*x_4
(3,4)=x_1*x_2 + x_1*x_3 + x_2*x_3 + x_1*x_4 + x_2*x_4 + x_3*x_4
(4,4)=x_1 + x_2 + x_3 +x_4

Dabei ist die Anzahl der Summanden (binomial) j über i (endbinom) mit (i,j)=...

x_k ist eine double var.

Leider habe ich nur ansatzweise eine idee.
Gruß und dank

Werner Salomon

Vielleicht passt folgender rekursiver Algorithmus:

(n,n) = Summe x_i
(1,n) = Produkt x_i
(k,n) = (k-1,n-1) + x_n * (k,n-1) ; für 1 < k < n

das sollte recht einfach zu programmieren sein (nutze accumulate und multiplies<double>). Falls Du Probleme hast, frag' nochmal nach.

Gruß
Werner

zeusosc

Jo nette idee,
für die i=1,..,3,j=3 klappts,... (aufm pappier),
ich versuche es mal umzusetzen,..
ich melde mich nachher nochmal,
thx

zeusosc

Hi hier die ausgabe (symbolic):

(x1*x2*x3)
((x1*x2) + x3*(x1 + x2))
(x1 + x2 + x3)
(x1*x2*x3x4)
((x1*x2*x3) + x4((x1*x2) + x3*(x1 + x2)))
(((x1*x2) + x3*(x1 + x2)) + x4*(x1 + x2 + x3))
(x1 + x2 + x3 + x4)
Drücken Sie eine beliebige Taste . . .

Und hier der Code:

#include <cstdlib>
#include <iostream>
#include <string>
using namespace std;
string test(int i, int j, string *test_array)
{
string ret="(";

if(i==j){
         for(int k=0;k<i;k++)
         {
          if(k==0){ret+=test_array[k];}
          else{ret+=" + ";ret+=test_array[k];};
         };
          ret+=")";return ret;
}

if(i==1){
         for(int k=0;k<j;k++)
         {
          if(k==0){ret+=test_array[k];}
          else{ret+="*";ret+=test_array[k];};
         };
         ret+=")";return ret;
}

//(k,n)=(k-1,n-1)+x_n*(k,n-1)

ret+=test(i-1,j-1,test_array);
ret+=" + ";
ret+= test_array[j-1];
ret+="*";
ret+=test(i,j-1,test_array);
ret+=")";
return ret;
};

int main(int argc, char *argv[])
{
    string *test_array;
    test_array= new string[4];
    test_array[0]="x1";
    test_array[1]="x2";
    test_array[2]="x3";
    test_array[3]="x4";
    cout<<endl<<test(1,3,test_array);
    cout<<endl<<test(2,3,test_array);
    cout<<endl<<test(3,3,test_array);

    cout<<endl<<test(1,4,test_array);
    cout<<endl<<test(2,4,test_array);
    cout<<endl<<test(3,4,test_array);
    cout<<endl<<test(4,4,test_array);

    cout<<endl;
    system("PAUSE");
    return EXIT_SUCCESS;
}

danke vielmals

Werner Salomon

Das ist ein interessantes Problem.

Ich schlage folgende Implementierung vor:

#include <functional> // multiplies
#include <numeric> // accumulate
#include <iterator> // distance

template< typename InItr, typename Sz, typename T >
T algoX( InItr first, InItr last, Sz k, T sum )
{
    assert( 1 <= k );
    assert( k <= std::distance( first, last ) );
    if( k == 1 )
        return std::accumulate( first, last, T(1), std::multiplies< T >() ) + sum;
    if( k == std::distance( first, last ) )
        return std::accumulate( first, last, sum );

    --last;
    return algoX( first, last, k-1, *last * algoX( first, last, k, T(0) ) + sum );
}

Die Template-Lösung hat den Vorteil, dass man auch 'Strings' addieren kann, genau wie Du es gemacht hast, nur geht der algo natürlich für Zahlen (double) genauso. Mit einem Zahl-String

#include <cassert>
#include <iostream>
#include <string>
#include <boost/operators.hpp>

struct Z : public boost::addable< Z, boost::multipliable< Z > >
{
    Z() : m_x() {}
    explicit Z( int n ) 
        : m_x( n == 0? "": "1" ) 
    { 
        assert( n <= 1 ); 
    }
    Z( const std::string& x ) : m_x( x ) {}
    Z& operator+=( const Z& b )
    {
        if( m_x.empty() )
            m_x = b.m_x;
        else if( !b.m_x.empty() )
            m_x = "(" + m_x + "+" + b.m_x + ")";
        return *this;
    }
    Z& operator*=( const Z& b )
    {
        assert( !m_x.empty() );
        assert( !b.m_x.empty() );
        if( m_x == "1" )
            m_x = b.m_x;
        else if( b.m_x != "1" )
            m_x += "*" + b.m_x;
        return *this;
    }

    friend std::ostream& operator<<( std::ostream& out, const Z& z )
    {
        return out << z.m_x;
    }
private:
    std::string m_x;
};

und einem kleinen Programm

int main()
{
    using namespace std;
    const Z x_i[] = { "x_1", "x_2", "x_3", "x_4" }; // n == 4
    const int n = sizeof(x_i)/sizeof(*x_i);
    for( int i = 1; i <= n; ++i )
        cout << "(" << i << "," << n << ") = " << algoX( x_i, x_i + n, i, Z() ) << endl;
    return 0;
}

erhält man dann diese Ausgabe:

(1,4) = x_1*x_2*x_3*x_4
(2,4) = (x_1*x_2*x_3+x_4*(x_1*x_2+x_3*(x_1+x_2)))
(3,4) = (x_1*x_2+(x_3*(x_1+x_2)+x_4*((x_1+x_2)+x_3)))
(4,4) = (((x_1+x_2)+x_3)+x_4)

Wenn man Zeile 4 durch

const double x_i[] = { 1., 2., 3., 4. }; // n == 4

ersetzt und den Startwert in Zeile 7 mit 0.0 statt Z(), sollte es auch funktionieren.
Gruß
Werner

zeusosc

Cool, danke vielmals