Pseudokod

@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

@lion137: mnożenia

Nindzia napisał(a):

@lion137: mnożenia

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

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

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ć:

Kopiuj

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.