Hi Leute,
ich will ein zweidimensionales Array auf Transitivität überprüfen. Ich hab z.B. ein Array:
[bla1, bla2]
[bla3, bla2]
[bla1, bla3]
Nach der Überprüfung soll er mir dann einfach folgendes ausgeben:
(Kann man dies auch unabhängig von der Stellung der Paare machen?)
[bla1, bla2, bla3] falls Transitivität vorhanden ist.
Beschreib’ mal genauer, was du meinst: Meinst du ein Array der Größe nn, oder ein Array der Größe n2? Wenn man sich
[bla1, bla2]
[bla3, bla2]
[bla1, bla3]
vorstellt als Paare, die in einer (transitiven) Relation stehen, und man mal einsetzt:
bla1 = 1
bla2 = 3
bla3 = 2
und als Relation mal “<” annimmt, dann steht da
1 < 3
2 < 3
1 < 2
wobei das erste aus den letzten beiden folgt.
Oder willst du einfach nur wissen, ob die Paare genau alle Elemente einer Transitiven (Hülle einer) Relation sind?
Ich meine n*2!
[QUOTE=Marco13;9690]
Oder willst du einfach nur wissen, ob die Paare genau alle Elemente einer Transitiven (Hülle einer) Relation sind? [/QUOTE]
Ich glaube ich meine das zweitere!? Ich sehe:
[bla1, bla2]
[bla3, bla2]
[bla1, bla3]
als Objektpaare und möchte prüfen, ob ein Paar transitiv ist.
Es soll in einem n*2 Array geprüft werden, ob es bei jedem Objektpaar der Fall ist.
OK - eine (binäre) Relation R ist eine Menge von Tupeln (a,b) mit a € S und b € T. Die Relation heißt transitiv, gdw.
(a,b) € R ^ (b,c) € R -> (a,c) € R.
Was so viel heißen soll wie: “ob ein Paar transitiv ist” kann man nicht sagen, weil nicht die Paare transitiv sind, sondern bestenfalls die Relation, die sie beschreiben.
Aber ich gehe jetzt davon aus, dass die gegbenen Paare genau die Relation SIND. In Anlehnung an die oben genannte Bedingung wäre ein Algorithmus im Pseudocode
Für jedes Element (a,b) der Relation
Für jedes Element (c,d) der Relation
Wenn b==c ist
Wenn (a,d) nicht in der Relation enthalten ist, gib "false" zurück
Gib "true" zurück
Oder im richtigen Code…
import java.util.*;
public class TransitivityTest
{
public static void main(String args[])
{
Object r0[][] = new Object[][]
{
{ "bla1", "bla2" },
{ "bla3", "bla2" },
{ "bla1", "bla3" }
};
System.out.println(isTransitive(r0));
Object r1[][] = new Object[][]
{
{ "bla1", "bla2" },
{ "bla3", "bla2" },
{ "bla1", "bla3" },
{ "bla2", "bla1" }
};
System.out.println(isTransitive(r1));
}
private static boolean isTransitive(Object array[][])
{
Object a[] = new Object[2];
for (int i=0; i<array.length; i++)
{
for (int j=i+1; j<array.length; j++)
{
Object a0[] = array**;
Object a1[] = array[j];
if (a0[1].equals(a1[0]))
{
a[0] = a0[0];
a[1] = a1[1];
if (!contains(array, a))
{
return false;
}
}
}
}
return true;
}
private static boolean contains(Object array[][], Object a[])
{
for (int i=0; i<array.length; i++)
{
if (array**[0].equals(a[0]) &&
array**[1].equals(a[1]))
{
return true;
}
}
return false;
}
}
Ggf. könnte man das natürlich noch effizienter machen, aber … naja, Arrays sind eben erstmal unhandlich.
such mal nach dem Warshall algorithmus… der berechnet die trans. Huelle (wenn auch in O(n^3))
Ja, war auch mein erster Ansatz: Eine Methode um aus dem Array ein Set von Paaren zu machen, eine Methode um die Transitive Hülle einer Menge von Paaren zu berechnen, und dann einfach prüfen, ob die Menge gleich ihrer transitiven Hülle ist. Da könnte man auch noch einiges optimierien, aber in diesem Fall braucht man die transitive Hülle ja nicht zu berechnen: Wenn schon das erste (a,c) für (a,b) und (b,c) NICHT vorhanden ist, ist die Sache ja schon klar…
Hi,
ich hab nun folgenden vergleich gemacht und es funzt auch.
String[][] array = { { "bla1", "bla2" }, { "bla2", "bla3" }, { "bla3", "bla1" } };
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array.length; j++) {
if (array**[1].equals(array[j][0])) {
boolean transitiv = false;
for (int k = 0; k < array.length; k++) {
if (array**[0].equals(array[k][0])
&& array[j][1].equals(array[k][1])) {
transitiv = true;
System.out.println("Verbindung von " + array**[0]
+ " -> " + array**[1] + " und "
+ array[j][0] + " -> " + array[j][1]
+ " und " + array[k][0] + " -> "
+ array[k][1]);
}
else if (array**[0].equals(array[k][1])
&& array[j][1].equals(array[k][0])) {
transitiv = true;
System.out.println("Verbindung von " + array**[1]
+ " -> " + array**[0] + " und "
+ array[j][1] + " -> " + array[j][0]
+ " und " + array[k][1] + " -> "
+ array[k][0]);
}
}
if (!transitiv) {
System.out.println("Die Relation ist nicht transitiv");
}
}
}
}
}```
Nun gibt er mir natürlich eine doppelte Ausgabe:
> Verbindung von bla2 -> bla1 und bla3 -> bla2 und bla1 -> bla3
> Verbindung von bla3 -> bla2 und bla1 -> bla3 und bla2 -> bla1
Wie könnte ich aus meiner Ergebnismenge ein Durchschnitt der Elemente ziehen und es in ein Array2
```String[] array2 = { { "bla1" }, { "bla2" }, { "bla3" } };```
speichern.Hab das Programm jetzt nicht 100% nachvollzogen, aber … vermutlich(!) kann das Problem gelöst werden, indem du eine der Inneren Schleifen nicht bei 0 loslaufen läßt, sondern bei “Schleifenzähler der äußeren Schleife + 1”. War es das, was du meintest? Oder willst du nur “doppelte Elemente aus einem Array entfernen”?
Hi,
ich will eigentlich nur die doppelten bzw. mehrfachen Elemente aus dem Array entfernen!
Hat jemand dafür eine Idee?
Die Elemente des Arrays in ein “Set” einfügen - das enthält jedes Element nur EIN mal, d.h. Elemente, die mehrfach eingefügt werden, liegen trotzdem nur EIN mal im Set. Das Set kann man dann wieder in einen Array verwandeln. Und wenn man ein LinkedHashSet verwendet, ist das ganze auch noch einigermaßen schnell, und die Reihenfolge der Elemente bleibt erhalten. Oder als code
import java.util.*;
class UniqueTest
{
public static void main(String args[])
{
String array[] = new String[] { "A", "B", "C", "A", "C" };
System.out.println(Arrays.toString(makeUnique(array)));
}
private static String[] makeUnique(String array[])
{
return new LinkedHashSet<String>(Arrays.asList(array)).toArray(new String[0]);
}
}
Danke!