Python Permutation

31.05.2016, 18:29

Dr.Java

Python Permutation

Hi.
Ich beschäftige mich grade mit Permutation bei Python,bzw. einer entsprechenden Aufgabe dazu. Und zwar sollte zunächst ein Programm erzeugt werden mit dem eine n Permutation erzeugt wird.

code:
1: 2: 3: 4: 5:	>>> sigma = (4, 3, 2, 1) >>> spam = [’s’, ’p’, ’a’, ’m’] >>> apply(sigma, spam) >>> spam [’m’, ’a’, ’p’, ’s’]

So sollte das ganze ungefähr am Ende aussehen.
Ich habe dann zunächst probiert ob das mit spam.sort(key=sigma) klappen würde ,allerdings erfolglos. Könnte mir jemand bitte auf die Sprünge helfen?

Vielen Dank

lg

31.05.2016, 22:40

Auf diesen Beitrag antworten »

eulerscheZahl

Wenn ich die Frage richtig verstanden habe:

code:
1:	spam = [spam[sigma[i]-1] for i in range(len(sigma))]

01.06.2016, 09:52

Auf diesen Beitrag antworten »

Dr.Java

Dann sage ich nochmals danke ,das ganze klappt einwandfrei. Aber fertig bin ich leider noch nicht ganz. Gibt es denn konkrete Befehle für Permutation bei Python ,mit denen dann auch so Sachen wie die Komposition zweier Permutationen oder die inverse einer Permutation ermittelt werden können?

lg

01.06.2016, 10:02

Auf diesen Beitrag antworten »

eulerscheZahl

Das weiß ich nicht auswendig, da hilft mich auch nur suchen.

01.06.2016, 11:23

Auf diesen Beitrag antworten »

Dr.Java

Danke für den Link und deine Hilfe, aber leider klappt die Funktion nicht ,wenn ich jetzt zum Beispiel sage perm=[2,3,1,4], ergibt das

code:
1: 2: 3: 4: 5:	File "<pyshell#12>", line 1, in <module> print(inv(s)) File "<pyshell#3>", line 4, in inv inverse[p] = i IndexError: list assignment index out of range

Ansonsten habe ich schon das Forum und diverse Websiten nach der Lösung für die Permutationsprobleme durchsucht,ich konnte bisher aber nichts konkretes finden,deswegen wollte ich hier nochmal fragen .

lg

01.06.2016, 14:44

Auf diesen Beitrag antworten »

eulerscheZahl

Mache aus perm=[2,3,1,4] das hier: perm=[1,2,0,3].
Natürlich kannst du auch den Code von stackoverflow so anpassen, dass der Offset rausgerechnet wird.

01.06.2016, 17:03

Auf diesen Beitrag antworten »

Dr.Java

Heißt das perm geht nur für spezielle Werte?

Und nochmal zur ursprünglichen Frage.Ich bin und war bemüht dein anfangs angegebenes Beispiel(dein Code funktioniert und ist richtig,ich habe es schon ausprobiert) zu einer Funktion zu generalisieren. Ich dachte auch zunächst das das gehen würde indem ich wie folgt vorgehen würde.

code:
1: 2: 3: 4:	def apply(s, lst): s=[s[t[i]-1] for i in range(len(t))] return s

Dann habe ich die Werte für Sigma und Spam definiert und das so eingeben

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

apply(sigma, spam)
Traceback (most recent call last):
  File "<pyshell#21>", line 1, in <module>
    apply(sigma,spam)
  File "C:\Users\Name\AppData\Local\Programs\Python\Python35-32\examples\permutationas.py", line 2, in apply
    s=[s[lst[i]-1] for i in range(len(lst))]
  File "C:\Users\Name\AppData\Local\Programs\Python\Python35-32\examples\permutationas.py", line 2, in <listcomp>
    s=[s[lst[i]-1] for i in range(len(lst))]
TypeError: unsupported operand type(s) for -: 'str' and 'int'

Das ist dann was dabei raus kam.
Interessanterweise stellte sich heraus das die Funktion wohl die Verkettung zweier Permutationen berechnen kann,immerhin wäre das damit erledigt.

Entschuldige bitte das Durcheinander.
lg

Edit: Hat sich erledigt. Ich musste die Variablen bei der Definition vertauschen. Aber das mit der inversen krieg ich immer noch nicht auf die Reihe,egal was ich mach,ich bekomm immer die Fehlermeldung.

02.06.2016, 16:53

Auf diesen Beitrag antworten »

Dr.Java

Entschuldigt den Doppelpost. Ich habe aber noch ein paar Probleme bei denen ich auf Granit stoße. Inzwischen habe ich es noch immer nicht geschafft die Funktion von StackOverflow zum laufen zu bringen,egal was ich versuche und ändere ,er gibt mir immer die Fehlermeldung aus.

Das andere Programm, zur Ermittlung zur Komposition zweier Permutationen sieht so aus (klappt so viel ich weiß,fehlerfrei)

code:
1: 2: 3:	def compose(s, t): s=[s[t[i]-1] for i in range(len(t))] return s

Ich möchte dann noch um die Ordnung der Permutation zu ermitteln die Funktion ein wenig umbauen. Die Ordnung wäre ja die Anzahl der Verknüpfungen mit sich selbst bis wieder die ursprüngliche Permutation rauskommt. Wäre es möglich einen Zähler oder ähnliches einzubauen ,der dann ermittelt wie oft man die Komposition verknüpfen muss? Das sollte am Ende dann so aussehen

code:
1: 2: 3: 4:	sigma = (2, 1, 4, 3) order(sigma) 2

Vielen Dank nochmal

lg

03.06.2016, 18:58

Auf diesen Beitrag antworten »

eulerscheZahl

Du musst ja auch eine Indexverschiebung machen, wenn du es mit [2,3,1,4] aufrufen willst.

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:

def inv(perm):
	inverse = [0] * len(perm)
	for i, p in enumerate(perm):
		inverse[p-1] = i+1
	return inverse

def compose(s, t):
	s=[s[t[i]-1] for i in range(len(t))]
	return s

def order(s):
	counter = 1
	current = compose(s, s)
	while any(s[i] != current[i] for i in range(len(s))):
		counter += 1
		current = compose(current, s)
	return counter

sigma = [2, 1, 4, 3]
inv(sigma) #[2, 1, 4, 3]
order(sigma) #2

04.06.2016, 18:23

Auf diesen Beitrag antworten »

Dr.Java

Wegen dem Index, ach so geht das , etwas ähnlich dachte ich mir auch fast.
Wegen dem Orderprogramm. Das ist natürlich eine gute Idee mit dem counter und der Integration der compose Funktion ,aber darauf zu kommen ist immer ziemlich schwierig. Ich kann mich nur wiederholen und nochmals bedanken für deine Hilfe, eulersche.

lg

Neue Frage »

Antworten »

Python Permutation

Verwandte Themen