Mehrere Arrays sortieren

newcomer007

Hey Leute,
ich steh gerade vor folgendem Problem.
Ich habe eine bestimmte Anzahl Arrays, eindimensional, z.B 6 Arrays mit je 4 Speicherplätzen.
Diese möchte ich nun vergleichen, und sie danach sinnvoll wie folgt anordnen.
Die Arrays sollen so geordnet(angezeigt) werden dass sie in der Reihenfolge buchstäblich die meisten Punkte erzielen.
Wenn Speicherplatz 1 im Vergleich zum Vorgänger gleich ist bringt das 10 Punkte.
Speicherplatz 2 bringt 11 Punkte.
Speicherplatz 3 bringt 15 Punkte.
Speicherplatz 4 bringt 12 Puntke.

Ich bin über jede Hilfe dankbar

Programm bisher:

int array1[4];
int array2[4];
int array3[4];
int array4[4];

for (int i=0;i<4;i++)
{  
cin>> array1[i];
cin>> array2[i];
cin>> array3[i];
cin>> array4[i];
}

SeppJ

Kannst du mal ein paar Beispiele bringen? Bitte mit Rechenvorschriften, denn mir ist absolut nicht klar, wie sich 11, 15 und 12 aus 2, 3 und 4 ergeben. Und was ist der Vorgänger von Speicherplatz 1? Und was hat das überhaupt irgendwie mit den Werten im Array zu tun?

PS: Dein Programm ist jetzt schon fehlerhaft, Arrays fangen bei 0 an.

newcomer007

Ursprünglich:

Array 1 =(1,2,3,4)
Array 2 =(2,4,1,2) 0Pkt
Array 3 =(1,2,4,3) 0Pkt
Array 4 =(3,3,3,3) 12Pkt // Speicherplatz 4 identisch
_____
12Pkt

Sortiert

Array 3 =(1,2,4,3)
Array 1 =(1,2,3,4) 33Pkt //Speicherplatz 1,2,4 identisch
Array 4 =(3,3,3,3) 15Pkt //Speicherplatz 3 identisch
Array 2 =(2,4,1,2) 0Pkt
______
48 Pkt

Das Programm soll die beste Reihenfolge angeben.
Die Anzahl der Möglichkeiten hab ich wie folgt Programmiert:

int a=1;
	for (int i = 0; i < 4; i++)
	{
		a = (a*4 - i);
	};

newcomer007 schrieb:

Array 3 =(1,2,4,3)
Array 1 =(1,2,3,4) 33Pkt //Speicherplatz 1,2,4 identisch
Array 4 =(3,3,3,3) 15Pkt //Speicherplatz 3 identisch
Array 2 =(2,4,1,2) 0Pkt
______
48 Pkt

Halt! Schon das verstehe ich nicht - wie kommen die 33 zustande? Klar verstehe ich die Rechnung: 10 + 11 + 12 = 33. Aber ich sehe irgendwie nur, dass die ersten beiden Specherplätze von Array 3 und Array 1 identisch sind. Wie kommt man auf die 4? Bzw. was wird hier verglichen??

Die Anzahl der Möglichkeiten hab ich wie folgt Programmiert:
int a=1;
	for (int i = 0; i < 4; i++)
	{
		a = a*4 - i);
	};

Sehr unwahrscheinlich, denn das kann nicht kompilieren (du hast mehr schließende als öffnende Klammern).

Vielleicht ist der erste Schritt zur Lösung, dass du eine Funktion schreibst, die den Punktestand berechnet. Bzw sofern möglich, die zwischen zwei Arrays berechnet, wie viele Punkte diese bilden, wenn sie hintereinander stehen.

camper

Sieht nach Salesman-Problem aus.

newcomer007

@ wob
sry du hast recht speicherplatz 4 ist nicht identisch...
Aber das prinzip sollte verständlich sein.
Ich mach mich jetzt über das Salesman Problem schlau, und schau ob ich das so hinbekomme.

Die Anzahl der Möglichkeiten stimmt schon so wie ich sie geschrieben habe;), bis auf die eine Klammer die ich nicht geöffnet hatte bei der Rechnung, war aber ein Tippfehler.

Danke für eure Hilfe

newcomer007

Hey Camper hast du nen Ansatz wie ich das Programmieren könnte, gerne auch ein ganz einfaches Beispiel wäre super nett, komm i-wie nicht weiter.
Dankö

camper

z.B. Einfach Brute-force alle Varianten durchprobieren:

#include <algorithm>
#include <numeric>
#include <limits>
#include <iostream>
#include <vector>

using array_type = std::vector<int>;

array_type input(std::string info, int n) {
    array_type result(n);
    std::cout << info;
    for ( ; n--; )
        std::cin >> result[n];
    return result;
}

int score(const std::vector<array_type>& arrays, const array_type& weights) {
    return std::inner_product( std::begin( arrays ), std::end( arrays ) - 1, std::begin( arrays ) + 1, 0, std::plus<int>{},
        [&](auto& a, auto& b) {
            return std::inner_product( std::begin( a ), std::end( a ), std::begin( b ), 0, std::plus<int>{},
                [&](auto& x, auto& y) {
                    return ( x == y ) * weights[&x - &a.front()];
                } );
        } );
}

int main()
{
    std::cout << "Arraylänge: ";
    int l = 0;
    std::cin >> l;
    array_type weights = input( "Gewichte: ", l );
    std::cout << "Anzahl Arrays: ";
    int n = 0;
    std::cin >> n;
    std::vector<array_type> arrays;
    for ( int i = 0; i != n; ++i ) {
        arrays.push_back( input( "Array " + std::to_string( i ) + ": ", l ) );
    }
    std::sort( begin( arrays ), end( arrays ) );
    int best_score = std::numeric_limits<int>::min();
    std::vector<array_type> best;
    do {
        if ( score( arrays, weights ) > best_score ) {
            best_score = score( arrays, weights );
            best = arrays;
        }
    } while ( next_permutation( std::begin( arrays ), std::end( arrays ) ) );
    std::cout << "\nBeste Punkte: " << best_score << '\n';
    for ( auto& a : arrays ) {
    	std::cout << "( ";
        for ( auto& x : a ) {
            std::cout << x << ' ';
        }
        std::cout << ")\n";
    }
    std::cout << std::endl;
}

http://ideone.com/LcWxlH

newcomer007

Vielen Dank !!!!!!

Ich versuch ihn gleich mal aus !!

newcomer007

Funktioniert super!!!
Nochmals Danke.

#include <string>

musste ich noch an den Anfang schreiben.
Danach i.O
Danke