Sortieren !!

--Neo--

Hi,
ich suche einen kleine Algorithmus, wie ich ein Feld von mehreren Objekten sortieren kann!
Es handelt sich hierbei um Zahlen von 1 bis 3 die je nachdem welche Zahl folgt einen anderen Wert haben!

Beispiel:

3 2 1 = Summe ist 284

1 2 3 = Summe ist 160

Ich möchte jetzt diese Zahlenreihe so sortieren, daß die Summe minimal wird !!

Um Hilfe wäre ich sehr dankbar!

mfg
Neo

CStoll

Wonach berechnet sich denn die "Summe" so einer Reihe? Eventuell kann man anhand der Berechnungsvorschrift ja bereits ablesen, welche Reihenfolge die beste sein könnte. Andernfalls mußt du per next_permutation() alle Varianten durchtesten und miteinander vergleichen.

--Neo--

Also die Variablen orientieren sich an Standartwerten.
Ich liste hier mal alle Möglichkeiten auf!
Ziel ist es die Gesamtsumme zu minimieren!

Folgt auf 1 eine 2 ist die Summe 82
auf 2 eine 1 = 146
auf 3 eine 1 = 167
auf 1 eine 3 = 78
auf 3 eine 2 = 138
auf 2 eine 3 = 78
auf 1 eine 1 = 82
auf 2 eine 2 = 82
auf 3 eine 3 = 167

Ziel ist es ein Feld von 10 Zahlen zufälliger Reihenfolge so zu sortieren, daß die Summe minimal wird!

Beispiel mit einem Feld mit 3 Zahlen:

der Generator gibt 3 1 2 aus
jetzt soll sortiert werden so das die Summe minimal wird:

bei 3 1 2 = 249
bei 1 3 2 = 216
bei 3 2 1 = 284
bei 1 2 3 = 160
bei 2 1 3 = 224
bei 2 3 1 = 245

das Ergebnis wäre also 160, d.h 1 2 3 wäre die gesuchte Reihenfolge
und das soll jetzt automatisch gehen
Die Zahlen können natürlich auch mehrmals vorkommen!!

Danke für die Mühe

--Neo--

Hmm kann mir denn hier keiner weiterhelfen ??

Ich muß den Kram in 2 Tagen abgeben!
Also ich zähl auf euch!

Gruß Neo

Werner Salomon

weil's schon so spät ist - ohne Kommentar:

#include <algorithm>    // copy
#include <functional>   // plus<>
#include <iostream>
#include <iterator>     // ostream_iterator
#include <numeric>      // inner_product
#include <vector>

int bestimmeWert( int i1, int i2 )
{
    const int N = 4;
    switch( i1 * N + i2 )
    {
    case 1 * N + 1: return 82;
    case 1 * N + 2: return 82;
    case 1 * N + 3: return 78;
    case 2 * N + 1: return 146;
    case 2 * N + 2: return 82;
    case 2 * N + 3: return 78;
    case 3 * N + 1: return 167;
    case 3 * N + 2: return 138;
    case 3 * N + 3: return 167;
    }
    return 0;
}

int main()
{
    using namespace std;
    vector< int > v(3);
    v[0] = 1; v[1] = 2; v[2] = 3; // ! muss sortiert sein
    vector< int > maxV;
    int wert = 0;
    bool first = true;
    do
    {
        int w = inner_product( v.begin(), v.end()-1, v.begin() + 1, 0, std::plus< int >(), &bestimmeWert );
        if( first || w < wert )
        {
            maxV = v;
            wert = w;
        }
        first = false;
    } while( next_permutation( v.begin(), v.end() ) );

    cout << "Reihenfolge mit minimaler Summe: ";
    copy( maxV.begin(), maxV.end(), ostream_iterator< int >( cout, " " ) );
    cout << "= " << wert << endl;
    return 0;
}

Gruß
Werner

--Neo--

Danke für die Mühe, aber so ganz verstehe ich es nicht!
Wäre nett, wenn du bei Gelegenheit doch noch ein paar Kommentare hinzufügen könntest!

mfg
Neo

--Neo--

// Optimierung Landereihenfolge

#include<iostream.h>
#include<math.h>
#include<ctype.h>
#include<conio.h>
#include<iomanip.h>
#include<stdlib.h>

int main(void)
{
  const max = 10;
  int flieger [max];
  int i, Summe1;
  randomize();

  cout << "Es wird jetzt eine zufällige Reihenfolge von Maschinen generiert :  "      
  << endl;
  cout << endl;
  cout << "1 = Light" << endl;
  cout << "2 = Medium" << endl;
  cout << "3 = Heavy" << endl;
  cout << endl;
  cout << endl;

    for (i=0; i <= max; i++)
        {
        flieger [i] = random (3)+1;
        }

  cout << "Reihenfolge: " << endl;

  Summe1 = 0;
  Summe2 = 0;

    for (i=0; i <= max; i++)
        {
        cout << flieger [i];
        }

    for (i=0; i <= max; i++)
    {

        if (flieger [i] == 1 && flieger [i+1] == 2)
            {
              Summe1 = Summe1 + 82;
            }
        else if (flieger [i] == 2 && flieger [i+1] == 1)
            {
              Summe1 = Summe1 + 146;
            }
        else if (flieger [i] == 3 && flieger [i+1] == 1)
            {
              Summe1 = Summe1 + 167;
            }
        else if (flieger [i] == 1 && flieger [i+1] == 3)
            {
              Summe1 = Summe1 + 78;
            }
        else if (flieger [i] == 3 && flieger [i+1] == 2)
            {
              Summe1 = Summe1 + 138;
            }
        else if (flieger [i] == 2 && flieger [i+1] == 3)
            {
              Summe1 = Summe1 + 78;
            }
        else if (flieger [i] == 1 && flieger [i+1] == 1)
            {
              Summe1 = Summe1 + 82;
            }
        else if (flieger [i] == 2 && flieger [i+1] == 2)
            {
              Summe1 = Summe1 + 82;
            }
        else if (flieger [i] == 3 && flieger [i+1] == 3)
            {
              Summe1 = Summe1 + 167;
            }

        }
        cout << endl;
        cout << endl;
        cout << "Die Summe1 ist:  " << Summe1 << "sec" <<endl;
        cout << "Die Summe1 ist:  " << Summe1/60 << "min" <<endl;

getch();
return 0;
}

Soweit bin ich bis jetzt, daß er mir eine zufälliges Feld mit 10 Zahlen generiert und dann die Summe ausrechnet!
Jetzt müßte man das obere Sortierverfahren noch integrieren, aber da bin ich wohl etwas überfordert...

Neo

//Code tags...

CStoll

Die Grundidee hatte ich schon in meinem Programm erklärt: Du mußt alle Permutationen deiner Zahlenfolge durchlaufen und ihren Wert vergleichen:

vector<int> reihe;                 //gefüllt mit Werten
vector<int> optimum;               //hierher kopieren wir die optimale Reihe
int opt_sum=numeric_limits<int>::max();
sort(reihe.begin(),reihe.end());   //wir beginnen mit geordneter Reihenfolge

do
{
  int sum=summe(reihe);            //in der Funktion "summe" darfst du dich austoben und den "Wert" der aktuellen Reihe bestimmen
  if(sum<opt_sum)
  {
    opt_sum=sum;
    optimum=reihe;
  }
}
while(next_permutation(reihe.begin(),reihe.end());
//next_permutation() ordnet die Elemente zur nächstgrößeren Permutation um und gibt false zurück, wenn es "überläuft"
//(deshalb muß reihe auch vor dem Start sortiert werden)

--Neo--

Danke Werner für die Mühe!
Er zeigt aber in der 3.letzten Zeile noch nen Fehler an (bei copy...)
Und wie integrier ich das am besten in mein vorhandenes Programm ??

Gruß

.filmor

Irgendwie sieht das geradezu erschreckend nach einem Graphenproblem aus. Wenn du mit Graphen umzugehen weist, dann könntest du das ganze auch mit der BGL implementieren.

Werner Salomon

--Neo-- schrieb:

... aber so ganz verstehe ich es nicht!

Wenn Du konkrete Fragen stellst, so kann man Dir auch konkrete Antworten geben.

--Neo-- schrieb:

Er zeigt aber in der 3.letzten Zeile noch nen Fehler an (bei copy...)

Welchen genau? Welchen Compiler und Entwicklungsumgebung benutzt Du?
Du kannst das copy auch wegleassen und das Ergebnis wie in Deinem Programm ausgeben.

--Neo-- schrieb:

Und wie integrier ich das am besten in mein vorhandenes Programm ??

Die Frage müßte doch lauten, wie integriert man Deinen Code?

CStoll hat Dir doch bereits den Weg gewiesen

CStoll schrieb:

vector<int> reihe;                 //gefüllt mit Werten

hier musst Du die Variable 'reihe' mit dem Füllen, was in 'flieger[]' drin steht. Bzw. besser reihe in 'flieger' umbenennen und so füllen wie in Deinem Programm.

CStoll schrieb:

int sum=summe(reihe);            //in der Funktion "summe" darfst du dich austoben und den "Wert" der aktuellen Reihe bestimmen

und in der Funktion 'summe' schreibst Du das rein, was in der Riesen-for-Schleife Deines Programms passiert.

Da sind übrigens noch ein paar Fehler drin:

--Neo-- schrieb:

for (i=0; i <= max; i++) // <- i < max; i läuft von 0 bis 9 macht 10 Flugzeuge
        {
        flieger [i] = random (3)+1;
        }
// ...
    for (i=0; i <= max; i++) // (s.o.)
        {
        cout << flieger [i];
        }
    for (i=0; i <= max; i++) // muss i < max-1 heißen, da innerhalb der Schleife auf i+1 zugegriffen wird
    {
        if (flieger [i] == 1 && flieger [i+1] == 2)
            {
              Summe1 = Summe1 + 82;
            }

--Neo-- schrieb:

Da ich mit Flugzeugklassen arbeite gibt es im Prinzip nur 3 verschiedene Flugzeugtypen: Heavy, Medium und Small !

Das Programm soll dann im Prinzip ein Feld generieren können mit einer bestimmten Zahl von Flugzeugen, so zwischen 10 und 200 vielleicht! Wieviele von jedem Typ is dabei willkürlich !
Für diese Menge soll dann die optimale Reihefolge bstimmt werden, also die minimale Zeit die sie benötigen um alle zu landen!
Ziel ist es also die Reihenfolge so zu verändern das die Summe der Zeit minimal wird!

hast Du Dir mal überlegt, wieviele Möglichkeiten es für 10 und 200 Flugzeuge gibt. Bei 10 können es 4200 Möglichkeiten werden und bei 200 sind es ca 10^333, wenn ich mich nicht vertan habe, also um viele Größenordnungen zuviel als dass man alle durchprobieren könnte. Wenn Du das mit den 200 ernst meinst, kannst Du das Verfahren, welches CStoll und ich Dir vorgeschlagen haben, vergessen.
Dann ist es eher ein Problem der diskreten Optimierung. Also liegt die Lösung eher im Bereich der Graphentheorie (s. filmor's Beitrag) bzw. genauer des TSP's.

Gruß
Werner

--Neo--

Hmm davon hab ich leider noch weniger ahnung als von vectoren

Werner Salomon

--Neo-- schrieb:

Hmm davon hab ich leider noch weniger ahnung als von vectoren

.. musst Du ja nicht. Die Aussage war lediglich: wenn 200 Flugzeuge, dann geht's so nicht.

Kommst Du ansonsten mit dem zurecht, was hier gepostet wurde?

--Neo--

Hi sorry aber ich bin ein ziemlicher Newbie in Sachen C++!
Ich werde mich morgen mal dransetzen und versuchen was damit auf die Beine zu stellen!
Mehr als 100 Flugzeuge sollen damit auch nicht optimiert werden!

Aber danke für die Mühe erstmal!
Bei Fragen meld ich mich nochmal!

gruß
Neo

--Neo--

Hi,
also ich wollte jetzt mal das Programm zusammenschreiben, aber ich weiß noch net so genau wie ich das arry Flieger in die reihe übergebe!
der zeigt mir immer ne fehlermeldung an!

Kann mir da einer von euch pros helfen ??

Gruß
Neo

LordJaxom

Kurze Antwort: Nein.

Lange Antwort: Wenn Du uns nen Stück Code und den Wortlaut der Fehlermeldung nicht gibst brauchen wir es eigentlich garnicht versuchen (wie oft eigentlich noch?)

--Neo--

Das hab ich hier stehen:

// Optimierung Landereihenfolge

#include<iostream.h>
#include<math.h>
#include<ctype.h>
#include<conio.h>
#include<iomanip.h>
#include<stdlib.h>
#include <vector>
#include <algorithm>
#include <functional>
#include <numeric>
#include <iterator>
#include <iostream>

int main(void)
{
const max = 10;
int flieger [max];
int i, Summe1;
randomize();
vector<int> reihe; //gefüllt mit Werten
vector<int> optimum; //hierher kopieren wir die optimale Reihe

cout << "Es wird jetzt eine zufällige Reihenfolge von Maschinen generiert : "
<< endl;
cout << endl;
cout << "1 = Light" << endl;
cout << "2 = Medium" << endl;
cout << "3 = Heavy" << endl;
cout << endl;
cout << endl;

for (i=0; i < max; i++)
{
flieger [i] = random (3)+1;
}

cout << "Reihenfolge: " << endl;

for (i=0; i < max; i++)
{
cout << flieger [i];
}

Summe1 = 0;

for (i=0; i < max-1; i++)
{

if (flieger [i] == 1 && flieger [i+1] == 2)
{
Summe1 = Summe1 + 82;
}
else if (flieger [i] == 2 && flieger [i+1] == 1)
{
Summe1 = Summe1 + 146;
}
else if (flieger [i] == 3 && flieger [i+1] == 1)
{
Summe1 = Summe1 + 167;
}
else if (flieger [i] == 1 && flieger [i+1] == 3)
{
Summe1 = Summe1 + 78;
}
else if (flieger [i] == 3 && flieger [i+1] == 2)
{
Summe1 = Summe1 + 138;
}
else if (flieger [i] == 2 && flieger [i+1] == 3)
{
Summe1 = Summe1 + 78;
}
else if (flieger [i] == 1 && flieger [i+1] == 1)
{
Summe1 = Summe1 + 82;
}
else if (flieger [i] == 2 && flieger [i+1] == 2)
{
Summe1 = Summe1 + 82;
}
else if (flieger [i] == 3 && flieger [i+1] == 3)
{
Summe1 = Summe1 + 167;
}

}
cout << endl;
cout << endl;
cout << "Die Summe1 ist: " << Summe1 << "sec" <<endl;
cout << "Die Summe1 ist: " << Summe1/60 << "min" <<endl;

Hier muß doch auch noch das Feld flieger [max] in "reihe" kopiert werden oder ? Und wie geht das ?

int opt_sum=numeric_limits<int>::max();
sort(reihe.begin(),reihe.end()); //wir beginnen mit geordneter Reihenfolge

do
{
int sum=Summe1; //in der Funktion "summe" darfst du dich austoben und den "Wert" der aktuellen Reihe bestimmen
if(sum<opt_sum)
{
opt_sum=sum;
optimum=reihe;
}
}
while(next_permutation(reihe.begin(),reihe.end());
//next_permutation() ordnet die Elemente zur nächstgrößeren Permutation um und gibt false zurück, wenn es "überläuft"
//(deshalb muß reihe auch vor dem Start sortiert werden)

getch();
return 0;
}

Folgende Fehlermeldung:
[C++Fehler] Sort_Funkt.cpp(115): Do-while statement missing ).

Und die Ausgabe fehlt halt noch! Das Problem is halt, daß ich etwas unter Zeitdruck stehe mit noch einer anderen Hausarbeit!
Ich entschuldige deshalb mein Verhalten in Sachen Angaben, aber mir fehlt halt einfach das Hintergrundwissen für C++!

Gruß Neo

LordJaxom

Naja "Do-While-Statement missing )" sollte man auch mit geringen Englischkenntnissen schaffen -> Im do-while-Statement fehlt eine schliessende Klammer (sieht man wenn man genau hinschaut auch).

Das Feld flieger in das Feld reihe kannst Du mit copy überführen:

copy(flieger, flieger + max, back_inserter(reihe));

Dann weiss ich nicht was opt_sum ist, glaube aber nicht dass Du darin den größten möglichen Integer-Wert den Dein System verarbeiten kann haben möchtest, oder? Denn das liefert numeric_limits<int>::max()

EDIT:
Und bitte, bitte stell Deinen Code in [ cpp] .... [ /cpp] Tags (ohne die Leerstellen nach der öffnenden Klammer)

--Neo--

// Optimierung Landereihenfolge

#include<iostream.h>
#include<math.h>
#include<ctype.h>
#include<conio.h>
#include<iomanip.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>
#include <iterator>

int GSumme (int i);
{
for (int i=0; i <= 9; i++)
{
if (reihe [i] == 1 && reihe [i+1] == 2)
{
Summe = Summe + 82;
}
else if (reihe [i] == 2 && reihe [i+1] == 1)
{
Summe = Summe + 146;
}
else if (reihe [i] == 3 && reihe [i+1] == 1)
{
Summe = Summe + 167;
}
else if (reihe [i] == 1 && reihe [i+1] == 3)
{
Summe = Summe + 78;
}
else if (reihe [i] == 3 && reihe [i+1] == 2)
{
Summe = Summe + 138;
}
else if (reihe [i] == 2 && reihe [i+1] == 3)
{
Summe = Summe + 78;
}
else if (reihe [i] == 1 && reihe [i+1] == 1)
{
Summe = Summe + 82;
}
else if (reihe [i] == 2 && reihe [i+1] == 2)
{
Summe = Summe + 82;
}
else if (reihe [i] == 3 && reihe [i+1] == 3)
{
Summe = Summe + 167;
}
}
return 0;
}

int main()
{
using namespace std;
vector<int> reihe(10);
vector<int> maxV;

for (int i=0; i <= 9; i++)
{
reihe [i] =random (3)+1;
}

cout <<reihe[0]<<" "<<reihe [1]<<" "<<reihe[2]<<" "<< reihe[3]<<" "<<reihe[4]<<" "<<reihe[5]<<" "<<reihe[6]<<" "<<reihe[7]<<" "<<reihe[8]<<" "<<reihe[9]<<" "<<endl;

int wert = 0;
bool first = true;
do
{
int w = inner_product( reihe.begin(), reihe.end()-1, reihe.begin() + 1, 0, std::plus< int >(),&GSumme );
if( first || w < wert )
{
maxV = reihe;
wert = w;
}
first = false;
}

while( next_permutation( reihe.begin(), reihe.end() ) );

cout << "Reihenfolge mit minimaler Summe: ";
std::copy( maxV.begin(), maxV.end(), std::ostream_iterator< int >(reihe) );
cout << "= " << wert << endl;

getch();
return 0;
}

Soweit bin ich jetzt gekommen, allerdings gibt es wohl noch ein Problem mit der Funktion!

Fehlermeldung:
[C++Fehler] Variante_1.cpp(15): Declaration terminated incorrectly.

Wäre schön, wenn nochmal einer von euch drübergucken könnte!

Danke
Neo

--Neo--

Also soweit bin ich jetzt!
Hab aber noch einen Fehler mit der Ausgabe bzw mit den Klammern und finde den Fehler einfach nicht. Wäre schön, wenn mir da einer helfen könnte!

// Optimierung Landereihenfolge

#include<iostream.h>
#include<math.h>
#include<ctype.h>
#include<conio.h>
#include<iomanip.h>
#include<stdlib.h>

int main(void)
{
  const max = 10;
  int flieger [max];
  int Bestfeld [max];
  int n, m, k;
  int j1, j2, j3, j4, j5, j6, j7, j8, j9, j10;
  int i, Summe, Bestzeit;

  cout << "Es wird jetzt eine Reihenfolge von Maschinen generiert und berechnet:  " << endl;
  cout << endl;
  cout << "1 = Light" << endl;
  cout << "2 = Medium" << endl;
  cout << "3 = Heavy" << endl;
  cout << endl;
  cout << endl;
  n=0;
  m=0;
  k=0;

    for (j1=1; j1 <=3; j1++)
        {
        flieger [1] = j1;
            if (j1=1) n++;
            if (j1=2) m++;
            if (j1=3) k++;
            for (j2=1; j2 <=3; j2++)
            {
            flieger [2] = j2;
                if (j2=1) n++;
                if (j2=2) m++;
                if (j3=3) k++;
                for (j3=1; j3 <=3; j3++)
                {
                flieger [3] = j3;
                    if (j3=1) n++;
                    if (j3=2) m++;
                    if (j3=3) k++;
                    for (j4=1; j4 <=3; j4++)
                    {
                    flieger [4] = j4;
                        if (j4=1) n++;
                        if (j4=2) m++;
                        if (j4=3) k++;
                        for (j5=1; j5 <=3; j5++)
                        {
                        flieger [5] = j5;
                            if (j5=1) n++;
                            if (j5=2) m++;
                            if (j5=3) k++;
                            for (j6=1; j6 <=3; j6++)
                            {
                            flieger [6] = j6;
                                if (j6=1) n++;
                                if (j6=2) m++;
                                if (j6=3) k++;
                                for (j7=1; j7 <=3; j7++)
                                {
                                flieger [7] = j7;
                                    if (j7=1) n++;
                                    if (j7=2) m++;
                                    if (j7=3) k++;
                                    for (j8=1; j8 <=3; j8++)
                                    {
                                    flieger [8] = j8;
                                        if (j8=1) n++;
                                        if (j8=2) m++;
                                        if (j8=3) k++;
                                        for (j9=1; j9 <=3; j9++)
                                        {
                                        flieger [9] = j9;
                                            if (j9=1) n++;
                                            if (j9=2) m++;
                                            if (j9=3) k++;
                                            for (j10=1; j10 <=3; j10++)
                                            {
                                            flieger [10] = j10;
                                                 if (j10=1) n++;
                                                 if (j10=2) m++;
                                                 if (j10=3) k++;
                                            if (((n==3) && (m==4)) && (k==3))
                                            {                                            {
                                            cout << "Test" << endl;
                                            Summe = 0;

                                            for (i=0; i <=9; i++)
                                                {
                                                if (flieger [i] == 1 && flieger [i+1] == 2)
                                                {
                                                    Summe = Summe + 82;
                                                }
                                                else if (flieger [i] == 2 && flieger [i+1] == 1)
                                                {
                                                     Summe = Summe + 146;
                                                }
                                                else if (flieger [i] == 3 && flieger [i+1] == 1)
                                                {
                                                      Summe = Summe + 167;
                                                }
                                                 else if (flieger [i] == 1 && flieger [i+1] == 3)
                                                  {
                                                      Summe = Summe + 78;
                                                  }
                                                  else if (flieger [i] == 3 && flieger [i+1] == 2)
                                                 {
                                                    Summe = Summe + 138;
                                                  }
                                                 else if (flieger [i] == 2 && flieger [i+1] == 3)
                                               {
                                                       Summe = Summe + 78;
                                                }
                                                  else if (flieger [i] == 1 && flieger [i+1] == 1)
                                                {
                                                        Summe = Summe + 82;
                                                   }
                                                    else if (flieger [i] == 2 && flieger [i+1] == 2)
                                                {
                                                       Summe = Summe + 82;
                                                 }
                                                 else if (flieger [i] == 3 && flieger [i+1] == 3)
                                                {
                                                         Summe = Summe + 167;
                                                 }
                                                }
                                                if (Summe < Bestzeit)
                                                {
                                                Bestzeit=Summe;
                                                Bestfeld [max] =flieger [max];
                                                cout << Bestzeit << endl;
                                                }

                   }
                                         }
                                     }
                                }
                            }
                         }
                    }
                 }
               }
             }

        }
  cout << "Reihenfolge: " << endl;
  cout << n << endl;
  cout << m << endl;
  cout << k << endl;

    for (i=1; i <max+1; i++)
      {
       cout << Bestfeld [i];
        }

    cout << endl;
    cout << endl;
   cout << "Die Summe ist:  " << Bestzeit << "sec" <<endl;
   cout << n;
    cout << "Die Summe ist:  " << Bestzeit/60 << "min" <<endl;

getch();
}
}