기술
f(m, G)맵핑 m과 인수가 아닌 고유 한 음수가 아닌 정수 세트 / 목록을 인수로 받아들이 는 함수 를 작성하십시오 G.
m의 정수 쌍을의 G새 정수에 매핑해야합니다 G. ( G, m)는 유한 아벨 리아 그룹 을 형성한다고 보장 되지만, 어떤 요소라도 G정체성 일 수있다.
다음과 같은 중요한 정리가 있습니다.
f주요 능력 목록을 [p1, ... pn]오름차순으로 반환해야합니다.
예
-
f((a, b) → (a+b) mod 4, [0, 1, 2, 3])[4]매개 변수가 그룹 Z 4를 설명하므로 반환해야합니다 . -
f((a, b) → a xor b, [0, 1, 2, 3])[2, 2]매개 변수가 Z 2 × Z 2에 대해 동형 그룹을 설명하므로 반환해야합니다 . -
f((a, b) → a, [9])[]매개 변수가 사소한 그룹을 설명하므로을 반환해야합니다 . 즉, 제로시 클릭 기의 생성물. -
m다음과 같이 정의하십시오 .(a, b) → (a mod 3 + b mod 3) mod 3 + ((floor(a / 3) + floor(b / 3)) mod 3) * 3 + ((floor(a / 9) + floor(b / 9)) mod 9) * 9이어서
f(m, [0, 1, ..., 80])반환해야[3, 3, 9]이 그룹에 동형으로, Z 3 × Z 3 × Z 9
규칙
-
m함수 (또는 함수에 대한 함수 포인터)Int × Int → Int이거나의G × G새 요소에 대한 사전 매핑 쌍일 수G있습니다. -
f매개 변수를 반대 순서로 취할 수도 있습니다f(G, m). 즉, 구현할 수도 있습니다 . -
구현은 이론적 으로 임의로 큰 입력에 효과적이지만 실제로 효율적일 필요는 없습니다.
-
어떤 종류의 내장 사용에도 제한이 없습니다.
-
표준 코드 골프 규칙이 적용됩니다. 바이트 단위의 최단 코드가 이깁니다.
리더 보드
점수가 보드에 표시 되려면 다음 형식이어야합니다.
# Language, Bytes
var QUESTION_ID=67252,OVERRIDE_USER=3852;function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"http://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>답변
Matlab, 326 바이트
일부 그룹 이론에서는 아이디어가 매우 간단합니다. 여기서 TL; DR 그룹의 가능한 모든 요소 순서를 계산합니다. 그런 다음 특정 주요 전력 주문의 가장 큰 하위 그룹을 찾아 그룹에서 “요소 화”하고 헹구고 반복하십시오.
function r=c(h,l)
%factorize group order
N=numel(L);
f=factor(N);
P=unique(f); %prime factors
for k=1:numel(P);
E(k)=sum(f==P(k)); %exponents of unique factors
end;
%calculate the order O of each element
O=L*0-1;
l=L;
for k=2:N+1;
l=h(l,L);
O(l==L & O<0)=k-1
end;
%%
O=unique(O); % (optional, just for speedupt)
R=[];
% for each prime,find the highest power that
% divides any of the orders of the element, and
% each time substract that from the remaining
% exponent in the prime factorization of the
% group order
for p=1:nnz(P); % loop over primes
while E(p)>1; % loop over remaining exponent
for e=E(p):-1:1; % find the highest exponent
B=mod(O,P(p)^e)==0;
if any(B)
R=[R,P(p)^e]; % if found, add to list
O(B)=O(B)/(P(p)^e);
E(p)=E(p)-e;
break;
end;
end;
end;
if E(p)==1;
R=[R,P(p)];
end;
end;
r=sort(R)
입력 예 :
L = 0:3;
h=@(a,b)mod(a+b,4);
h=@(a,b)bitxor(a,b);
L = 0:80;
h=@(a,b)mod(mod(a,3)+mod(b,3),3)+mod(floor(a/3)+floor(b/3),3)*3+ mod(floor(a/9)+floor(b/9),9)*9;
골프 버전 :
function r=c(h,l);N=numel(L);f=factor(N);P=unique(f);for k=1:numel(P);E(k)=sum(f==P(k));end;O=L*0-1;l=L;for k=2:N+1;l=h(l,L);O(l==L&O<0)=k-1;end;R=[];for p=1:nnz(P);while E(p)>1;for e=E(p):-1:1;B=mod(O,P(p)^e)==0; if any(B);R=[R,P(p)^e]; O(B)=O(B)/(P(p)^e);E(p)=E(p)-e;break;end;end;end;if E(p)==1;R=[R,P(p)];end;end;r=sort(R)
답변
갭 , 159 111 바이트
GAP을 사용하면 곱셈표로 그룹을 간단하게 구성하고 그 불변량을 계산할 수 있습니다.
ai:= # the golfed version states the function w/o assigning it
function(m,G)
local t;
t:=List(G,a->List(G,b->Position(G,m(a,b))));
# t is inlined in the golfed version
return AbelianInvariants(GroupByMultiplicationTable(t));
end;
구 버전
제너레이터 G가있는 유한하게 표시된 그룹과 관계 a * b = m (a, b) (G의 모든 a, b)는 우리가 시작한 그룹 (G, m)입니다. 우리는 그것을 만들고 GAP을 사용하여 아벨 리아 불변량을 계산할 수 있습니다 :
ai:= # the golfed version states the function w/o assigning it
function(m,G)
local F,n,rels;
n:=Size(G);
F:=FreeGroup(n);
rels:=Union(Set([1..n],i->
Set([1..n],j->
F.(i)*F.(j)/F.(Position(G,m(G[i],G[j]))) ) ));
# rels is inlined in the golfed version
return AbelianInvariants(F/rels);
end;
예
m1:=function(a,b) return (a+b) mod 4; end;
# I don't feel like implementing xor
m3:=function(a,b) return 9; end;
m4:=function(a,b)
return (a+b) mod 3 # no need for inner mod
+ ((QuoInt(a,3)+QuoInt(b,3)) mod 3) * 3
+ ((QuoInt(a,9)+QuoInt(b,9)) mod 9) * 9;
end;
이제 우리는 할 수 있습니다 :
gap> ai(m1,[0..3]);
[ 4 ]
실제로 정수 목록을 사용하는 것으로 제한되지 않습니다. 올바른 도메인을 사용하면 일반적인 플러스를 사용할 수 있습니다.
ai(\+,List(Integers mod 4));
[ 4 ]
따라서 본질적으로 그룹이 2 요소로 필드 위의 2 차원 벡터 공간의 가산 그룹에 동형임을 사용하여 두 번째 예를 수행 할 수 있습니다.
gap> ai(\+,List(GF(2)^2));
[ 2, 2 ]
나머지 예는 다음과 같습니다.
gap> ai(m3,[9]);
[ ]
gap> ai(m4,[0..80]);
[ 3, 3, 9 ]
추가 비고
이전 버전에서 m은 G에 대한 그룹 구성을 정의 할 필요가 없었습니다. m (a, b) = m (a, c)라면, 그것은 단지 b = c라고 말합니다. 그래서 우리는 할 수 ai(m1,[0..5])있고ai(m3,[5..15]) . m이 G가 아닌 값을 반환하면 두 버전 모두 새 버전은이 경우 끔찍하게 실패합니다.
(G, m)이 아벨 리아식이 아닌 경우, 우리는 아벨 리아 식 버전에 대한 설명을 얻습니다.
gap> ai(\*,List(SymmetricGroup(4)));
[ 2 ]
이것은 AbelianInvariants일반적으로 사용되는 것입니다. 우리는 보통을 호출 AbelianInvariants(SymmetricGroup(4))합니다.
골프 버전
function(m,G)return AbelianInvariants(GroupByMultiplicationTable(List(G,a->List(G,b->Position(G,m(a,b))))));end