Cycles of a permutation: Difference between revisions

Line 342:

with javascript_semantics

~~function~~ ~~smallestFirst~~(~~sequence~~ cycle<span~~ style~~="color~~: ~~#0000FF;">)

requires("1.0.2") -- (tagstart)

⚫

function smallest_first(sequence cycle)

-- Rearrange a cycle so the lowest element is first.

integer mdx = smallest(cycle,true)

return cycle[mdx..$]&cycle[1..mdx-1]

return cycle[mdx..$] & cycle[1..mdx-1]

end function

function ~~oneLineToString~~(sequence ol)

function one_line_to_string(sequence one_line)

-- Converts a list in one line notation to a space separated string.

return join(ol," ",fmt:="%d")

return join(one_line," ",fmt:="%d")

end function

function ~~cyclesToString~~(sequence cycles)

function cycles_to_string(sequence cycles)

-- Converts a list in cycle notation to a string where each cycle

-- is space separated and enclosed in parentheses.

⚫

return join(apply(true,join,{cycles,{" "},{" "},{"%d"}}),fmt:="(%s)")

⚫

~~sequence~~ ~~cycles2~~ = {}

⚫

for ~~cycle~~ in ~~cycles~~ do

⚫

~~cycles2~~ = ~~append~~(~~cycles2~~,~~"("~~ & ~~join~~(~~cycle~~,~~fmt~~:="%d") & ")")

end for

⚫

~~return~~ ~~join~~(~~cycles2~~)

end function

function ~~oneLineNotation~~(~~string~~ s, t)

function one_line_notation(sequence s, t)

-- Returns a list in one line notation derived from two strings s and t.

~~sequence~~ ~~res~~ = ~~repeat~~(~~0,15~~)

integer l = length(s)

for i=1 to 15 do res~~[i]~~ = ~~find~~(t~~[i]~~,s)~~ end for~~

sequence res = repeat(0,l)

for i=15 to 1 by -1 do

for i=1 to l do res[i] = find(t[i],s) end for

⚫

for i=l to 1 by -1 do

if res[i]!=i then exit end if

res=res[1..-2]

res = res[1..-2]

end for

return res

end function

function ~~cycleNotation~~(string s, t)

function cycle_notation(string s, t)

-- Returns a list in cycle notation derived from two strings s and t.

sequence used = repeat(false,15),

sequence used = repeat(false,length(s)),

cycles = {}

for i=1 to 15 do

for i=1 to length(used) do

if not used[i] then

⚫

~~sequence~~ ~~cycle~~ = {}

used[i] = true

integer ix = find(s[i],t)

if i!=ix then

if ix!=i then

cycle &= i

sequence cycle = {i}

while true do

cycle &= ix

used[ix] = true

ix = find(s[ix],t)

if ~~cycle~~~~[1]=~~=ix then

if ix=i then

cycle = ~~smallestFirst~~(cycle)

cycle = smallest_first(cycle)

cycles = append(cycles,cycle)

exit

Line 401:

Line 398:

end function

function ~~oneLineInverse~~(sequence ~~oneLine~~)

function one_line_inverse(sequence one_line)

-- Converts a list in one line notation to its inverse.

~~string~~ s = ~~"ABCDEFGHIJKLMNO"~~, t ~~= s~~

integer l = length(one_line)

~~for~~ i=1 to ~~length~~(~~oneLine~~) ~~do~~

string s = repeat(' ',l),

~~<span~~ ~~style="color:~~ ~~#000000;">s<span~~ ~~style="color: #0000FF;">[~~~~i]~~ = ~~oneLine~~[i]+~~'A'~~~~-1~~

t = tagstart('A',l)

⚫

for i=1 to l do

⚫

s[i] = one_line[i]+'A'-1

end for

return ~~oneLineNotation~~(s, t)

return one_line_notation(s,t)

end function

function ~~cycleInverse~~(sequence cycles)

function cycle_inverse(sequence cycles)

-- Converts a list of cycles to its inverse.

sequence cycles2 = repeat(0,length(cycles))

Line 420:

Line 419:

end function

function ~~oneLinePermute~~(string s, sequence perm)

function one_line_permute(string s, sequence perm)

-- Permutes a string using perm in one line notation.

string t = s

for i=1 to length(perm) do t[i] = s[perm[i]] end for

return t

--alternative one-liner:

-- return reinstate(s,tagset(length(perm)),extract(s,perm))

end function

function ~~cyclePermute~~(string s, sequence cycles)

function cycle_permute(string s, sequence cycles)

-- Permutes a string using perm in cycle notation.

sequence t = ~~repeat("",~~~~15)~~

sequence t = s

for cycle in cycles do

for i=1 to length(cycle)-1 do

Line 436:

Line 437:

t[cycle[1]] = s[cycle[$]]

end for

~~for~~ ~~i=1 to 15 do~~

return t

⚫

if t[i]="" ~~then~~ t[i] = s[i] end if

end for

⚫

return ~~join~~(t,"")

end function

function ~~cycleCombine~~(sequence cycles1, cycles2)

function cycle_combine(sequence cycles1, cycles2)

// Returns a single perm in cycle notation resulting

// from applying cycles1 first and then cycles2.

~~string~~ s = "~~ABCDEFGHIJKLMNO~~",

integer m = max(max(flatten(cycles1)),

~~<span~~ ~~style="color:~~ ~~#000000;">t~~ ~~<span~~ ~~style="color:~~ ~~#0000FF;">=~~ ~~cyclePermute~~(s, cycles1)

max(flatten(cycles1)))

t = ~~cyclePermute~~(t, ~~cycles2~~)

string s = tagstart('A',m),

~~return~~ ~~cycleNotation~~(s, t)

t = cycle_permute(s, cycles1)

t = cycle_permute(t, cycles2)

⚫

return cycle_notation(s, t)

end function

function ~~oneLineToCycle~~(sequence ~~oneLine~~)

function one_line_to_cycle(sequence one_line)

// Converts a list in one line notation to cycle notation.

~~string~~ s = ~~"ABCDEFGHIJKLMNO"~~, t ~~= s~~

integer l = length(one_line)

~~for~~ i=1 to ~~length~~(~~oneLine~~)~~ do~~

string s = tagstart('A',l),

~~<span~~ ~~style="color:~~ ~~#000000;">t<span~~ ~~style="color: #0000FF;">[~~~~i]~~ = ~~oneLine~~[i]+~~'A'~~~~-1~~

t = repeat(' ',l)

⚫

for i=1 to l do

⚫

t[i] = one_line[i]+'A'-1

end for

return ~~cycleNotation~~(s, t)

return cycle_notation(s, t)

end function

function ~~cycleToOneLine~~(sequence cycles)

function cycle_to_one_line(sequence cycles)

-- Converts a list in cycle notation to one line notation.

string s = "~~ABCDEFGHIJKLMNO~~",

string s = tagstart('A',max(flatten(cycles))),

t = ~~cyclePermute~~(s, cycles)

t = cycle_permute(s, cycles)

return ~~oneLineNotation~~(s, t)

return one_line_notation(s, t)

end function

function ~~order~~(sequence cycles)

function cycle_order(sequence cycles)

-- Returns the order of a permutation.

return lcm(apply(cycles,length))

end function

function ~~signature~~(sequence cycles)

function cycle_signature(sequence cycles)

-- Returns the signature of a permutation.

return even(sum(apply(apply(cycles,length),even)))*2-1

end function

constant ~~letters~~ = {

constant DAYS = {

~~"HANDYCOILSERUPT"~~, ~~// Monday~~

MON := "HANDYCOILSERUPT",

~~"SPOILUNDERYACHT"~~, ~~// Tuesday~~

TUE := "SPOILUNDERYACHT",

~~"DRAINSTYLEPOUCH"~~, ~~// Wednesday~~

WED := "DRAINSTYLEPOUCH",

~~"DITCHSYRUPALONE"~~, ~~// Thursday~~

THU := "DITCHSYRUPALONE",

~~"SOAPYTHIRDUNCLE"~~, ~~// Friday~~

FRI := "SOAPYTHIRDUNCLE",

~~"SHINEPARTYCLOUD"~~, ~~// Saturday~~

SAT := "SHINEPARTYCLOUD",

~~"RADIOLUNCHTYPES"~~ ~~// Sunday~~

SUN := "RADIOLUNCHTYPES"

}

printf(1,"On Thursdays Alf and Betty should rearrange their letters using these cycles:\n")

sequence ~~cycles~~ = ~~cycleNotation~~(~~letters~~~~[3]~~,~~ letters[~~4])

sequence cycle_wt = cycle_notation(WED,THU)

printf(1,"%s\n",{~~cyclesToString~~(~~cycles~~)})

printf(1,"%s\n",{cycles_to_string(cycle_wt)})

printf(1,"So that %s becomes %s\n\n",{~~letters~~~~[3]~~,~~cyclePermute~~(~~letters~~~~[3]~~, ~~cycles~~)})

printf(1,"So that %s becomes %s\n\n",{WED,cycle_permute(WED,cycle_wt)})

sequence ~~oneLine~~ = ~~cycleToOneLine~~(~~cycles~~)

sequence one_line = cycle_to_one_line(cycle_wt)

assert(~~oneLineToCycle~~(~~oneLine~~)==~~cycles~~)

assert(one_line_to_cycle(one_line)==cycle_wt)

printf(1,"Or they could use the one line notation:\n%s\n\n",{~~oneLineToString~~(~~oneLine~~)})

printf(1,"Or they could use the one line notation:\n%s\n\n",{one_line_to_string(one_line)})

printf(1,"To revert to the Wednesday arrangement they should use these cycles:\n")

~~sequence~~ ~~cycles2~~ = ~~cycleInverse~~(~~cycles~~)

printf(1,"%s\n\n",{cycles_to_string(cycle_inverse(cycle_wt))})

⚫

~~printf~~(1,~~"%s\n\n"~~,{~~cyclesToString~~(~~cycles2~~~~)})~~

printf(1,"Or with the one line notation:\n")

sequence ~~oneLine2~~ = ~~oneLineInverse~~(~~oneLine~~)

sequence one_line2 = one_line_inverse(one_line)

printf(1,"%s\n",~~oneLineToString~~(~~oneLine2~~))

printf(1,"%s\n",one_line_to_string(one_line2))

printf(1,"So that %s becomes %s\n\n",{~~letters~~~~[4]~~,~~oneLinePermute~~(~~letters~~~~[4]~~, ~~oneLine2~~)})

printf(1,"So that %s becomes %s\n\n",{THU,one_line_permute(THU,one_line2)})

printf(1,"Starting with the Sunday arrangement and applying each of the daily arrangements\n")

printf(1,"consecutively, the arrangements will be:\n\n")

~~constant~~ ~~days~~ = ~~{"Mon"~~, "~~Tue"<span~~ ~~style="color:~~ ~~#0000FF;">,~~ ~~<span~~ ~~style="color:~~ ~~#008000;">"Wed~~", "Thu", "Fri", "Sat", "Sun"}

printf(1," %s\n\n",{(SUN)})

~~printf~~~~<span~~ ~~style="color: #0000FF;">(~~1,~~<span~~ ~~style="color: #008000;">" %s\n\n"~~,{(~~letters~~[~~<span~~ ~~style="color: #000000;">7~~])})

sequence signatures = {}, orders = {}

~~for~~ j=1 to 7 do

integer yesterday = length(DAYS)

~~string~~ cr = ~~iff~~~~<span~~ ~~style="color: #0000FF;">(~~j~~<span~~ ~~style="color: #0000FF;">>=~~6?~~"\n"~~:~~<span~~ ~~style="color: #008000;">""~~)

for today=1 to length(DAYS) do

~~integer~~ i = ~~iff~~(j=1~~?7~~~~<span~~ ~~style="color: #0000FF;">:~~j-1)

string td = DAYS[today], yd = DAYS[yesterday]

sequence ol = ~~oneLineNotation~~(~~letters~~~~[i]~~, ~~letters~~~~[j]~~)

sequence ol = one_line_notation(yd,td),

~~<span~~ ~~style="color:~~ ~~#7060A8;">printf<span~~ ~~style="color:~~ ~~#0000FF;">(<span~~ ~~style="color:~~ ~~#000000;">1<span~~ ~~style="color:~~ ~~#0000FF;">,<span~~ ~~style="color: #008000;">"%s: %s%s\n"~~,{~~<span~~ ~~style="color: #000000;">days~~~~[j~~~~<span~~ ~~style="color: #0000FF;">],~~~~oneLinePermute~~(~~letters[i], ol~~),cr})

cy = cycle_notation(yd,td)

⚫

printf(1,"%s: %s\n",{td,one_line_permute(yd,ol)})

⚫

if today>=find(SAT,DAYS) then printf(1,"\n") end if

⚫

signatures &= cycle_signature(cy)

⚫

orders &= cycle_order(cy)

⚫

yesterday := today

end for

printf(1,"To go from Wednesday to Friday in a single step they should use these cycles:\n")

sequence ~~cycles3~~ = ~~cycleNotation~~(~~letters~~~~[4]~~,~~ letters[~~5]),

sequence cycles_tf = cycle_notation(THU,FRI),

~~cycles4~~ = ~~cycleCombine~~(~~cycles~~, ~~cycles3~~)

cycles_wf = cycle_combine(cycle_wt,cycles_tf)

printf(1,"%s\n",{~~cyclesToString~~(~~cycles4~~)})

printf(1,"%s\n",{cycles_to_string(cycles_wf)})

printf(1,"So that %s becomes %s\n\n",{~~letters~~~~[3]~~,~~cyclePermute~~(~~letters~~~~[3]~~, ~~cycles4~~)})

printf(1,"So that %s becomes %s\n\n",{WED,cycle_permute(WED,cycles_wf)})

~~sequence~~ ~~signatures~~ = ~~{}, orders = {}~~

constant FMT = """

These are the %s of the permutations:

⚫

for j=1 to 7 do

Mon Tue Wed Thu Fri Sat Sun

⚫

~~<span~~ ~~style="color:~~ ~~#004080;">integer~~ i = ~~iff~~(~~<span~~ ~~style="color: #000000;">j~~=1 ? 7 : j-1~~)~~

%s

⚫

~~sequence~~ cy = ~~cycleNotation~~(~~letters~~[i], ~~letters~~[~~j])~~

signatures &= signature(cy)

⚫

~~orders~~ &= ~~order~~(cy)

end for

⚫

~~printf~~(1,"~~These~~ ~~are~~ ~~the~~ ~~signatures of the permutations~~:\n")

⚫

printf(1," %s\n %s\n\n",{~~join(~~~~days~~),~~join~~(~~signatures~~,~~fmt:="%2d "~~)})

"""

printf(1,"These are the orders of the permutations:\n")

printf(1,~~" %s\n %s\n\n"~~,{~~join(days~~),join(~~orders~~,fmt:="%3d")})

printf(1,FMT,{"signatures",join(signatures,fmt:="%2d ")})

printf(1,FMT,{"orders",join(orders,fmt:="%3d")})

printf(1,"Applying the Friday cycle to a string 10 times:\n\n")

Line 541:

Line 542:

printf(1," %s\n\n",{prev})

for i=1 to 10 do

~~string~~ cr = ~~iff~~(i>=~~9?"\n":""~~)

prev = cycle_permute(prev,cycles_tf)

~~prev~~ = ~~cyclePermute~~(~~prev~~, ~~cycles3~~)

printf(1,"%2d %s\n",{i,prev})

~~printf~~(1,"~~%2d~~ ~~%s%s\n~~",{i,~~prev~~,cr})

if i>=9 then printf(1,"\n") end if

end for

Output identical to Julia/Wren

=={{header|Python}}==