Pseudokod

0

Cześć, mam zadanie na algebrze, żeby w pseudokodzie zapisać dane permutacje:

  • x^2y^-1

  • x^-1y^3

  • x^ −1 y^−2

Dla podpuktu drugiego to wygląda tak:

for i=1 to n
z[ x [ i ] ] <- i

for i=1 to n 
s[ i ] <- y[ y[ y[ i ] ] ] 

for i = 1 to n 
w [ i ] <- z[ s [ i ] ]

Mógłby ktoś mi wytłumaczyć w prosty sposób - krok po kroku - jak to działa?

EDIT: Chodzi o permutacje z tego filu (około 9 minuty) ( ).
Treść zadania: Proszę napisać algorytm, który dla danych permutacji x, y należących do Sn (przedstawionych w zwykły sposób w odpowiednich tablicach) oblicza permutację x^-1y^-2.

0

@lion137: x do potęgi -1 oznacza permutację odwrotną a y do potęgi -2 oznacza permutację odwrotną i jeszcze podniesioną do potęgi 2

0

@lion137: mnożenia

0
Nindzia napisał(a):

@lion137: mnożenia

@lion137: jakbym wiedział to bym nie pytał o to na forum ;)

2

Nie ma pewności, jak te permutacje przedstawić, ale temat dość ciekawy. Po pierwsze primo, nie ma sensu "ciągnąć" za sobą tego rzędu indeksów, logicznie jest przedstawić permutację jako tablicę o długości n:
[3, 2, 1] - to oznacza 1 -> 3, 2 -> 2, 3 -> 1.
Po drugie primo, najlepiej jest stworzyć dwie funkcje: mnożącą permutacje i odwracającą permutację; wtedy te różne wyrażenia, będzie można z tych dwóch skomponować:

fun mult_perm(x, y):
	out_perm = []
	for i = 1 to length(y):
		out_perm.append(x[y[i]])
	return out_perm

fun rev_perm(x):
	out_perm = [0] * length(x)
	for i = 1 to length(x):
		out_perm[x[i]] = i
	return out_perm

fun sol1(x, y):
	return mult_perm(mult_perm(x, x), rev_perm(y))

Rozwiązanie pierwszego zadania wygląda akurat tak (funkcja sol1). out_perm.append(...) w pierwszym, to dodanie elementu do końca tablicy. Proof of concept w Pythonie (Wciśnij run). Permutacja najpierw pomnożona przez siebie, potem odwrócenie permutacji identycznościowej, to ta sama permutacja, co tłumaczy wynik trzeciego print. Tutaj permutacje nie idą od 1 do n, tylko od 0 do n - 1.
https://repl.it/repls/NecessaryGlamorousPi

0
lion137 napisał(a):

Nie ma pewności, jak te permutacje przedstawić, ale temat dość ciekawy. Po pierwsze primo, nie ma sensu "ciągnąć" za sobą tego rzędu indeksów, logicznie jest przedstawić permutację jako tablicę o długości n:
[3, 2, 1] - to oznacza 1 -> 3, 2 -> 2, 3 -> 1.
Po drugie primo, najlepiej jest stworzyć dwie funkcje: mnożącą permutacje i odwracającą permutację; wtedy te różne wyrażenia, będzie można z tych dwóch skomponować:

fun mult_perm(x, y):
	out_perm = []
	for i = 1 to length(y):
		out_perm.append(x[y[i]])
	return out_perm

fun rev_perm(x):
	out_perm = [0] * length(x)
	for i = 1 to length(x):
		out_perm[x[i]] = i
	return out_perm

fun sol1(x, y):
	return mult_perm(mult_perm(x, x), rev_perm(y))

Rozwiązanie pierwszego zadania wygląda akurat tak (funkcja sol1). out_perm.append(...) w pierwszym, to dodanie elementu do końca tablicy. Proof of concept w Pythonie (Wciśnij run). Permutacja najpierw pomnożona przez siebie, potem odwrócenie permutacji identycznościowej, to ta sama permutacja, co tłumaczy wynik trzeciego print. Tutaj permutacje nie idą od 1 do n, tylko od 0 do n - 1.
https://repl.it/repls/NecessaryGlamorousPi

No właśnie problem jest w tym, że nie sposób to przedstawić w formie działającego programu komputerowego - bo z tym też raczej nie miałbym problemu, tylko jestem na 3 roku studiów informatyki (zaczynam ostatni, 7 semestr w październiku) i niedługo mam poprawkę waruna z algebry i muszę go zdać, a takie zadanie to jedno z wielu, które najprawdopodobniej się pojawi, napisać w pseudokodzie na kartce algorytm, który liczy takie permutacje. Na szczęście już mniej więcej obadałem temat i chyba rozumiem. Jakby ktoś miał coś wartościowego do dodania to proszę się nie krępować. @lion137 - mimo wszystko dzięki za pomoc.

1 użytkowników online, w tym zalogowanych: 0, gości: 1