수학에서, 차수 n 의 순열 σ 는 정수 1 … n 에서 그 자체 까지의 형용 함수입니다 . 이 목록 :
2 1 4 3
나타내는 순열 σ 되도록 σ (1) (2) = σ (2) = 1, σ (3) = 4, 및 σ (4) = 3.
순열의 제곱근 σ는 자체에 적용 할 때, 부여하는 순열 σ . 예를 들어, 2 1 4 3
제곱근은 τ = 3 4 2 1
입니다.
k 1 2 3 4
τ(k) 3 4 2 1
τ(τ(k)) 2 1 4 3
모든 1≤k≤n에 대해 τ ( τ (k)) = σ (k) 이기 때문이다 .
입력
순열을 나타내는 1과 n 사이 의 n > 0 정수 목록 . 순열에는 항상 제곱근이 있습니다.
입력과 출력이 일치 하는 한 0 … n-1 목록을 대신 사용할 수 있습니다 .
산출
순열의 제곱근이며 배열입니다.
제한 사항
알고리즘은 다항식 시간으로 n 에서 실행해야합니다 . 즉, 모든 n을 반복 할 수는 없습니다 ! 차수 n의 순열 .
모든 내장이 허용됩니다.
테스트 사례 :
많은 입력에 여러 개의 가능한 출력이 있습니다.
2 1 4 3
3 4 2 1
1
1
3 1 2
2 3 1
8 3 9 1 5 4 10 13 2 12 6 11 7
12 9 2 10 5 7 4 11 3 1 13 8 6
13 7 12 8 10 2 3 11 1 4 5 6 9
9 8 5 2 12 4 11 7 13 6 3 10 1
답변
펄, 124122 바이트
에 +3 포함 -alp
STDIN에서 1 기반 순열로 실행하십시오.
rootperm.pl <<< "8 3 9 1 5 4 10 13 2 12 6 11 7"
rootperm.pl
:
map{//;@{$G[-1]^$_|$0{$_}}{0,@G}=(@G=map{($n+=$s{$_=$F[$_-1]}++)?():$_}(0+$',0+$_)x@F)x2,%s=$n=0for@F}@F;$_="@0{1..@F}"
복잡도는 O (n ^ 3)입니다
답변
수학, 165167 바이트
명명되지 않은 함수.
PermutationList[Cycles@Join[Riffle@@@#~(s=Select)~EvenQ@*(l=Length)~SortBy~l~Partition~2,#[[Mod[(#+1)/2Range@#,#,1]&@l@#]]&/@#~s~OddQ@*l]&@@PermutationCycles@#,l@#]&
반 ungolfed :
PermutationList[
Cycles@Join[
Riffle@@@Partition[SortBy[Select[#,EvenQ@*Length],Length], 2],
#[[Mod[(Length@#+1)/2Range@Length@#,Length@#,1]]]& /@ Select[#,OddQ@*Length]
]& @@ PermutationCycles @ #,
Max@#
]&
답변
프롤로그-69 자
p([],_,[]). p([H|T],B,[I|U]):-p(T,B,U),nth1(H,B,I). f(X,Y):-p(Y,Y,X).
설명:
permutate([], _, []). % An empty permutation is empty
permutate([X|Xs], List, [Y|Ys]) :- % To permutate List
permutate(Xs, List, Ys), % Apply the rest of the permutation
nth1(X, List, Y). % Y is the Xth element of List
root(Permutation, Root) :- % The root of Permutation
permutate(Root, Root, Permutation). % Applied to itself, is Permutation