Cycles of a permutation: Difference between revisions
Content added Content deleted
(Added Wren) |
(julia example) |
||
| Line 125: | Line 125: | ||
##return the signature of a permutation. |
##return the signature of a permutation. |
||
#Demonstrate how Alf and Betty can use this functionality in the scenario described above. Assume that Alf and Betty are novice programmers that have some famiiarity with your language. (i.e. Keep It Simple.) Provide the output from your demonstation code. |
#Demonstrate how Alf and Betty can use this functionality in the scenario described above. Assume that Alf and Betty are novice programmers that have some famiiarity with your language. (i.e. Keep It Simple.) Provide the output from your demonstation code. |
||
=={{header|Julia}}== |
|||
Normally, the Permutations.jl Julia package could be used, but equivalent non-library code is used instead, as specified in the task. |
|||
Note that the Alf and Betty's notation for cycles seems inverted compared to the syntax in Permutations.jl; printing of cycles |
|||
is therefore customizable in the code to either format, and the code is specified so as to duplicate the cycles as written in |
|||
the examples given in the task. |
|||
<lang julia>""" A Perm is a permutation in one-line form. `a` is a shuffled gapless 1-based range of Int. """ |
|||
struct Perm |
|||
a::Vector{Int} |
|||
function Perm(arr::Vector{Int}) |
|||
if sort(arr) != collect(1:length(arr)) |
|||
error("$arr must be permutation of 1-based integer range") |
|||
end |
|||
return new(arr) |
|||
end |
|||
end |
|||
""" Create an identity Perm for permutations of length n """ |
|||
Perm(n::Int) = Perm(1:n) |
|||
""" Create a Perm from its cycle vectors """ |
|||
function Perm(cycles::Vector{Vector{Int}}; addsingles = true) |
|||
elements = reduce(vcat, cycles) |
|||
if addsingles |
|||
for elem in filter(x -> !(x in elements), 1:maximum(elements)) |
|||
push!(cycles, [elem]) |
|||
push!(elements, elem) |
|||
end |
|||
end |
|||
a = collect(1:length(elements)) |
|||
sort!(elements) != a && error("Invalid cycles <$cycles> for creating a Perm") |
|||
for c in cycles |
|||
len = length(c) |
|||
for i in 1:len |
|||
j, n = c[i], c[mod1(i + 1, len)] |
|||
a[j] = n |
|||
end |
|||
end |
|||
return Perm(a) |
|||
end |
|||
""" length of Perm """ |
|||
Base.length(p::Perm) = length(p.a) |
|||
""" iterator interface for Perm """ |
|||
Base.iterate(p::Perm, state = 1) = state > length(p) ? nothing : (p[state], state + 1) |
|||
""" index into a Perm """ |
|||
Base.getindex(p::Perm, i::Int64) = p.a[i] |
|||
""" permutation signage for the Perm """ |
|||
Base.sign(p::Perm) = iseven(sum(c -> iseven(length(c)), permcycles(p))) ? 1 : -1 |
|||
""" order of permutation for Perm """ |
|||
order(p::Perm) = lcm(map(length, permcycles(p))) |
|||
""" Composition of Perm permutations with the * operator """ |
|||
function Base.:*(p1:: Perm, p2::Perm) |
|||
len = length(p1) |
|||
len != length(p2) && error("Permutations must be of same length") |
|||
return Perm([p1.a[p2.a[i]] for i in 1:len]) |
|||
end |
|||
""" inverse of a Perm """ |
|||
function Base.inv(p::Perm) |
|||
a = zeros(Int, length(p)) |
|||
for i in 1:length(p) |
|||
j = p.a[i] |
|||
a[j] = i |
|||
end |
|||
return Perm(a) |
|||
end |
|||
""" Get the Perm that functions to change one permutation result to another """ |
|||
transform(p1::Perm, p2::Perm) = inv(p1) * p2 |
|||
""" Get cycles of a Perm permutation as a vector of integer vectors, optionally with singles """ |
|||
function permcycles(p::Perm; includesingles = false) |
|||
pdict, cycles = Dict(enumerate(p.a)), Vector{Int}[] |
|||
for i in 1:length(p.a) |
|||
if (j = pop!(pdict, i, 0)) != 0 |
|||
c = [i] |
|||
while i != j |
|||
push!(c, j) |
|||
j = pop!(pdict, j) |
|||
end |
|||
push!(cycles, c) |
|||
end |
|||
end |
|||
return includesingles ? cycles : filter(c -> length(c) > 1, cycles) |
|||
end |
|||
""" Perm prints in cycle or optionally oneline format """ |
|||
function Base.print(io::IO, p::Perm; oneline = false, printsinglecycles = false, AlfBetty = false) |
|||
if length(p) == 0 |
|||
print(io, "()") |
|||
end |
|||
if oneline |
|||
width = length(string(maximum(p.a))) + 1 |
|||
print(io, "[ " * prod(map(n -> "$n ", p.a)) * "]") |
|||
else |
|||
cycles = permcycles(AlfBetty ? inv(p) : p, includesingles = printsinglecycles) |
|||
print(io, prod(c -> "(" * string(c)[begin+1:end-1] * ") ", cycles)) |
|||
end |
|||
end |
|||
""" Create a Perm from a string with only one of each of its letters """ |
|||
Perm(s::AbstractString) = Perm([findfirst(==(c), String(sort(unique(collect(s))))) for c in s]) |
|||
""" Create a Perm from two strings permuting first string to the second one """ |
|||
Perm(s1::AbstractString, s2::AbstractString) = Perm([findfirst(==(c), s1) for c in s2]) |
|||
""" Create a permuted string from another string using a Perm """ |
|||
permutestring(s::AbstractString, p::Perm) = String([s[i] for i in p.a]) |
|||
""" Given an iterable of equal length and a Perm, return a permuted vector of the iterable's elements """ |
|||
function permuted(iterable, p1::Perm) |
|||
p2 = Perm(iterable) |
|||
inttoitem = Dict(enumerate(iterable)) |
|||
return [inttoitem(i) for i in (p1 * p2).data] |
|||
end |
|||
function testAlfBettyPerms() |
|||
days = ["Mon", "Tue", "Wed", "Thu", "Fri", "Sat", "Sun"] |
|||
daystrings = ["HANDYCOILSERUPT", "SPOILUNDERYACHT", "DRAINSTYLEPOUCH", |
|||
"DITCHSYRUPALONE", "SOAPYTHIRDUNCLE", "SHINEPARTYCLOUD", "RADIOLUNCHTYPES"] |
|||
dayperms = [Perm(daystrings[mod1(i - 1, 7)], daystrings[i]) for i in 1:length(days)] |
|||
print("On Thursdays Alf and Betty should rearrange\ntheir letters using these cycles: ") |
|||
print(stdout, dayperms[4], AlfBetty = true) |
|||
println("\n\nSo that $(daystrings[3]) becomes $(daystrings[4])") |
|||
print("\nor they could use the one-line notation: ") |
|||
print(stdout, dayperms[4]; oneline = true) |
|||
print("\n\n\nTo revert to the Wednesday arrangement they\nshould use these cycles: ") |
|||
print(stdout, inv(dayperms[4]), AlfBetty = true) |
|||
print("\n\nor with the one-line notation: " ) |
|||
print(stdout, inv(dayperms[4]); oneline = true) |
|||
println("\n\nSo that $(daystrings[4]) becomes $(daystrings[3])") |
|||
println("\n\nStarting with the Sunday arrangement and applying each of the daily") |
|||
println("permutations consecutively, the arrangements will be:\n") |
|||
println(" "^6, daystrings[7], "\n") |
|||
for i in 1:length(days) |
|||
i == 7 && println() |
|||
println(days[i], ": ", permutestring(daystrings[mod1(i - 1, 7)], dayperms[i])) |
|||
end |
|||
Base.println("\n\nTo go from Wednesday to Friday in a single step they should use these cycles: ") |
|||
print(stdout, Perm(daystrings[3], daystrings[5]), AlfBetty = true) |
|||
println("\n\nSo that $(daystrings[3]) becomes $(daystrings[5])") |
|||
println("\n\nThese are the signatures of the permutations:\n\n Mon Tue Wed Thu Fri Sat Sun") |
|||
for i in 1:length(days) |
|||
j = i == 1 ? length(days) : i - 1 |
|||
print(lpad(sign(Perm(daystrings[mod1(i - 1, 7)], daystrings[i])), 4)) |
|||
end |
|||
println("\n\nThese are the orders of the permutations:\n\n Mon Tue Wed Thu Fri Sat Sun") |
|||
for i in 1:7 |
|||
print(lpad(order(dayperms[i]), 4)) |
|||
end |
|||
println("\n\nApplying the Friday cycle to a string 10 times:\n") |
|||
pFri, str = dayperms[5], "STOREDAILYPUNCH" |
|||
println(" $str\n") |
|||
for i in 1:10 |
|||
str = permutestring(str, pFri) |
|||
println(lpad(i, 2), " ", str, i == 9 ? "\n" : "") |
|||
end |
|||
end |
|||
testAlfBettyPerms() |
|||
</lang> {{out}} |
|||
<pre> |
|||
On Thursdays Alf and Betty should rearrange |
|||
their letters using these cycles: (2, 8, 7, 3, 11, 10, 15, 5, 14, 4) (9, 12, 13) |
|||
So that DRAINSTYLEPOUCH becomes DITCHSYRUPALONE |
|||
or they could use the one-line notation: [ 1 4 7 14 15 6 8 2 13 11 3 9 12 5 10 ] |
|||
To revert to the Wednesday arrangement they |
|||
should use these cycles: (2, 4, 14, 5, 15, 10, 11, 3, 7, 8) (9, 13, 12) |
|||
or with the one-line notation: [ 1 8 11 2 14 6 3 7 12 15 10 13 9 4 5 ] |
|||
So that DITCHSYRUPALONE becomes DRAINSTYLEPOUCH |
|||
Starting with the Sunday arrangement and applying each of the daily |
|||
permutations consecutively, the arrangements will be: |
|||
RADIOLUNCHTYPES |
|||
Mon: HANDYCOILSERUPT |
|||
Tue: SPOILUNDERYACHT |
|||
Wed: DRAINSTYLEPOUCH |
|||
Thu: DITCHSYRUPALONE |
|||
Fri: SOAPYTHIRDUNCLE |
|||
Sat: SHINEPARTYCLOUD |
|||
Sun: RADIOLUNCHTYPES |
|||
To go from Wednesday to Friday in a single step they should use these cycles: |
|||
(1, 10, 15, 7, 6) (2, 9, 14, 13, 11, 4, 8, 5, 12) |
|||
So that DRAINSTYLEPOUCH becomes SOAPYTHIRDUNCLE |
|||
These are the signatures of the permutations: |
|||
Mon Tue Wed Thu Fri Sat Sun |
|||
-1 -1 1 -1 -1 1 1 |
|||
These are the orders of the permutations: |
|||
Mon Tue Wed Thu Fri Sat Sun |
|||
18 30 12 30 10 33 40 |
|||
Applying the Friday cycle to a string 10 times: |
|||
STOREDAILYPUNCH |
|||
1 DNPYAOETISLCRUH |
|||
2 ORLSEPANTDIUYCH |
|||
3 PYIDALERNOTCSUH |
|||
4 LSTOEIAYRPNUDCH |
|||
5 IDNPATESYLRCOUH |
|||
6 TORLENADSIYUPCH |
|||
7 NPYIAREODTSCLUH |
|||
8 RLSTEYAPONDUICH |
|||
9 YIDNASELPROCTUH |
|||
10 STOREDAILYPUNCH |
|||
</pre> |
|||
=={{header|Quackery}}== |
=={{header|Quackery}}== |
||