Cycles of a permutation: Difference between revisions
Added Wren
Thundergnat (talk | contribs) m (Thundergnat moved page Cycles of a Permutation to Cycles of a permutation: Capitalization policy) |
(Added Wren) |
||
Line 546:
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|Wren}}==
{{libheader|Wren-math}}
{{libheader|Wren-fmt}}
I've tried to stick to Alf and Betty's various conventions throughout, particularly when printing anything.
I've also stuck rigidly to the Quackery entry's examples for ease of comparison.
<lang ecmascript>import "./math" for Int
import "./fmt" for Fmt
/*
It's assumed throughout that string arguments are always 15 characters long
and consist of unique upper case letters.
*/
class PC {
// Private method to shift a cycle one place to the left.
static shiftLeft_(cycle) {
var c = cycle.count
var first = cycle[0]
for (i in 1...c) cycle[i-1] = cycle[i]
cycle[-1] = first
}
// Private method to arrange a cycle so the lowest element is first.
static smallestFirst_(cycle) {
var c = cycle.count
var min = cycle[0]
var minIx = 0
for (i in 1...c) {
if (cycle[i] < min) {
min = cycle[i]
minIx = i
}
}
if (minIx == 0) return
for (i in 1..minIx) shiftLeft_(cycle)
}
// Converts a list in one line notation to a space separated string.
static oneLineToString(ol) { ol.join(" ") }
// Converts a list in cycle notation to a string where each cycle is space separated
// and enclosed in parentheses.
static cyclesToString(cycles) {
var cycles2 = []
for (cycle in cycles) cycles2.add("(" + cycle.join(" ") + ")")
return cycles2.toString
}
// Returns a list in one line notation derived from two strings s and t.
static oneLineNotation(s, t) {
var res = List.filled(15, 0)
for (i in 0..14) res[i] = s.indexOf(t[i]) + 1
for (i in 14..0) {
if (res[i] != i + 1) break
res.removeAt(i)
}
return res
}
// Returns a list in cycle notation derived from two strings s and t.
static cycleNotation(s, t) {
var used = List.filled(15, false)
var cycles = []
for (i in 0..14) {
if (used[i]) continue
var cycle = []
used[i] = true
var ix = t.indexOf(s[i])
if (i == ix) continue
cycle.add(i+1)
while (true) {
cycle.add(ix + 1)
used[ix] = true
ix = t.indexOf(s[ix])
if (cycle[0] == ix + 1) {
smallestFirst_(cycle)
cycles.add(cycle)
break
}
}
}
return cycles
}
// Converts a list in one line notation to its inverse.
static oneLineInverse(oneLine) {
var c = oneLine.count
var s = oneLine.map { |b| String.fromByte(b + 64) }.join()
if (c < 15) {
for (i in c..15) s = s + String.fromByte(c + 65)
}
var t = (0..14).map { |b| String.fromByte(b + 65) }.join()
return oneLineNotation(s, t)
}
// Converts a list of cycles to its inverse.
static cycleInverse(cycles) {
var cycles2 = []
for (i in 0...cycles.count) {
var cycle = cycles[i][-1..0]
smallestFirst_(cycle)
cycles2.add(cycle)
}
return cycles2
}
// Permutes a string using perm in one line notation.
static oneLinePermute(s, perm) {
var c = perm.count
var t = List.filled(15, "")
for (i in 0...c) t[i] = s[perm[i]-1]
if (c < 15) {
for (i in c..14) t[i] = s[i]
}
return t.join()
}
// Permutes a string using perm in cycle notation.
static cyclePermute(s, cycles) {
var t = List.filled(15, "")
for (cycle in cycles) {
for (i in 0...cycle.count-1) {
t[cycle[i+1]-1] = s[cycle[i]-1]
}
t[cycle[0]-1] = s[cycle[-1]-1]
}
for (i in 0..14) if (t[i] == "") t[i] = s[i]
return t.join()
}
// Returns a single perm in cycle notation resulting from applying
// cycles1 first and then cycles2.
static cycleCombine(cycles1, cycles2) {
var s = (0..14).map { |b| String.fromByte(b + 65) }.join()
var t = cyclePermute(s, cycles1)
t = cyclePermute(t, cycles2)
return cycleNotation(s, t)
}
// Converts a list in one line notation to cycle notation.
static oneLineToCycle(oneLine) {
var c = oneLine.count
var t = oneLine.map { |b| String.fromByte(b + 64) }.join()
if (c < 15) {
for (i in c..15) t = t + String.fromByte(c + 65)
}
var s = (0..14).map { |b| String.fromByte(b + 65) }.join()
return cycleNotation(s, t)
}
// Converts a list in cycle notation to one line notation.
static cycleToOneLine(cycles) {
var s = (0..14).map { |b| String.fromByte(b + 65) }.join()
var t = cyclePermute(s, cycles)
return oneLineNotation(s, t)
}
// Returns the order of a permutation.
static order(cycles) {
var lens = []
for (cycle in cycles) lens.add(cycle.count)
return Int.lcm(lens)
}
// Returns the signature of a permutation.
static signature(cycles) {
var count = 0
for (cycle in cycles) if (cycle.count % 2 == 0) count = count + 1
return (count % 2 == 0) ? 1 : -1
}
}
var letters = [
"HANDYCOILSERUPT", // Monday
"SPOILUNDERYACHT", // Tuesday
"DRAINSTYLEPOUCH", // Wednesday
"DITCHSYRUPALONE", // Thursday
"SOAPYTHIRDUNCLE", // Friday
"SHINEPARTYCLOUD", // Saturday
"RADIOLUNCHTYPES" // Sunday
]
System.print("On Thursdays Alf and Betty should rearrange their letters using these cycles:")
var cycles = PC.cycleNotation(letters[2], letters[3])
System.print(PC.cyclesToString(cycles))
System.print("So that %(letters[2]) becomes %(PC.cyclePermute(letters[2], cycles))")
System.print("\nOr they could use the one line notation:")
var oneLine = PC.cycleToOneLine(cycles)
System.print(PC.oneLineToString(oneLine))
System.print("\nTo revert to the Wednesday arrangement they should use these cycles:")
var cycles2 = PC.cycleInverse(cycles)
System.print(PC.cyclesToString(cycles2))
System.print("\nOr with the one line notation:")
var oneLine2 = PC.oneLineInverse(oneLine)
System.print(PC.oneLineToString(oneLine2))
System.print("So that %(letters[3]) becomes %(PC.oneLinePermute(letters[3], oneLine2))")
System.print("\nStarting with the Sunday arrangement and applying each of the daily arrangements")
System.print("consecutively, the arrangements will be:")
var days = ["Mon", "Tue", "Wed", "Thu", "Fri", "Sat", "Sun"]
System.print("\n %(letters[6])\n")
for (j in 0..6) {
if (j == 6) System.print()
System.write(days[j] + ": ")
var i = (j == 0) ? 6 : j - 1
var ol = PC.oneLineNotation(letters[i], letters[j])
System.print(PC.oneLinePermute(letters[i], ol))
}
System.print("\nTo go from Wednesday to Friday in a single step they should use these cycles:")
var cycles3 = PC.cycleNotation(letters[3], letters[4])
var cycles4 = PC.cycleCombine(cycles, cycles3)
System.print(PC.cyclesToString(cycles4))
System.print("So that %(letters[2]) becomes %(PC.cyclePermute(letters[2], cycles4))")
System.print("\nThese are the signatures of the permutations:")
System.print(days.join(" "))
for (j in 0..6) {
var i = (j == 0) ? 6 : j - 1
var cy = PC.cycleNotation(letters[i], letters[j])
Fmt.write("$2d ", PC.signature(cy))
}
System.print()
System.print("\nThese are the orders of the permutations:")
System.print(days.join(" "))
for (j in 0..6) {
var i = (j == 0) ? 6 : j - 1
var cy = PC.cycleNotation(letters[i], letters[j])
Fmt.write("$3d ", PC.order(cy))
}
System.print()
System.print("\nApplying the Friday cycle to a string 10 times:")
var prev = "STOREDAILYPUNCH"
System.print("\n %(prev)\n")
for (i in 1..10) {
if (i == 10) System.print()
Fmt.write("$2d ", i)
prev = PC.cyclePermute(prev, cycles3)
System.print(prev)
}</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 arrangements
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:
| |||