Java Werte aus 2D-Array gruppieren

Hallo Leute,

nun, schaut mal: ich habe so ein Int-Array z.B. (d.h. die positionen der Einsen und Nullen können variieren und auch das Array kann größer sein):


Nun ich möchte jetzt folgendes haben: undzwar eine Liste von Punktegruppen (diese Gruppe besteht aus einer Liste von Punkten). Darin werden aus dem Array mit den "Eins-Feldern" Gruppen gebildet. Dabei muss so eine Gruppe immer eine Breite von 2^n und eine Länge von 2^n haben und das Array zyklisch (d.h. die linke obere eins kann mit der rechten oberen 1 verbunden werden) und die einsen können mehrmals verwendet werden.

Als Ergebniss hätte ich dann für oben:

Wie gehe ich das am Besten und effizientesten an?

Für Vorschläge wäre ich Euch sehr dankbar!

Gruß,
CPU

Soll das arr1 selbst größer werden? Dann greif zu einer ArrayList oder Vector.

Das Gruppieren selbst geht wohl am Einfachsten, wenn du das Array ganz normal durchläufst und dann die x und y Positionen jeweils zu einem neuen Punkt(x,y)-Objekt machst und speicherst.
Um das ganze zu beschleunigen kannst du das ganze in n Threads ablaufen lassen. Also schneller als x*y Durchläufe geht nicht, außer es gibt ein Systemhinter den Punkten anhand dessen man den Algorithmus optimieren kann

Hey,

nee. Mir geht es jetzt erstmal darum die Felder mit dem Wert "1" zu gruppieren, dass ich o.g. Gruppen für diese Eingabe bekomme!

Gruß,
CPU

In zwei Schleifen drüberiterieren und sobald du ne '1' entdeckst das Array in ne Liste packen. Ist wirklich nicht so schwer...

So einfach ist das ja nicht, denn das Ausgangsarray ist ja zyklisch und die Gruppen dürfen nur so breit und so hoch wie 2^n sein, was ja auch über den Rand und über mehrere Zeilen gehen kann.

Gruß,
CPU

Ich hab zwei Mal drüber gelesen, aber mir ist nicht klar, was du da schreibst. Was für Gruppen? Wie soll das ablaufen?

Hallo,

ganz einfach: ich habe ein KV-Diagramm und möchte den Computer jetzt die Pakete zum minimieren bilden lassen!

Ich habe mir auch schon 1.200 Zeilen Code zusammengebaut, und machmal kommt etwas sinnvolles raus und manchmal nicht ...

Gruß,
CPU

Ach so, schreib das doch gleich.

Ist dein Diagramm immer zweidimensional? Das wäre wünschenswert, weil das die Komplexität des Programmcodes noch einigermaßen in Grenzen hält. Wenn es aber beliebig viele Ebenen enthalten soll, dann ist die Repräsentation als x-dimensionales Array eher eine schlechte Idee. Da muss man schauen, ob es da nicht was besseres gibt.

Hey,

wie wäre denn ein guter Ansatz für ein Programm? Also wie sollte ich vorgehen?

Gruß,
CPU

Mein Gedanke ist im Moment, erst mal alle "Punkte" zu sammeln, die eine 1 darstellen. So wie du es auch schon gemacht hast.
Im zweiten Schritt sollte in dieser Punkt"wolke" geschaut werden, welche Punkte benachbart liegen und ein Rechteck (Kantenlänge ist eine Potenz von 2) bilden. Kommt es dabei zu Kollisionen (zwei Rechtecke überschneiden sich, wird dem größeren Rechteck der Vorzug gegeben.
Das was an Punkten übrig bleibt wird daraufhin untersucht, ob sie Linien bilden.

Am Ende hat man dann drei Mengen: Rechtecke, Linien und verbleibende Punkte.
Diese Vorgehensweise eignet sich sich bei einem 2D-Array.
Edit: Man könnte Linien ebenfalls als Rechtecke sehen. Sie ist hier eben nur ein Rechteck, dessen eine Kante eine Länge von 1 hat. Dasselbe mit einzelnen Punkten. Diese Betrachtungsweise dürfte den Algorithmus spürbar entschärfen.



Bei 3D bis xD wird das zu kompliziert. Ich überlege da immer noch, wie man die Daten unabhängig von der Anzahl der Dimensionen speichern kann. Da bleibt eigentlich nur noch ein Graph übrig.
Hier gibt es zwei Herangehensweisen:
1.) Man speichert die Knoten, wobei jeder Knoten eine 1 im KV-Diagramm darstellt. Die Knoten müssen dann eine Liste der Nachbarknoten sowie deren Dimensionsrichtung haben.
2.) Man speichert nur die Verbindungen zwischen zwei Knoten. Die Verbindungen müssen aber eine Eigenschaft besitzen, anhand derer man die Dimensionsrichtung bestimmen kann.

Während 1. relativ umständlich zu handhaben ist, weiß man bei 2. nicht genau, wo im KV der Knoten steht. Bei 2. sollte es aber relativ einfach sein, zumindest Linien zu finden.
Eine Kombination aus 1. und 2. sieht mir am erfolgversprechendsten aus.
Das geht schon in Richtung semantischer Netze. Die haben mehr oder weniger denselben Aufbau, auch wenn sie für einen ganz anderen Zweck eingesetzt werden.

Ich kann mir allerdings nicht vorstellen, wie man Gruppen in so einem Graph finden kann. Bei 3D geht das ja noch, bei 4D versagt meine Vorstellungskraft. Da bräuchte man einen Mathematiker.

[Frage GELÖST]

Hallo,

ich wollte nur verkünden, dass ich jetzt so einen Algorithmus entwickelt habe, der (hoffentlich) funktioniert.

@e-Laurin
Vielen Dank für Deine Hilfe!

Ich wollte niemals in 3D arbeiten. Ich habe einen Algorithmus für KV-Tafeln mit 1-4 Variablen geschrieben (in 2D eben). Nun man könnte jetzt noch auf 5-6 Variablen erweitern (machen die hier), doch mir ist noch nicht so ganz klar, wie das gehen soll!

Nun gut. Vielleicht interessiert es ja die Nachwelt, wie der Algorithmus funktioniert: es wird das Array komplett durchlaufen und an jedem Feld halt gemacht und geschaut, wie weit man nach rechts expandieren kann und dann, ob man das Feld nach unten expandieren kann. Das Ergebnis wird zwischengespeichert. Dann wird die Ergebnisliste nach Arraygröße sortiert (größte oben) und auf Permutationen durlaufen und alle solche entfernt. Und schließlich wird noch diese Menge von Punktgruppen durchlaufen und auf Überflüssige Gruppen getestet (d.h. wenn zwei Punkte bereits schon von verschiedenen Gruppen belegt wurde, aber nochmals von einer Gruppe explizit angegeben werden). Und als Ergebnis hat man dann die Punktgruppen.

Beste Grüße,
CPU