ubuntuusers.de

Hallo Community!

Ich habe es mit meiner Frage bei den Mathematikern versucht und man kam auf keine Lösung, mal sehen wie es bei den Informatikern aussieht. ☺ Die Frage ist Folgende:

Ich habe zwei Matrizen der Größe 15x25, die mit Nullen und Einsen gefüllt sind. In jeder der 25 Zeilen jeder der Matrizen gibt es genau 2 Einsen, sonst Nullen, insgesamt also jeweils 50 Einsen und 325 Nullen. Die Matrizen sind fast identisch, nur eine einzige Eins ist verschoben.

Nun möchte ich überprüfen, ob die beiden Matrizen ineinander übergeführt werden können. Zulässig sind folgende Operationen: Man darf die Reihenfolge der Spalten und/oder Zeilen beliebig ändern, aber die Zeilen und Spalten müssen als ganze "bewegt" werden. Und so sehen die Matrizen aus:

http://www.ubuntu-pics.de/bild/12559/scan0013_HRM2U3.jpg

Die eine Matrix ist mit der Eins bei (14/15), die andere ist zur ersten identisch, nur die Eins ist nach (8/15) verschoben (siehe Pfeil).

Kann man das irgendwie vom Computer berechnen lassen? Ist es überhaupt eine gängige Operation bei einer Matrix (Array?) die Spalten bzw. Reihen zu vertauschen? Bin leider in Sachen Programmierung ziemlich unterbelichtet... ☹ Hoffe auf Hilfe,

PhotonX

Hi.

Eine allgemeingültige, leicht zu berechnende – also programmiertechnisch sinnvolle – Lösung kenne ich nicht.

Eine möglichkeit wäre sicherlich irgendwie rekursiv alle Zeilen und alle Spalten der Matrix A solange miteinander zu vertauschen, bis irgendwann (vielleicht) die Matrix B herauskommt. Das wäre also praktisch die Methode Brute-Force … ziemlich ineffizient.

PhotonX schrieb:

Nun möchte ich überprüfen, ob die beiden Matrizen ineinander übergeführt werden können. Zulässig sind folgende Operationen: Man darf die Reihenfolge der Spalten und/oder Zeilen beliebig ändern, aber die Zeilen und Spalten müssen als ganze "bewegt" werden. Und so sehen die Matrizen aus:

Willst du denn eine allgemeine Lösung oder nur den konkreten Fall? Wenn das die einzigen erlaubten Operationen sind, dann ist es im konkreten Fall nämlich einfach. Es geht nicht. 😉

Warum es nicht geht? Nun, wie du schon sagst hat jede Zeile genau 2 Einsen, daran wird sich auch bei noch so intensivem Vertauschen der Zeilen nichts ändern. Auch das Vertauschen von Spalten wird da nichts ausrichten können. Selbiges gilt übrigens auch für die Zahl der Einsen in jeder Spalte – wie sieht es mit denen eigentlich aus?

Genau eine Spalte hat 6 Einsen und das ist die letzte Spalte. Da sich auf keine andere Weise 6 Einsen in einer Spalte erzeugen lassen muss diese 15. Spalte also unverändert dort bleiben wo sie ist. Das einzige was noch zulässig wäre ist das Vertauschen der Zeilen. Da die Zeilen mit einer 1 in der letzten Spalte aber alle eindeutig sind, düfen auch die letzten 6 Zeilen nicht untereinander vertauscht werden.

Außerdem gibt es noch zwei Spalten mit jeweils 4 Einsen, nämlich die Spalten 13 und 14. Alle anderen Spalten enthalten genau 3 Einsen.

Wenn die Eins wandert, dann verschiebt sich eine Spalte mit 4 Einsen! Aus den beiden Spalten 13 und 14 werden auf diese Weise die Spalten 8 und 13 – die Frage ist also: lassen sich die Spalten 13 und 14, allein durch Vertauschen der Zeilen in die Spalten 8 und 13 verwandeln? Solange das nicht geht – und in diesem Fall geht es nicht – sind alle anderen Zeilen/Spalten komplett uninteressant. 😉

Gibt es eine Möglichkeit das mathematisch korrekt zu beweisen? Möglicherweise schon, und ich vermute dass es etwas mit linearen Abhängigkeiten zu tun haben könnte …

~jug

Meine Überlegung sieht wie folgt aus (mit einem besser überschaubaren Beispiel):

Man sortiert beide Matrizen nach einem Schema F, und wenn sie dann gleich sind, sind sie gleich, wenn nicht dann nicht, denn zum Sortieren bedient man sich nur der Verfahren (tausche Zeile)(tausche Spalte).

Beispiel:

1010
0011
1100

Regel 1: Zeilentausch. Setze die Zeile mit den meisten führenden Nullen* an den Anfang, sortiere den Rest solange ein Rest da ist. Habe 2 Zeilen gleich viele führende Nullen, so sortiere weiter nach den wenigsten Einsern, dann wieder nach vielen Nullen.

0010110011010
0010110100000

Man kann auch sagen: Fasse die Ziffernkette als binäre Zahl auf, und sortiere diese aufsteigend. Auf die Ausgangsmenge angewandt sieht das so aus:

0011
1010
1100

Regel 2: Das gleiche Verfahren, aber jetzt betrachten wir eine Spalte als Binärzahl, und sortieren analog:

0011
0101
1100

In diesem Fall sind wir fertig, weil ein weiteres Sortieren nach Regel 1 die Matrix nicht weiter verändert.

Die Frage ist aber, ob dies immer zu einem Ergebnis führt. Die traurige Antwort lautet: Nein.

10
01

Diese Matrix kann man immer weiter sortieren - aus 10,01 wird 01,10 und umgekehrt - immer so weiter. Man könnte natürlich eine Kopie der Vorversion behalten, und prüfen, ob man eine Version erzeugt hat, die man zuvor schon erzeugt hat, und dann könnte man per Konvention festlegen, daß dann der letzte Sortierschritt Regel 2 sein soll.

Gibt es vielleicht sogar zyklische Vertauschungen über mehr als zwei Schritte? Oh, ich weiß es nicht.

Gibt es vielleicht lokale Zyklen, d.h. ich kann aus einer Matrix A->A'->A->A->A' machen, aber mit einer anderen Vertauschung gerate ich in einen anderen Zyklus A->A#->A##->A###->A#, und die Schnittmenge der Zyklen ist leer? Oder die zweite Transformation endet gar nicht in einem Zyklus, und die Schnittmenge mit dem Zyklus ist dennoch leer? Ich denke nicht, aber wie beweisen? Also wenn man 2 Zeilen vertauscht - nicht nach der Regel 1, sondern willkürlich, und dann sortiert man nach Regel 1, dann erhält man das gleiche Ergebnis, wie wenn man sofort nach Zeilen sortiert. Ebenso, wenn man eine Spalte willkürlich vertauscht, bevor man die Spalten sortiert. Und außerdem gilt, daß eine Operation, die aus einem Spalten- und einem Zeilentausch besteht kommutativ ist, d.h.: M->s(i, j)->z(k,l) = M->z(k,l)->s(i,j). Daher nehme ich an, daß man einfach beide Matrizen sortieren kann, und wenn sie dann gleich sind sind sie überführbar. Ob es allgemein eine Lösung gibt - ich vermute ja. Wenn Du eine Matrix erzeugst, und die Einsen so gruppierst, daß für 2 Spalten alle Zeilen 0 sind, außer für die Zeilen p, und in p ist die eine besetzt, und in der zweiten Matrix die andere: {{{a 11.... b 1.1... c 1..1.. ... o ..11.. p 1....1}}} –– {{{a 11.... b 1.1... c 1..1.. ... o ..11.. p 1...1.}}} Vertausche die vorletzte Spalte mit der letzen, und voila!

@jug: Genial, das ist super! ☺ Ok, nachdem die beiden Matrizen nicht ineinander umgewandelt werden können, könnte meine Idee zumindest theoretisch sogar wirklich funktionieren.

Dann hab ich noch eine Frage zum Technischen: Angenommen, ich will den Computer Folgendes machen lassen: Eine solche Matrix nehmen (also auch eine, die nur aus Nullen und Einsen besteht und bei der in jeder Zeile immer zwei Einsen sind), sie dann auf unterschiedliche Arten modifizieren (also nicht so wie vorher mit dem Umordnen der Zeilen und Spalten, sondern anders, genauer hab ich's noch nicht, möchte erstmal sicher gehen, dass es überhaupt möglich ist), wobei es pro Matrix im Durchschnitt um die 5 bis 10 mal so viele Modifikationen gibt, wie die Matrix breit ist. Dann gibt es eine Anzahl an Matrizen, die bei diesen Modifikationen rausgekommen sind, die sollen dann nach ihren Abmessungen sortiert werden (die ändern sich bei den Modifikationen). Innerhalb einer Familie (in der lauter Matrizen gleicher Abmessungen sind), sollen dann alle Matrizen miteinander verglichen werden und anhand der Spaltensummen in Unterfamilien eingeteilt werden. Und dann soll in jeder Unterfamilie so wie oben beschrieben (bzw. gefragt ☺ ) geprüft werden, ob irgendwelche Matrizen durch Umstellen der Spalten und Reihen ineinander übergeführt werden können. Wenn dann zwei (oder mehr) solcher Matrizen gefunden werden, können sie als identisch angesehen werden und alle Duplikate gelöscht werden.

Dann sollen auf jede der übrig gebliebenen Matrizen wieder die Modifikationen vom Anfang angewandt werden und das Ganze wiederholt sich. Am Ende soll eine Tabelle rauskommen, in der drinsteht, wie viele Matrizen welcher Abmessungen rausgekommen sind. Ist das in annehmbarer Zeit und mit durchschnittlicher Hardware zu realisieren? 😇 Für den Duplikatencheck könnte man ja den Algorithmus von user unknown nehmen, der klingt für mich als Programmierlaie absolut genial. ☺

Was willst Du denn machen?

Also es ist so. ☺ Ich hab vor Kurzem eine Facharbeit über Polyeder geschrieben. Hab mich mit dem Thema schon vor der Facharbeit beschäftigt und will mich auch nach ihr weiter damit beschäftigen (das Thema ist einfach viel zu interessant und ich hab trotz nahender Abiprüfungen anscheinend zu viel Freizeit 😀). Die Fragestellung ist Folgende: Welche Kriterien muss ein Polyeder erfüllen, um geometrisch realisierbar zu sein? Dabei geht es mir nicht um Streckenlängen und Abstände sondern nur um die Anzahl der Ecken/Kanten/Flächen, ist also ein Problem aus der Topologie.

Die Idee ist Folgende: Man nehme ein Ausgangspolyeder - vorzugsweise ein Tetraeder - und wende dann bestimmte Prozesse an. Zwei der Prozesse hat Steinitz beschrieben: Eine Ecke abschneiden und eine Pyramide auf eine Fläche aufsetzen. Aber damit lassen sich nicht alle Polyeder erhalten. Ich hab mir ein paar weitere Prozesse überlegt und will prüfen, ob man mit ihnen alle Polyeder aus dem Tetraeder erhalten kann.

Das kann man natürlich nicht von Hand überprüfen. Also hab ich mir überlegt, wie man das von einem Programm durchrechnen lassen kann. Und da wurde mir der Tipp gegeben, Polyeder auf 2D-Graphen runterzubrechen und dann mithilfe der Graphentheorie weiterzumachen. Und das geht tatsächlich, weil jedem Polyeder eindeutig ein 2D-Graph zugeordnet werden kann. Umgekehrt kann zwar nicht jedem 2D-Graph ein Polyeder zugeordnet werden, aber die Pointe bei der Geschichte ist, dass man durch diese Prozesse von Steinitz sicher immer nur existierende Polyeder erhält, das heißt man muss sich keine Sorgen machen, dass man einen Graph bekommt, der keine Realisierung hat.

Auf jeden Fall hab ich dann beim Wiki über Inzidenzmatrizen. Und die eignen sich m. E. perfekt dafür, dieses Problem vom Computer "verstehen" zu lassen. Das Programm soll also so eine Inzidenzmatrix eines Ausgangspolyeders (Tetraeders) nehmen und dann die Steinitzschen Prozesse an allen möglichen Ecken und Flächen anwenden. Dann soll es schauen, ob ein Polyeder doppelt rausgekommen ist (zwei Matrizen, bei denen nur die Zeilen und Spalten verdreht sind, entsprechen dem gleichen Polyeder) und Duplikate löschen, damit mit ihnen nicht unnötig weitergearbeitet wird und damit sie später die Zählung der Polyeder pro Familie nicht beeinflussen. Dann werden wieder die Prozesse angewendet, dann wieder die Duplikate aussortiert, usw. Irgendwann wird dann das Programm abgebrochen (bei einer bestimmten maximalen Zahl von Ecken und/oder Kanten) und zählt nach, wie viele Polyeder in jeder Familie existieren. Und das will ich dann abgleichen mit dieser Tabelle. Die wurde auch mit einem Programm erstellt, aber ich *vermute*, dass dieses Programm nicht mit den Prozessen gearbeitet hat (leider versteh ich den Code nicht...). Wenn dann die gleichen Zahlen rauskommen, dann war die verwendete Kombination von Prozessen mit großer Wahrscheinlichkeit ausreichend, um alle möglichen Polyeder zu erhalten.

Eigentlich müsste man hier nicht den Computer rechnen lassen sondern einen hübschen mathematischen Beweis finden, aber mir sind einfach schon die Ideen ausgegangen. ☺

Interessant, aber Du gestattest, daß ich ein tieferes Eintauchen Dir überlasse. ☺

Ja, mit den Polyedergeschichten wollte ich eigentlich gar nicht anfangen. Aber du wolltest es ja wissen. ☺ Aber wenn wir mal bei den Matrizen bleiben: Wie realistisch wäre denn so ein Programm? Ich bin hier auf Anraten eines Mitglieds eines anderen Forums gerade dabei, ein Kriterium zu suchen, nach dem sich sofort aussagen lässt, ob zwei Matrizen sich ineinander überführen lassen und habe schon kleine Fortschritte gemacht: http://www.quantenforum.de/viewtopic.php?p=28026#p28026 Jetzt müsste man sich nur noch etwas für die Nuller- und Einser-Matrizen einfallen lassen, aber ich fürchte, das wird nicht einfach. ☹ Aber angenommen, es lässt sich ein relativ einfacher Algorithmus für diese Überprüfung finden, es gibt ja noch den ersten Teil des Programms (die Anwendung der Prozesse auf die Matrizen). Ein Prozess könnte zum Beispiel so aussehen (ich zitiere aus einer Mail, interessant ist eigentlich nur die Modifikation der Matrix und nicht die ganzen Polyedersachen):

So ein Prozess könnte dann so aussehen: Beispiel: Prozess P "Ecke abschneiden" angewendet auf ein Tetraeder:

Tetraeder (eine mögliche Matrix):

0|1234
_______
1|1100
2|0110
3|1010
4|1001
5|0101
6|0011

Die 4 Spalten entsprechen hier den 4 Ecken und die 6 Zeilen den 6 Kanten des Tetraeders. Eine Eins bedeutet, dass eine Ecke an eine Kante angrenzt, eine Null, dass sie es nicht tut. In jeder Zeile sind genau zwei Einsen, weil jede Kante von zwei Punkten begrenzt wird, die Einserzahl in einer Spalte entspricht der Zahl z_i der zusammenlaufenden Kanten in der betreffenden Ecke.

Wenn wir jetzt die Ecke 4 abschneiden, dann verschwindet die Spalte 4 und es kommen 3 zusätzliche Spalten (die neuen Punkte) und drei neue Reihen (die neuen Kanten) dazu.

0|123456
_________
1|110xxx
2|011xxx
3|101xxx
4|100xxx
5|010xxx
6|001xxx
7|xxxxxx
8|xxxxxx
9|xxxxxx

Wie füllt man aber die Kreuzchen auf? In den ersten drei Reihen kann man sie mit Nullen ausfüllen, weil da schon pro Zeile beide Einsen drin sind. Bei den ersten drei Spalten der Reihen 7 bis 9 kann man auch Nullen einfügen, weil in den Spalten schon je drei Einsen drin sind und das auch so bleiben muss (wenn man eine Ecke durch die Kantenmitten abschneidet, verändert sich ja nichts an den anderen Ecken). Also sieht es schon mal so aus:

0|123456
_________
1|110000
2|011000
3|101000
4|100xxx
5|010xxx
6|001xxx
7|000xxx
8|000xxx
9|000xxx

Jetzt sind noch zwei 3x3-Quadrate zu füllen. Im oberen muss pro Zeile eine Eins rein, im Unteren jeweils zwei (damit die zwei Einsen pro Zeile stimmen). Wie genau man hier auffüllen kann, weiß ich noch nicht, ist alles noch in Arbeit. ☺ Eine mögliche Auffüllung ist aber:

0|123456
_________
1|110000
2|011000
3|101000
4|100100
5|010010
6|001001
7|000110
8|000011
9|000101

Sorry, dass es alles so zusammengemixt ist, aber das Prblem ist, dass ich vom Programmieren absolut keine Ahnung habe aber dieses Problem unbedingt lösen will. ☺

Ich versuche das gerade selbst zu realisieren und bei der Gelegenheit etwas Python zu lernen. ☺ Es scheitert aber daran, eine Liste zu sortieren. Ich hab mal schön zusammengeschrieben, wie es funktionieren soll (siehe Anhang). Und hier ist mein erster Versuch, das in Python umzusetzen:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

def eckenrang(ecke):
        z = 0
        for i in range(0, len(ecke)):
                z = z + ecke[i]
        return z

def prozess_p3(polytop,eckennummer): # Abschneiden einer 3-Ecke
	if eckenrang(polytop[eckennummer]) == 3:
        # Zeilen sortieren, wie?!
	    del polytop[eckennummer] ## 1. Schritt, ausgewählte Spalte löschen
            for i in range(0,len(polytop)):
                polytop[i]=polytop[i]+[0,0,0] ## 2. Schritt
            polytop.extend([len(polytop[1])*[0]]) ############################
            polytop.extend([len(polytop[1])*[0]]) ## 3. Schritt, Nullen füllen 
            polytop.extend([len(polytop[1])*[0]]) ############################
            polytop[(len(polytop)-3)][0]=1 ###################################
            polytop[(len(polytop)-2)][1]=1 ## 3. Schritt, oberes Quadrat 
            polytop[(len(polytop)-1)][2]=1 ###################################
            polytop[(len(polytop)-3)][len(polytop[1])-1]=1 ###################
            polytop[(len(polytop)-3)][len(polytop[1])-2]=1 ##
            polytop[(len(polytop)-2)][len(polytop[1])-1]=1 ## 3. Schritt,
            polytop[(len(polytop)-2)][len(polytop[1])-3]=1 ## unteres Quadrat
            polytop[(len(polytop)-1)][len(polytop[1])-2]=1 ##
            polytop[(len(polytop)-1)][len(polytop[1])-3]=1 ###################
            return polytop

tetraeder=([[1,0,1,1,0,0],[1,1,0,0,1,0],[0,1,1,0,0,1],[0,0,0,1,1,1]]) # tetraeder[ecke][kante]

print(prozess_p3(tetraeder,3))

Man muss dazu sagen, dass meine Pythonkenntnisse gegen Null gehen (die Funktion da oben hab ich mir im Prinzip stückchenweise zusammengegoogelt), deswegen brauche ich evtl. ab und zu etwas länger, um ein Stück Code zu durchblicken. ☺

@PhotonX: Du solltest vielleicht erst einmal das Tutorial in der Python-Dokumentation durcharbeiten und schauen was es so für grundlegende Funktionen und Datenstrukturen gibt.

Dann wüsstest Du zum Beispiel, dass range(len(obj)) in einer for-Schleife ein "anti pattern" ist. Man kann in 99% der Fälle direkt über die Elemente einer Sequenz iterieren, ohne den Umweg über einen Index zu gehen. eckenrang() kann man viel kürzer schreiben:

1

eckenrang = sum

☺

Und es gilt (bei Listen) immer polytop[(len(polytop)-3)] == polytop[-3], da lässt sich also einiges kürzer schreiben. Und die Zeilen 16 bis 24 kann man mit einer Schleife sicher auch kompakter ausdrücken.

Zum Sortieren haben Listen eine sort()-Methode. Da gibt es auch die Möglichkeit eine Funktion anzugeben, die aus einem Element einen Sortierschlüssel berechnet, nach dem dann sortiert wird, falls die "natürliche" Sortierung nicht das gewünschte bringt.

Marc 'BlackJack' Rintsch schrieb:

@PhotonX: Du solltest vielleicht erst einmal das Tutorial in der Python-Dokumentation durcharbeiten und schauen was es so für grundlegende Funktionen und Datenstrukturen gibt.

Naja, ich hab mir das hier angeschaut: http://de.wikibooks.org/wiki/Python-Programmierung:_Datentypen_Operationen#Listen Die Python-Dokumentation versuch ich gleich zu verdauen. ☺

Dann wüsstest Du zum Beispiel, dass range(len(obj)) in einer for-Schleife ein "anti pattern" ist. Man kann in 99% der Fälle direkt über die Elemente einer Sequenz iterieren, ohne den Umweg über einen Index zu gehen.

Hmm, das hab ich noch nicht so ganz verstanden. Hier gab es das Thema ja schon mal und ich hab das mal analog versucht: {{{#!code python polytop2 = (spalte + [0,0,0] for spalte in polytop) }}} Aber als Ausgabe kommt: {{{ <generator object <genexpr> at 0x7f3b0ac32be0> }}} Also hab ich das erstmal mit der nicht eleganten Methode gelassen. ☺ Ok, hab jetzt geschnallt, wie das geht. 😀

eckenrang() kann man viel kürzer schreiben:

1	eckenrang = sum

☺

Oh, da hab ich wohl das Rad neu erfunden... Habs verbessert.

Und es gilt (bei Listen) immer polytop[(len(polytop)-3)] == polytop[-3], da lässt sich also einiges kürzer schreiben. Und die Zeilen 16 bis 24 kann man mit einer Schleife sicher auch kompakter ausdrücken.

Verbessert, aber vielleicht auch verschlimmbessert (sind ja doch mehr als eine Schleife geworden)...

Zum Sortieren haben Listen eine sort()-Methode. Da gibt es auch die Möglichkeit eine Funktion anzugeben, die aus einem Element einen Sortierschlüssel berechnet, nach dem dann sortiert wird, falls die "natürliche" Sortierung nicht das gewünschte bringt.

Das Problem ist, dass die Zeilen sortiert werden sollen, aber die Elemente der Liste sind ja Spalten.

Hier ist die verbesserte Version:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

def prozess_p3(polytop,eckennummer): # Abschneiden einer 3-Ecke
    if sum(polytop[eckennummer]) == 3:
        
        # Zeilen sortieren, wie?!
        
	del polytop[eckennummer] ## 1. Schritt, ausgewaehlte Spalte loeschen
        
        for spalte in polytop:
            spalte=spalte.extend([0,0,0]) ## 2. Schritt 
           
        polytop.extend([len(polytop[1])*[0]])
        polytop.extend([len(polytop[1])*[0]]) ## 3. Schritt 
        polytop.extend([len(polytop[1])*[0]])
        
        for i in range(3):
            polytop[-3+i][i]=1 ## 3. Schritt, oberes Quadrat 
            
        for i in range(1,4):
            for k in range(1,4):
                polytop[-i][-k]=1 ## 3. Schritt, unteres Quadrat
        for i in range(1,4):
            polytop[-i][-i]=0
            
        return polytop

tetraeder=([[1,0,1,1,0,0],[1,1,0,0,1,0],[0,1,1,0,0,1],[0,0,0,1,1,1]]) # tetraeder[ecke][kante]

print(prozess_p3(tetraeder,3))

Ok, ich hab das Problem etwas anders gelöst und noch einen zweiten Prozess geschrieben:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

#!/usr/bin/env python
# -*- coding: utf-8 -*-

def anbindung(polytop, ecke1, ecke2): # Überprüfe, ob zwei Ecken durch eine Kante verbunden sind
    for i in range(len(polytop[1])):
        w=polytop[ecke1][i]*polytop[ecke2][i]
        if w==1:
            return True
            break
        else:
            pass
    return False

def prozess_p3(polytop,ecke): # Abschneiden einer 3-Ecke
	if sum(polytop[ecke]) == 3: # Überprüfe, ob an der angegebenen Ecke drei Kanten zusammenlaufen
		for spalte in polytop:
			spalte=spalte.extend([0,0,0]) ## 2. Schritt 
		polytop.extend([len(polytop[1])*[0]]) ############################
		polytop.extend([len(polytop[1])*[0]]) ## 3. Schritt 
		polytop.extend([len(polytop[1])*[0]]) ############################
		for i in range(3):
			a=polytop[ecke].index(1)
			polytop[-(i+1)][a]=1
			polytop[ecke][a]=0
		del polytop[ecke] ## 1. Schritt, ausgewählte Spalte löschen
		for i in range(1,4):
			for k in range(1,4):
				polytop[-i][-k]=1
		for i in range(1,4):
			polytop[-i][-i]=0
		return polytop
	else:
		return polytop

def prozess_q3(polytop, ecke1, ecke2, ecke3): # Aufsetzen einer Dreieckspyramide auf eine Dreiecksfläche
    if anbindung(polytop, ecke1, ecke2) and anbindung(polytop, ecke2, ecke3) and anbindung(polytop, ecke1, ecke3): # Überprüfe, ob die angegebenen Ecken ein Dreieck bilden
        polytop.extend([len(polytop[1])*[0]])
        for spalte in polytop:
            spalte=spalte.extend([0,0,0])
        polytop[-1][-3:]=[1,1,1]
        polytop[ecke1][-1]=1
        polytop[ecke2][-2]=1
        polytop[ecke3][-3]=1
        return polytop
    else:
        return polytop
    
tetraeder=([[1,0,1,1,0,0],[1,1,0,0,1,0],[0,1,1,0,0,1],[0,0,0,1,1,1]]) # tetraeder[ecke][kante]

Aber jetzt hab ich ein ziemlich großes Problem, nämlich doppelte Ergebnisse auszusortieren. Da hat ja schon user unknown einen guten Algorithmus vorgeschlagen, allerdings sehe ich noch überhaupt nicht, wie man ihn implementieren könnte... Das eine Problem ist es, Spalten und Zeilen beliebig verschieben zu können (mit Spalten geht das, aber mit Zeilen?); das andere ist es, sie so verschieben zu lassen, dass immer die größte Binärzahl rauskommt (siehe Post von user unknown)...

Python ist eine wirklich schöne Sprache, aber ich würde auch nicht alles in Python machen.

Wenn Du viel mit Matricen arbeitest, würde ich Dir eher zu R raten. Dort gibt es einen dezidierten Matrix-Datentyp, mehrdimensionale Arrays und weitere hübsche Spielereien. Bei einer Matrix kannst Du bequem auf Spalten und Zeilen zugreifen, sie neu sortieren, etc.

Liebe Grüße
Fredo

@PhotonX: Nach einem return braucht man nichts mehr zu schreiben. Das break in anbindung() wird niemals erreicht. Und einen else-Zweig, in dem nur ein pass steht, kann man sich auch schenken.

Ist das eigentlich [rw]ichtig, dass Du immer len(polytop[1]) schreibst, statt len(polytop[0])? Wenn es eine rechteckige Matrix ist, dann sollten doch alle Zeilen gleich lang sein, und es wäre irgendwie verständlicher wenn man die erste Zeile dafür heranzieht, statt die zweite. Dann könnte man anbindung() so schreiben:

1
2
3
4
5
6

from itertools import izip

def hat_anbindung(polytop, ecke1, ecke2):
    """Überprüfe, ob zwei Ecken durch eine Kante verbunden sind.
    """
    return any(a * b == 1 for a, b in izip(polytop[ecke1], polytop[ecke2]))

Bei prozess_p3() kann man sich das else sparen, weil der Code dort auch am Ende vom if-Zweig ausgeführt wird. Der wird also in jedem Fall ausgeführt und kann deshalb einmal ans Ende der "Funktion" geschrieben werden. Da es aber eigentlich gar keine Funktion ist, die etwas neues, unabhängiges zurückgibt, hätte ich hier gar kein return verwendet. Das originale polytop wird ja verändert, dann braucht man keinen Rückgabewert. Gleiches gilt für prozess_q3().

Fredo: Die Denke bei Python war einfach die, dass es weit verbreitet ist (ergo viele Tutorials existieren und auch viele Forenmitglieder sich damit auskennen und helfen können 😉 ) und dass es ziemlich einfach sein soll. Und nachdem ich bisher noch überhaupt nicht programmieren kann, dachte ich, Python sei perfekt für den Einstieg. Aber kann gut sein, dass R besser für mein Anliegen geeignet ist. Das Blöde ist, dass man nach "R" so schlecht googeln kann... Ich bin mittlerweile zu Arch umgestiegen (man hat ja in den Sommerferien nichts zu tun 😉 ) und da hab ich bis jetzt nur ein Paket "r" finden können. Das entspricht wohl r-base aus den Ubuntu-Quellen - also nichts mit einem grafischen Editor und so. Nur die R-Konsole im Terminal. Und keine Ahnung, was man damit anstellen soll. ☺ Ich hab hier sowas gefunden: http://cran.r-project.org/doc/manuals/R-intro.html#Arrays-and-matrices Aber viel hilft mir das noch nicht... Erstmal: Wie schreibt man mit dem Ding überhaupt ein Programm? Es scheint ja sowas wie die Python Shell zu sein, oder?

@Marc: Ach schon wieder so dumme Fehler. 😕 len(polytop[0]) geht natürlich auch. Was macht denn dieses izip()? Das mit dem return ist so eine Sache, ich weiß noch nicht, wie das Hauptprogramm am Ende aussehen wird. Vermutlich wird prozess_xy(polytop) als polytop_xyz gespeichert. Da müssen natürlich noch die Prozess-Funktionen angepasst werden. Aber erstmal muss dieses Sortieren irgendwie klappen, damit Duplikate rausgefiltert werden...