int-Listen entsprechend der Häufigkeiten der Elemente vereinigen

rotzenplotz

Moin, vllt. könnt ihr mir weiterhelfen:

Ich habe beliebig viele Listen, gefüllt mit int. Diese möchte ich möglichst effizient mergen, dabei aber die Häufigkeiten der einzelnen Zahlen zählen und die gemergte Liste entsprechend der Häufigkeiten sortieren. Mal ein Beispiel:

3 Listen*
* 1 4 6 8 9
* 1 2 3 6
* 4 6 7 8 9 10

Häufigkeiten:
1 -> 2 (Die Zahl "1" kommt insgesamt 2x vor)
2 -> 1
3 -> 1
4 -> 2
6 -> 3
7 -> 1
8 -> 2
9 -> 2
10 -> 1

Gemergte Liste, entsprechend der Häufigkeiten, absteigend:
6, 1, 4, 8, 9, 2, 3, 7, 10 (bei gleichen Häufigkeiten ist Reihenfolge egal)

Mein 1. Versuch: Listen durchgehen, die Häufigkeiten durchgehen und in einer Map speichern. Problem: Map kann nicht nach Value geordnet werden (was ich hier müsste).

Mein 2.Versuch: Häufigkeiten in einer Liste von Paaren (Paar besteht aus Zahl und Häufigkeit). Beim Durchlaufen müsste ich feststellen, ob es bereits ein Paar für die gerade besuchte Zahl gibt. Mittels "find" kann man aber wohl nur feststellen, ob beriets ein Paar mit gleichem "first" und gleichem "second" gibt. Ich bräuchte quasi eine Möglichkeit, Paare zu finden, die nur den gleichen "first" haben.

Kann mir da einer bei meinem Problem helfen? (Hoffe, ich habe nichts wesentliches vergessen, was zum Verständnis des Problems nötig ist).

SeppJ

Sind die Zwischenschritte wichtig oder kommt es dir nur auf das Endergebnis (die nach Häufigkeiten sortierte Liste) an?

rotzenplotz

Zwischenschritte sind eigtl. egal, im Prinzip brauch ich letztendlich eine Liste der Zahlen, absteigend nach ihrer Häufigkeit (Zwischenschritte waren meine Versuche, aber die haben mich wie man sieht nicht weitergebracht )

SeppJ

Also spontan würde ich so vorgehen:
1. Listen durchgehen, Häufigkeiten in map speichern.
2. map durchgehen, umgedrehte Paare (also <value, key>) in set sortieren.

Ist vermutlich nicht das cleverste, aber ein einfach programmierbarer Anfang.

rean

Kannst du irgendwelche Aussagben über die Zahlen in den Listen treffen?
Liegen alle in einem bestimmten Bereich?
Kennst du das kleinste und/oder größte Element vor dem Mergen?

rotzenplotz

SeppJ schrieb:

Also spontan würde ich so vorgehen:
1. Listen durchgehen, Häufigkeiten in map speichern.
2. map durchgehen, umgedrehte Paare (also <value, key>) in set sortieren.

Ist vermutlich nicht das cleverste, aber ein einfach programmierbarer Anfang.

Danke für den Denkanstoss, werde ich mir mal durch den Kopf gehen lassen

rotzenplotz

rean schrieb:

Kannst du irgendwelche Aussagben über die Zahlen in den Listen treffen?
Liegen alle in einem bestimmten Bereich?
Kennst du das kleinste und/oder größte Element vor dem Mergen?

Alle Zahlen sind >= 0. Aber das sind ist schon die einzige Einschränkung.

rean

Wirklicher schwer ist der Code ja nicht:

#include <map>
#include <list>
#include <iostream>
#include <conio.h>

void mergeInto( std::map< int, int > &m, const std::list< int > &l )
{
	for( std::list<int>::const_iterator iter = l.begin();
		 iter != l.end(); ++iter )
	{
		++(m.insert( std::make_pair( *iter, 0 ) ).first->second);
	}
}

void convert( std::list< int > &l, const std::map< int, int > &m )
{
	std::multimap< int, int, std::greater<int> > tmp;

	for( std::map< int, int >::const_iterator iter = m.begin();
		 iter != m.end(); ++iter )
	{
		tmp.insert( std::make_pair( iter->second, iter->first ) );
	}

	for( std::multimap< int, int, std::greater<int> >::iterator iter = tmp.begin();
		 iter != tmp.end(); ++iter )
	{
		l.insert( l.end(), iter->second );
	}
}

int main()
{
	int l1a[] ={ 1, 4, 6, 8, 9 };
	int l2a[] ={ 1, 2, 3, 6 };
	int l3a[] ={ 4, 6, 7, 8, 9, 10 };

	std::list< int > l1( l1a, l1a + sizeof( l1a ) / sizeof( int ) );
	std::list< int > l2( l2a, l2a + sizeof( l2a ) / sizeof( int ) );
	std::list< int > l3( l3a, l3a + sizeof( l3a ) / sizeof( int ) );

	std::map< int, int > m;
	std::list< int > newList;

	mergeInto( m, l1 );
	mergeInto( m, l2 );
	mergeInto( m, l3 );
	//...
	convert( newList, m );

	for( std::list< int >::iterator iter = newList.begin();
		 iter != newList.end(); ++iter )
	{
		std::cout << *iter << ',';
	}

	getch();

	return 0;
}

Der Aufwand ist aber halt relativ groß.

[EDIT]
Sind die ursprünglichen Listen eigentlich schon sortiert oder ist das bei deinem Beispiel nur Zufall?

[EDIT#X]
Ein paar Fehler im Code korrigiert

rotzenplotz

rean schrieb:

Wirklicher schwer ist der Code ja nicht:

#include <algorithm>
#include <map>
#include <list>
#include <cstdlib>
#include <ctime>

void mergeInto( std::map< int, int > &m, const std::list< int > &l )
{
	for( std::list<int>::const_iterator iter = l.begin();
		 iter != l.end(); ++iter )
	{
		++(m.insert( std::make_pair( *iter, 0 ) ).first->second);
	}
}

void convert( std::list< int > &l, const std::map< int, int > &m )
{
	std::map< int, int > tmp;

	for( std::map< int, int >::const_iterator iter = m.begin();
		 iter != m.end(); ++iter )
	{
		tmp.insert( std::make_pair( iter->second, iter->first ) );
	}

	for( std::map< int, int >::iterator iter = tmp.begin();
		 iter != tmp.end(); ++iter )
	{
		l.insert( l.end(), iter->first );
	}
}

int main()
{
	std::list< int > l;

	srand( time( NULL ) );

	for( int i = 0; i < 10; ++i )
	{
		l.insert( l.end(), rand() );
	}

	std::map< int, int > m;
	std::list< int > newList;

	mergeInto( m, l );
	//...
	convert( newList, m );	

	return 0;
}

Der Aufwand ist aber halt relativ groß.

[EDIT]
Sind die ursprünglichen Listen eigentlich schon sortiert oder ist das bei deinem Beispiel nur Zufall?

Ui, soviel Aufwand hättest du dir echt nicht machen müssen. Brauchte eigtl. nur einen kleinen Denkanstoss, um mir da was schlaues ausdenken zu können. Trotzdem danke für deine Mühe. Habs jetzt einigermaßen hinbekommen durch die Idee von SeppJ.
Zum Edit: Achja, vergessen zu erwähnen: Listen sind sortiert

rean

Der Code stellt ja eigentlich genau SeppJ Vorschlag dar

Wenn die Listen vorher schon sortiert sind könnte man das ganze durch nen intelligenten Merge noch ordentlich beschleunigen.