Teile und Herrsche

[info_11]

hi, ich habe große probleme Teile und Herrsche Algorithmen zuentwickeln und deswegen suche ich hier mal nachhilfe.


Es soll ein unsortiertes Array durchlaufen werden. Das Element was am häufigsten vorkommt, soll zurückgeben werden.
Habe mich mal ein bisscehn an den code vom maximum bestimmen, den ich hier gefunden habe, orientiert. Aber so wirklich weitergeholfen hat er nicht.

static int max(int[] a){
return max(a, 0, a.length-1);
}
 
static int max(int arr[],int min, int max){
 
  if( max - min > 1 ){
            int middle = (min + max) / 2;
            int a = max( arr, min, middle );
           int b= max( arr, middle+1, max );
           return (a==b)?a:0;
        }
        else
            return ( arr[min] ==arr[max] )  ?
                    arr[min]: 0;
                    
                    
    }
}

 

[Marco13]

Entweder ich bin übermüdet und sehe wieder mal den :idea: - Punkt dabei nicht, oder ... das ist gar nicht so leicht (sowohl mit als auch ohe Divide and Conquer - und insbesondere natürlich ohne Dinge wie TreeMaps ). Kannst du die genaue Aufgabenstellung posten?

 

[info_11]

Naja die genaue Aufgabe ist noch etwas komplizierter^^.

Gegeben sei ein Array A[1 ... n] über einem Datentyp, für den keine Ordnung seiner Elemente
vorliegt. Wohl aber ist ein Vergleich A = A[j] in konstanter Zeit möglich. Ein solches Array
A[1 ... n] besitzt nun ein majorisierendes Element, falls mehr als die Hälfte seiner Elemente
denselben Wert besitzt.


1. Geben Sie einen Teile-und-Herrsche Algorithmus in an, der in O(n
log n)
Schritten feststellt, ob in einem Array A[1 ... n] ein majorisierendes Element vorhanden ist
und, falls dies der Fall ist, dieses auch ausgibt. Begründen Sie die Rechenzeit O(n
log n).

 

[Marco13]

Ahjanaja... "Am häufigsten" ist da was ganz anderes als "majorisierend". (Dieser ganze formale Kram hat oft einen Grund ) Jetzt bin ich zwar ggf. NOCH übermüdeter aber spontan würde ich sagen, dass ein Element majorisierend ist, wenn es in beiden Hälften des Arrays majorisierend ist... vielleicht hilft das als Ansatz...?

 

[Fant]

spontan würde ich sagen, dass ein Element majorisierend ist, wenn es in beiden Hälften des Arrays majorisierend ist... vielleicht hilft das als Ansatz...?

Das ist zwar richtig, aber bringt einen nicht weiter. Die andere Richtung, die viel interessanter wäre, gilt nämlich nicht.

Die Idee sollte eher dahin gehen, dass man in beiden Array-Hälften nach einem möglichen majorisierenden Element sucht, und dann im kombinierten Array überprüft, ob es sich wirklich um ein majorisierendes Element handelt.

Alternativ kann man auch ein Quicksort über das Array laufen lassen (ist ja ein DC-Algo) und braucht nur noch den Median zu überprüfen. Die Lösung ist aber vermutlich nicht gewünscht

Man kann das majorisiernde Element eines Arrays übrigens auch in O(n) finden, aber das ist hier ja nicht gefordert...


Gruß Fant

 

[info_11]

Also den Algorithmus mit der Laufzeit von O(n) ist dann aufgabe 2. Da soll wir den nochmal optimieren.

Aber hätte einfach gerne erstmal überhaupt eine Lösung oder einen Ansatz, weil wie gesagt komm mit Teile und Herrsche irgendwie nicht so klar und finds schwierig so einen Algorithmus zuentwickeln.

 

[Paddelpirat]

Hmm ein majorisierendes Element ist nicht majorisierend, wenn es in beiden hälften majorisierend ist. Einfaches Gegenbeispiel: Array: 0 0 0 1 -> 0 0 | 0 1
Da ist die 0 nur in der einen Hälfte majorisierend. Aber sie ist für das gesamte Array majorisierend.

Um das Problem zu lösen, würde ich mir eine Hashmap "Occurrence" definieren, in der ich die einzelnen Alemente des Arrays und deren Häufigkeit ablegen kann. Die Hashmap ist anfangs leer.

Dann würde ich auf dem gegebenen Array divide & conquer anwenden (wie du es getan hast). Jedes mal, wenn A==A[j] gilt, guckst du dann, ob A schon in der Hashmap "Anzahl" enthalten ist (geht in O(n)).
Wenn nicht, dann fügst du A hinzu und erhöhst dann in der zweiten Spalte der Hashmap den Counter für diesen Eintrag um 2, falls in deinem Algorithmus max-min>1 ist und sonst nur um 1 (min=max).

Wenn du dann mit Teile und Herrsche durch bist, musst du nur noch einmal deine Hashmap durchgehen und das größte als "biggest" Element merken, was in O(n) geht. (Dann ist das Element majorisierend, wenn der Counter > n/2 ist.)

Edit: Obiges Gegenbeispiel noch abgeändert, da hatte ich einen kleinen Denkfehler drin

 

[info_11]

Mhh danke erstmal.

Aber ich glaube mit Hashmap sollen wir das nicht wirklich machen, weil wir das noch gar nicht bei uns vorkam.

Das problem ist das ich irgendein counter brauche mit den ich dann die Elemente zähle und dann wenn counter>arr.length/2 ist dann das Element zurückgebe. Klingt irgendwie nicht so schwierig, aber trotzdem komm ich nicht drauf.

Also reintheoretisch reicht auch eine vereinfachte Version in Pseudocode. Also wir müssen das nicht unbedingt implementieren. So ist das vllt einfacher.

 

[Paddelpirat]

Kannst ja auch statt Hashmap zwei Arrays verwenden:
Dann guckst du in dem ersten Array nach, ob du das eine Element schon mal hattest, wenn ja nimmst du dessen position p und erhöhst dann in dem zweiten Array an Position p den counter um 1 bzw. 2.

Vielleicht gibts aber wirklich noch eine elegantere Lösung, aber funktionieren sollte es ;-)

 

[Fant]

Was ist das Problem bei meinem Vorschlag?

Hab es gerade einfach mal testweise implementiert und es läuft.

 

[info_11]

Quicksort benutzen??

Also habe ich gestern auch versucht, aber irgendwie nicht hinbekommen. Vllt bin ich einfach zu dumm dafür.

 

[Fant]

Nein, kein Quicksort. Das war nur als (nicht unbedingt ernst gemeinte) Alternative gedacht (da etwas an der Aufgabenstellung vorbei).

In der Zeile dadrüber steht eigentlich alles, was man machen muss. Hier:

Die Idee sollte eher dahin gehen, dass man in beiden Array-Hälften nach einem möglichen majorisierenden Element sucht, und dann im kombinierten Array überprüft, ob es sich wirklich um ein majorisierendes Element handelt.

 

[info_11]

Also ich habe mich jetzt auch mal hingesetzt, aber keine ahnung wie du das machst. Vorallem weiße ich auch nicht wie das mit Teile und Herrsche geht.

Ich muss doch erstmal das array teilen und zwei neue Arrays erstellen und diese initialiseren mit den werten. Und dann muss ich ja beide arrays nochmal durchgehen und diese überprüfen ob es ein majorisierendes Element gibt. Das geht ja eigentlich auch nur mit einer doppelten For schleife.
Wie gesagt Teile und Herrsche habe ich einfach überhaupt nicht drauf.

Das hier erstmal mein code. Aber habe ich jetzt auch nicht weitergeführt, weil das sowieso auf nichts sinnvolles hinausläuft. Naja wär cool wenn du mir vllt mal was du da gemacht hast, schicken könntest.

  public static int maj(int[] arr, int links, int rechts){
     
      int n=arr.length;
      int [] a=new int [n/2] ;
      int []b= new int [n/2];
      
      for(int i=0;i<a.length;i++){
        a[i]=arr[i];
        
        
        }
      
        for(int j=0;j<b.length;j++){
        
        arr[j]=arr[(n+1/2)+j];
        
        
        }
        
        
        for(int i=0;i<a.length;i++){
        
        .....
        
        }
      
    
}

 

[Fant]

Eigentlich bin ich kein Freund von so was, da der Lernerfolg sicherlich höher ausfällt, wenn du dir die Lösung selbst erarbeitest. Aber wenn du unbedingt willst, dann bitte:

package de.javaforum.util;

import java.util.ArrayList;
import java.util.List;

public class ArrayUtil {

	
	// Gibt das majorisierende Element zurück, wenn es ein gibt, sonst NULL
	// Komplexität in O(n*log(n)
	// denn:
	// T[n] = 2*T[n/2] + O(n)
	public static Object findMajorityElement(List<? extends Object> liste) {
		int size = liste.size(); 					// in O(1)
		if (size == 0) return null;					// in O(1)
		else if (size == 1)	return liste.get(0);	// in O(1)
		else {
			Object lMajor = findMajorityElement(liste.subList(0, (size-1)/2));			// rek. Aufrug mit n = n/2
			Object rMajor = findMajorityElement(liste.subList((size-1)/2+1, size-1));	// rek. Aufruf mit n = n/2
			int count = 0;
			if (lMajor != null) {														// in O(n)
				for(Object o : liste) {	if (o.equals(lMajor)) count += 1; }				//
				if (count>size/2) return lMajor;										//
			}
			count = 0;
			if (rMajor != null) {														// in O(n)
				for(Object o : liste) {	if (o.equals(rMajor)) count += 1; }				//
				if (count>size/2) return rMajor;										//
			}
		}
		return null;
	}
	
	// Test-Main
	public static void main(String[] args) {
		List<Integer> liste = new ArrayList<Integer>();
		int [] array = {1,2,3,4,2,2,5,2,6,2,2,2,2,7,2,8,2,2,2,9,2,2,2};
		
		for(int i : array) {
			liste.add(new Integer(i));
		}
		
		Integer i = (Integer) findMajorityElement(liste);
		
		if(i == null) System.out.println("There is no majority element in the list");
		if(i != null) System.out.println("The majority element in the list is: "+i.toString());

	}
}

Ich habe hier Listen benutzt, da man sich so das Hin- und Herschaufeln in Teilarrays sparen kann. Eine Liste als Datenstruktut erschien mir daher sinnvoller. Mit Arrays würde es aber praktisch genau so funktionieren.

 

[BildschirmUser]

Deine Lösung beinhaltet einen Fehler, falls das array eine ungerade Anzahl an Werten beinhaltet.

Teste mal:
{1,2,1,2,2,3,2,1,2} -> 9 Elemente, 5 mal taucht dort die 2 auf.

Jedoch gibt dein Code als Ausgabe, dass es kein major Element gibt...

PS.
gruß an die TU

jm

 

[Fant]

Du hast Recht, danke für den Hinweis

public List subList(int fromIndex, int toIndex)

Returns a view of the portion of this list between the specified fromIndex, inclusive, and toIndex, exclusive.

Das hab ich nicht bedacht, ich hab angenommen, der letzte Eintrag sei auch inclusive. Lässt sich aber ja schnell fixen.


Die Grüße gingen wohl an den Themenersteller? Ich hab jedenfalls nix mit irgendeiner TU zu tun.

Gruß Fant

 

[Crian]

aber spontan würde ich sagen, dass ein Element majorisierend ist, wenn es in beiden Hälften des Arrays majorisierend ist... vielleicht hilft das als Ansatz...?

Gesamt: a, a, a, a, b, b - majorisierend ist a

Hälfte 1: a, a, a - majorisierend ist a

Hälfte 2: a, b, b - majorisierend ist b

 

[Marco13]

Leute, die mich darauf hingewiesen haben, dass dieser um halb drei nachts spontan geäußerte Gedanke falsch war: 3
Leute, die eine richtige Lösung gespostet haben: 0.5

 

[Dow Jones]

Leute, die mich darauf hingewiesen haben, dass dieser um halb drei nachts spontan geäußerte Gedanke falsch war: 3
Leute, die eine richtige Lösung gespostet haben: 0.5

Die Fähigkeit Besserwisser in einem Forum ggf. ignorieren zu können: Unbezahlbar.

 

[Paddelpirat]

Leute, die mich darauf hingewiesen haben, dass dieser um halb drei nachts spontan geäußerte Gedanke falsch war: 3
Leute, die eine richtige Lösung gespostet haben: 0.5

Stellt sich noch die Frage, ob die Uhrzeit dafür eine Rolle spielt, oder wie die allgemeine Statistik für spontan geäußerte falsche Gedanken ist. ;-)

 

[Marco13]

Die Aussage, die ich ursprünglich gemacht habe, war ja sogar richtig:

Wenn ein Element in beiden hälften majorisierend ist, dann ist es im Gesamtarray majorisierend

Aber wie Fant richtig gesagt hat: Es hilft einem hier nichts. Es würde helfen, wenn es eine "Genau dann, wenn"-Aussage wäre, was aber nicht der Fall ist.

Wie der Autofahrer, der sich verirrt hat, und einen Informatiker am Straßenrand fragt: "Wo bin ich denn hier?" und der Informatiker sagt: "In einem Auto": Lauter wahre Aussagen, die kein Stück weiterhelfen

Den Hinweis von Dow Jones ignoriere ich jetzt einfach mal ( )

 

[Crian]

Die Aussage, die ich ursprünglich gemacht habe, war ja sogar richtig:

Wenn ein Element in beiden hälften majorisierend ist, dann ist es im Gesamtarray majorisierend

Aber wie Fant richtig gesagt hat: Es hilft einem hier nichts. Es würde helfen, wenn es eine "Genau dann, wenn"-Aussage wäre, was aber nicht der Fall ist.

Stimmt.

Man könnte noch etwas hinzufügen: Wenn ein Element in beiden Hälften nicht majorisierend ist, kann es das trotzdem in der Gesamten Menge sein.


Menge a, a, a, b, b, b, b, c, c, c -> b gewinnt

Teil 1: a, a, a, b, b - > a gewinnt

Teil 2: b, b, c, c, c -> b gewinnt

Also reicht es leider auch nicht aus, nur die Kandidaten aus den Teilmengen zu untersuchen. Verflixt.

 

[Fant]

Man könnte noch etwas hinzufügen: Wenn ein Element in beiden Hälften nicht majorisierend ist, kann es das trotzdem in der Gesamten Menge sein.

Nein, das kann nicht sein.


Ich weiß nicht, wieso das hier jedem entgangen zu sein scheint, aber ich hab schon eine Lösung des Problems gepostet.

 

[jgh]

mmmh, bis auf den Schreibfehler...kann ein Element doch in beiden Teilmengen nicht majorisierend sein, in der gesamten Menge wohl.

Menge a, a, a, b, b, b, b, c, c, c -> b ist majorisierend

Teil 1: a, a, a, b, b - > a ist majorisierend

Teil 2: b, b, c, c, c -> c ist majorisierend

oder...???

 

[Crian]

ja unten sollte c stehen. Bei einem gegebenen Gegenbeispiel zu sagen "das kann nicht sein" ist ... gewagt

 

[Fant]

In deinem "Gegenbeispiel" ist b aber NICHT majorisierend. Ich denke es ist einfach nicht klar, was der Begriff bedeutet!

Ist ein Element in einer Liste/einem Array majorisierend, dann ist es auf jeden Fall in einer Hälfte majorisierend, egal wie man das Array in zwei "Hälften" aufteilt.


Hier noch mal die gegebene Definition:

Ein solches Array
A[1 ... n] besitzt nun ein majorisierendes Element, falls mehr als die Hälfte seiner Elemente
denselben Wert besitzt.

Und abgesehen von dem falsch gesetzten Index bei der Aufteilung in Sublisten, funktioniert mein Code fehlerfrei. Das ist aber in den beiden Posts dadrunter schon vermerkt. Den Index richtig setzen, das wird mit diesem Hinweis ja nun wohl jeder selbst hinbekommen. (ändern kann ich den Beitrag eh nicht mehr)


Gruß Fant

 

[Marco13]

Hast du das Gegenbeispiel von Crian (bzw. das korrigierte von jgh) gesehen?

 

[Fant]

Ja, habe ich. Und noch mal: Das ist KEIN Gegenbeispiel, da b dort nicht majorisierend ist.

 

[Marco13]

Stimmt, da hatte mich Crian rausgehauen... Zeit für den Feierabend ... :autsch:

 

[Crian]

Stimmt. Da hab ich mich mit der falschen Definition im Kopf selbst auch rausgehauen. :autsch:

Dann nehme ich alles zurück und behaupte das Gegenteil:

Behauptung: Wenn das Element e majorisierend in Menge M ist, und M1 und M2 jeweils disjunkte Teilmengen von M sind, deren Vereinigung M ergibt, so gilt: A ist majorisierend in M1 oder in M2.

Beweis: Aufgrund der Bedingungen an M, M1 und M2 in der Behauptung gilt

(i) |M| = |M1| + |M2|

Die Anzahl der in einer Menge N vorkommenden Elemente e sei berechnet durch f(N). Dann gilt

(ii) f(M) >= |M| / 2

(iii) f(M1) + f(M2) = f(M)


Falls f(M1) >= |M1| oder f(M2) >= |M2| gilt, so ist die Behauptung bewiesen. Also gelte

(iv) f(M1) < |M1| / 2
(v) f(M2) < |M2| / 2

Aus (iv) und (v) folgt

(vi) f(M1) + f(M2) < (|M1| + |M2|) / 2

Aus (vi) und (i) folgt

(vii) f(M1) + f(M2) < |M| / 2

Aus (vii) und (iii) folgt

(viii) f(M) < |M| / 2

was im Widerspruch zu (ii) steht. Also ist die Annahme ( (iv) + (v) )falsch und die Behauptung bewiesen.
q.e.d.