Cycles of a permutation: Difference between revisions
→{{header|jq}}
m (→{{header|Quackery}}: typo) |
|||
| (21 intermediate revisions by 7 users not shown) | |||
Line 1:
{{
On the event of their marriage, Alf and Betty are gifted a magnificent and weighty set of twenty-six wrought iron letters, from A to Z, by their good friends Anna and Graham.
Line 71:
Thu->Wed: (2 4 14 5 15 10 11 3 7 8) (9 13 12)
If Alf and Betty went to visit Anna and Graham on a Wednesday and came home on a Friday, they'd need to figure out the permutation Wed->Fri from the permutations Wed->Thu and Thu->Fri. Mathematicians call this either composition or multiplication, and if A is the notation for Wed->Thu and B is the notation for Thu->Fri, they would write it as BA or
Note that
The cycle notation for Thu->Fri is
Line 79:
Thu->Fri: (1 10 4 13 2 8 9 11 3 6) (5 7) (12 14)
and the multiplication Thu->
Wed->Fri: (1 10 15 7 6 ) (2 9 14 13 11 4 8 5 12)
Line 101:
Their choice of orderings for cycle notation (i.e. smallest number first for cycles, cycles sorted in ascending order by first number) is not mandated. If your solution uses a different ordering, describe it.
Similarly, right-to-left evaluation of cycle multiplication as composition of functions is not mandated. Show how Thu->
Alf and Betty's system is one-based. If a zero-based system is more appropriate, then use that, but provide the means (e.g. one or more functions, procedures, subroutines, methods, or words, et cetera) to allow conversion to and from zero-based and one-based representations so that user I/O can be one-based. State if this is the case in your solution.
Line 125:
##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.
=={{header|C++}}==
Please note that the definitions used by Alf and Betty are not in agreement with standard mathematical practice.
<syntaxhighlight lang="c++">
#include <algorithm>
#include <cstdint>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <numeric>
#include <string>
#include <unordered_set>
#include <vector>
typedef std::vector<uint32_t> One_line;
typedef std::vector<One_line> Cycles;
class Permutation {
public:
// Initialise the length of the strings to be permuted.
Permutation(uint32_t letters_size) : letters_count(letters_size) { }
// Return the permutation in one line form that transforms the string 'source' into the string 'destination'.
const One_line create_one_line(const std::string& source, const std::string& destination) {
One_line result;
for ( const char& ch : destination ) {
result.emplace_back(source.find(ch) + 1);
}
while ( result.back() == result.size() ) {
result.pop_back();
}
return result;
}
// Return the cycles of the permutation given in one line form.
const Cycles one_line_to_cycles(One_line& one_line) {
Cycles cycles;
std::unordered_set<uint32_t> used;
for ( uint32_t number = 1; used.size() < one_line.size(); ++number ) {
if ( std::find(used.begin(), used.end(), number) == used.end() ) {
uint32_t index = index_of(one_line, number) + 1;
if ( index > 0 ) {
One_line cycle;
cycle.emplace_back(number);
while ( number != index ) {
cycle.emplace_back(index);
index = index_of(one_line, index) + 1;
}
if ( cycle.size() > 1 ) {
cycles.emplace_back(cycle);
}
used.insert(cycle.begin(), cycle.end());
}
}
}
return cycles;
}
// Return the one line notation of the permutation given in cycle form.
const One_line cycles_to_one_line(Cycles& cycles) {
One_line one_line(letters_count);
std::iota(one_line.begin(), one_line.end(), 1);
for ( uint32_t number = 1; number <= letters_count; ++number ) {
for ( One_line& cycle : cycles ) {
const int32_t index = index_of(cycle, number);
if ( index >= 0 ) {
one_line[number - 1] = cycle[( cycle.size() + index - 1 ) % cycle.size()];
break;
}
}
}
return one_line;
}
// Return the inverse of the given permutation in cycle form.
const Cycles cycles_inverse(const Cycles& cycles) {
Cycles cycles_inverse = cycles;
for ( One_line& cycle : cycles_inverse ) {
cycle.emplace_back(cycle.front());
cycle.erase(cycle.begin());
std::reverse(cycle.begin(), cycle.end());
}
return cycles_inverse;
}
// Return the inverse of the given permutation in one line notation.
const One_line one_line_inverse(One_line& one_line) {
One_line one_line_inverse(one_line.size(), 0);
for ( uint32_t number = 1; number <= one_line.size(); ++number ) {
one_line_inverse[number - 1] = index_of(one_line, number) + 1;
}
return one_line_inverse;
}
// Return the cycles obtained by composing cycleOne first followed by cycleTwo.
const Cycles combined_cycles(Cycles cycles_one, Cycles cycles_two) {
Cycles combined_cycles;
std::unordered_set<uint32_t> used;
for ( uint32_t number = 1; used.size() < letters_count; ++number ) {
if ( std::find(used.begin(), used.end(), number) == used.end() ) {
uint32_t combined = next(cycles_two, next(cycles_one, number));
One_line cycle;
cycle.emplace_back(number);
while ( number != combined ) {
cycle.emplace_back(combined);
combined = next(cycles_two, next(cycles_one, combined));
}
if ( cycle.size() > 1 ) {
combined_cycles.emplace_back(cycle);
}
used.insert(cycle.begin(), cycle.end());
}
}
return combined_cycles;
}
// Return the given string permuted by the permutation given in one line form.
const std::string one_line_permute_string(const std::string text, const One_line one_line) {
std::string permuted;
for ( const uint32_t& index : one_line ) {
permuted.append(1, text[index - 1]);
}
permuted.append(text, permuted.size());
return permuted;
}
// Return the given string permuted by the permutation given in cycle form.
const std::string cycles_permute_string(const std::string& text, Cycles& cycles) {
std::string permuted = text;
for ( const One_line& cycle : cycles ) {
for ( const uint32_t number : cycle ) {
permuted[next(cycles, number) - 1] = text[number - 1];
}
}
return permuted;
}
// Return the signature of the permutation given in one line form.
const std::string signature(One_line one_line) {
Cycles cycles = one_line_to_cycles(one_line);
uint32_t evenCount = 0;
for ( const One_line& cycle : cycles ) {
if ( cycle.size() % 2 == 0 ) {
evenCount++;
}
}
return ( evenCount % 2 == 0 ) ? "+1" : "-1";
}
// Return the order of the permutation given in one line form.
const uint32_t order(One_line one_line) {
Cycles cycles = one_line_to_cycles(one_line);
uint32_t lcm = 1;
for ( const One_line& cycle : cycles ) {
const uint32_t size = cycle.size();
lcm *= size / std::gcd(size, lcm);
}
return lcm;
}
private:
// Return the index of the given digit in the given vector.
const int32_t index_of(One_line& numbers, const uint32_t& digit) {
One_line::iterator iterator = std::find(numbers.begin(), numbers.end(), digit);
return ( iterator == numbers.end() ) ? -1 : std::distance(numbers.begin(), iterator);
}
// Return the element to which the given number is mapped by the permutation given in cycle form.
const uint32_t next(Cycles& cycles, const uint32_t& number) {
for ( One_line& cycle : cycles ) {
if ( std::find(cycle.begin(), cycle.end(), number) != cycle.end() ) {
return cycle[( index_of(cycle, number) + 1 ) % cycle.size()];
}
}
return number;
}
const uint32_t letters_count;
};
std::string to_string(const One_line& one_line) {
std::string result = "(";
for ( const uint32_t& number : one_line ) {
result += std::to_string(number) + " ";
}
return result.substr(0, result.length() - 1) + ") ";
}
std::string to_string(const Cycles& cycles) {
std::string result = "";
for ( const One_line& cycle : cycles ) {
result += to_string(cycle);
}
return result;
}
int main() {
enum Day { MONDAY, TUESDAY, WEDNESDAY, THURSDAY, FRIDAY, SATURDAY, SUNDAY };
const std::vector<std::string> day_names =
{ "MONDAY", "TUESDAY", "WEDNESDAY", "THURSDAY", "FRIDAY", "SATURDAY", "SUNDAY" };
const std::vector<std::string> letters = { "HANDYCOILSERUPT", "SPOILUNDERYACHT", "DRAINSTYLEPOUCH",
"DITCHSYRUPALONE", "SOAPYTHIRDUNCLE", "SHINEPARTYCLOUD", "RADIOLUNCHTYPES" };
auto previous_day = [day_names] (const uint32_t& today) {
return ( day_names.size() + today - 1 ) % day_names.size();
};
Permutation permutation(letters[0].length());
std::cout << "On Thursdays Alf and Betty should rearrange their letters using these cycles:" << std::endl;
One_line one_line_wed_thu = permutation.create_one_line(letters[WEDNESDAY], letters[THURSDAY]);
Cycles cycles_wed_thu = permutation.one_line_to_cycles(one_line_wed_thu);
std::cout << to_string(cycles_wed_thu) << std::endl;
std::cout << "So that " << letters[WEDNESDAY] << " becomes " << letters[THURSDAY] << std::endl;
std::cout << "\n" << "Or they could use the one line notation:" << std::endl;
std::cout << to_string(one_line_wed_thu) << std::endl;
std::cout << "\n" << "To revert to the Wednesday arrangement they should use these cycles:" << std::endl;
Cycles cycles_thu_wed = permutation.cycles_inverse(cycles_wed_thu);
std::cout << to_string(cycles_thu_wed) << std::endl;
std::cout << "\n" << "Or with the one line notation:" << std::endl;
One_line one_line_thu_wed = permutation.one_line_inverse(one_line_wed_thu);
std::cout << to_string(one_line_thu_wed) << std::endl;
std::cout << "So that " << letters[THURSDAY] << " becomes "
<< permutation.one_line_permute_string(letters[THURSDAY], one_line_thu_wed) << std::endl;
std::cout << "\n" << "Starting with the Sunday arrangement and applying each of the daily" << std::endl;
std::cout << "arrangements consecutively, the arrangements will be:" << std::endl;
std::cout << "\n" << std::string(6, ' ') << letters[SUNDAY] << "\n" << std::endl;
for ( uint32_t today = 0; today < day_names.size(); ++today ) {
One_line day_one_line = permutation.create_one_line(letters[previous_day(today)], letters[today]);
std::cout << std::setw(11) << day_names[today] << ": "
<< permutation.one_line_permute_string(letters[previous_day(today)], day_one_line)
<< ( ( day_names[today] == "SATURDAY" ) ? "\n" : "" ) << std::endl;
}
std::cout << "\n" << "To go from Wednesday to Friday in a single step they should use these cycles:" << std::endl;
One_line one_line_thu_fri = permutation.create_one_line(letters[THURSDAY], letters[FRIDAY]);
Cycles cycles_thu_fri = permutation.one_line_to_cycles(one_line_thu_fri);
Cycles cycles_wed_fri = permutation.combined_cycles(cycles_wed_thu, cycles_thu_fri);
std::cout << to_string(cycles_wed_fri) << std::endl;
std::cout << "So that " << letters[WEDNESDAY] << " becomes "
<< permutation.cycles_permute_string(letters[WEDNESDAY], cycles_wed_fri) << std::endl;
std::cout << "\n" << "These are the signatures of the permutations:" << "\n" << std::endl;
for ( uint32_t today = 0; today < day_names.size(); ++today ) {
One_line one_line = permutation.create_one_line(letters[previous_day(today)], letters[today]);
std::cout << std::setw(11) << day_names[today] << ": " << permutation.signature(one_line) << std::endl;
}
std::cout << "\n" << "These are the orders of the permutations:" << "\n" << std::endl;
for ( uint32_t today = 0; today < day_names.size(); ++today ) {
One_line one_line = permutation.create_one_line(letters[previous_day(today)], letters[today]);
std::cout << std::setw(11) << day_names[today] << ": " << permutation.order(one_line) << std::endl;
}
std::cout << "\n" << "Applying the Friday cycle to a string 10 times:" << std::endl;
std::string previous = "STOREDAILYPUNCH";
std::cout << "\n" << " 0 " << previous << "\n" << std::endl;
for ( uint32_t i = 1; i <= 10; ++i ) {
previous = permutation.cycles_permute_string(previous, cycles_thu_fri);
std::cout << std::setw(2) << i << " " << previous << ( ( i == 9 ) ? "\n" : "" ) << std::endl;
}
}
</syntaxhighlight>
{{ 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
MONDAY: HANDYCOILSERUPT
TUESDAY: SPOILUNDERYACHT
WEDNESDAY: DRAINSTYLEPOUCH
THURSDAY: DITCHSYRUPALONE
FRIDAY: SOAPYTHIRDUNCLE
SATURDAY: SHINEPARTYCLOUD
SUNDAY: 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:
MONDAY: -1
TUESDAY: -1
WEDNESDAY: +1
THURSDAY: -1
FRIDAY: -1
SATURDAY: +1
SUNDAY: +1
These are the orders of the permutations:
MONDAY: 18
TUESDAY: 30
WEDNESDAY: 12
THURSDAY: 30
FRIDAY: 10
SATURDAY: 33
SUNDAY: 40
Applying the Friday cycle to a string 10 times:
0 STOREDAILYPUNCH
1 DNPYAOETISLCRUH
2 ORLSEPANTDIUYCH
3 PYIDALERNOTCSUH
4 LSTOEIAYRPNUDCH
5 IDNPATESYLRCOUH
6 TORLENADSIYUPCH
7 NPYIAREODTSCLUH
8 RLSTEYAPONDUICH
9 YIDNASELPROCTUH
10 STOREDAILYPUNCH
</pre>
=={{header|Java}}==
Please note that the definitions used by Alf and Betty are not in agreement with standard mathematical practice.
<syntaxhighlight lang="java">
import java.util.ArrayList;
import java.util.Collections;
import java.util.EnumSet;
import java.util.HashSet;
import java.util.List;
import java.util.NavigableSet;
import java.util.Objects;
import java.util.Set;
import java.util.TreeSet;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import java.util.stream.Stream;
public final class CyclesOfAPermutation {
public static void main(String[] args) {
enum Day {
MONDAY("HANDYCOILSERUPT"), TUESDAY("SPOILUNDERYACHT"), WEDNESDAY("DRAINSTYLEPOUCH"),
THURSDAY("DITCHSYRUPALONE"), FRIDAY("SOAPYTHIRDUNCLE"), SATURDAY("SHINEPARTYCLOUD"),
SUNDAY("RADIOLUNCHTYPES");
public Day previous() {
return Objects.requireNonNullElseGet(days.lower(this), days::last);
}
public String letters() {
return letters;
}
private Day(String aLetters) {
letters = aLetters;
}
private String letters;
private static NavigableSet<Day> days = new TreeSet<Day>(EnumSet.allOf(Day.class));
}
Permutation permutation = new Permutation(Day.MONDAY.letters.length());
System.out.println("On Thursdays Alf and Betty should rearrange their letters using these cycles:");
List<Integer> oneLineWedThu = permutation.createOneLine(Day.WEDNESDAY.letters(), Day.THURSDAY.letters());
List<List<Integer>> cyclesWedThu = permutation.oneLineToCycles(oneLineWedThu);
System.out.println(cyclesWedThu);
System.out.println("So that " + Day.WEDNESDAY.letters() + " becomes " + Day.THURSDAY.letters());
System.out.println("\n" + "Or they could use the one line notation:");
System.out.println(oneLineWedThu);
System.out.println("\n" + "To revert to the Wednesday arrangement they should use these cycles:");
List<List<Integer>> cyclesThuWed = permutation.cyclesInverse(cyclesWedThu);
System.out.println(cyclesThuWed);
System.out.println("\n" + "Or with the one line notation:");
List<Integer> oneLineThuWed = permutation.oneLineInverse(oneLineWedThu);
System.out.println(oneLineThuWed);
System.out.println("So that " + Day.THURSDAY.letters() + " becomes "
+ permutation.oneLinePermuteString(Day.THURSDAY.letters(), oneLineThuWed));
System.out.println("\n" + "Starting with the Sunday arrangement and applying each of the daily");
System.out.println("arrangements consecutively, the arrangements will be:");
System.out.println("\n" + " ".repeat(6) + Day.SUNDAY.letters() + "\n");
for ( Day day : Day.values() ) {
List<Integer> dayOneLine = permutation.createOneLine(day.previous().letters(), day.letters());
String result = permutation.oneLinePermuteString(day.previous().letters(), dayOneLine);
System.out.println(
String.format("%11s%s%s", day.name() + ": ", result, ( day == Day.SATURDAY ) ? "\n" : ""));
}
System.out.println("\n" + "To go from Wednesday to Friday in a single step they should use these cycles:");
List<Integer> oneLineThuFri = permutation.createOneLine(Day.THURSDAY.letters(), Day.FRIDAY.letters());
List<List<Integer>> cyclesThuFri = permutation.oneLineToCycles(oneLineThuFri);
List<List<Integer>> cyclesWedFri = permutation.combinedCycles(cyclesWedThu, cyclesThuFri);
System.out.println(cyclesWedFri);
System.out.println("So that " + Day.WEDNESDAY.letters() + " becomes "
+ permutation.cyclesPermuteString(Day.WEDNESDAY.letters(), cyclesWedFri));
System.out.println("\n" + "These are the signatures of the permutations:" + "\n");
for ( Day day : Day.values() ) {
List<Integer> oneLine = permutation.createOneLine(day.previous().letters(), day.letters());
System.out.println(String.format("%11s", day.name() + ": ") + permutation.signature(oneLine));
}
System.out.println("\n" + "These are the orders of the permutations:" + "\n");
for ( Day day : Day.values() ) {
List<Integer> oneLine = permutation.createOneLine(day.previous().letters(), day.letters());
System.out.println(String.format("%11s", day.name() + ": ") + permutation.order(oneLine));
}
System.out.println("\n" + "Applying the Friday cycle to a string 10 times:");
String word = "STOREDAILYPUNCH";
System.out.println("\n" + " 0 " + word + "\n");
for ( int i = 1; i <= 10; i++ ) {
word = permutation.cyclesPermuteString(word, cyclesThuFri);
System.out.println(String.format("%2d%s%s%s", i, " ", word, ( i == 9 ) ? "\n" : ""));
}
}
}
final class Permutation {
// Initialise the length of the strings to be permuted.
public Permutation(int aLettersCount) {
lettersCount = aLettersCount;
}
// Return the permutation in one line form that transforms the string 'source' into the string 'destination'.
public List<Integer> createOneLine(String source, String destination) {
List<Integer> result = new ArrayList<Integer>();
for ( char ch : destination.toCharArray() ) {
result.addLast(source.indexOf(ch) + 1);
}
while ( result.getLast() == result.size() ) {
result.removeLast();
}
return result;
}
// Return the cycles of the permutation given in one line form.
public List<List<Integer>> oneLineToCycles(List<Integer> oneLine) {
List<List<Integer>> cycles = new ArrayList<List<Integer>>();
Set<Integer> used = new HashSet<Integer>();
for ( int number = 1; used.size() < oneLine.size(); number++ ) {
if ( ! used.contains(number) ) {
int index = oneLine.indexOf(number) + 1;
if ( index > 0 ) {
List<Integer> cycle = new ArrayList<Integer>();
cycle.addLast(number);
while ( number != index ) {
cycle.addLast(index);
index = oneLine.indexOf(index) + 1;
}
if ( cycle.size() > 1 ) {
cycles.addLast(cycle);
}
used.addAll(cycle);
}
}
}
return cycles;
}
// Return the one line notation of the permutation given in cycle form.
public List<Integer> cyclesToOneLine(List<List<Integer>> cycles) {
List<Integer> oneLine = IntStream.rangeClosed(1, lettersCount).boxed().collect(Collectors.toList());
for ( int number = 1; number <= lettersCount; number++ ) {
for ( List<Integer> cycle : cycles ) {
final int index = cycle.indexOf(number);
if ( index >= 0 ) {
oneLine.set(number - 1, cycle.get(( index - 1 + cycle.size() ) % cycle.size()));
break;
}
}
}
return oneLine;
}
// Return the inverse of the given permutation in cycle form.
public List<List<Integer>> cyclesInverse(List<List<Integer>> cycles) {
List<List<Integer>> cyclesInverse =
cycles.stream().map( list -> new ArrayList<Integer>(list) ).collect(Collectors.toList());
for ( List<Integer> cycle : cyclesInverse ) {
cycle.addLast(cycle.removeFirst());
Collections.reverse(cycle);
}
return cyclesInverse;
}
// Return the inverse of the given permutation in one line notation.
public List<Integer> oneLineInverse(List<Integer> oneLine) {
List<Integer> oneLineInverse = Stream.generate( () -> 0 ).limit(oneLine.size()).collect(Collectors.toList());
for ( int number = 1; number <= oneLine.size(); number++ ) {
oneLineInverse.set(number - 1, oneLine.indexOf(number) + 1);
}
return oneLineInverse;
}
// Return the cycles obtained by composing cycleOne first followed by cycleTwo.
public List<List<Integer>> combinedCycles(List<List<Integer>> cyclesOne, List<List<Integer>> cyclesTwo) {
List<List<Integer>> combinedCycles = new ArrayList<List<Integer>>();
Set<Integer> used = new HashSet<Integer>();
for ( int number = 1; used.size() < lettersCount; number++ ) {
if ( ! used.contains(number) ) {
int combined = next(next(number, cyclesOne), cyclesTwo);
List<Integer> cycle = new ArrayList<Integer>();
cycle.addLast(number);
while ( number != combined ) {
cycle.addLast(combined);
combined = next(next(combined, cyclesOne), cyclesTwo);
}
if ( cycle.size() > 1 ) {
combinedCycles.addLast(cycle);
}
used.addAll(cycle);
}
}
return combinedCycles;
}
// Return the given string permuted by the permutation given in one line form.
public String oneLinePermuteString(String text, List<Integer> oneLine) {
List<String> permuted = new ArrayList<String>();
for ( int index : oneLine ) {
permuted.addLast(text.substring(index - 1, index));
}
permuted.addLast(text.substring(permuted.size()));
return String.join("", permuted);
}
// Return the given string permuted by the permutation given in cycle form.
public String cyclesPermuteString(String text, List<List<Integer>> cycles) {
List<String> permuted = text.chars().mapToObj( i -> String.valueOf((char) i) ).collect(Collectors.toList());
for ( List<Integer> cycle : cycles ) {
for ( int number : cycle ) {
permuted.set(next(number, cycles) - 1, text.substring(number - 1, number));
}
}
return String.join("", permuted);
}
// Return the signature of the permutation given in one line form.
public String signature(List<Integer> oneLine) {
List<List<Integer>> cycles = oneLineToCycles(oneLine);
final long evenCount = cycles.stream().filter( list -> list.size() % 2 == 0 ).count();
return ( evenCount % 2 == 0 ) ? "+1" : "-1";
}
// Return the order of the permutation given in one line form.
public int order(List<Integer> oneLine) {
List<List<Integer>> cycles = oneLineToCycles(oneLine);
List<Integer> sizes = cycles.stream().map( list -> list.size() ).collect(Collectors.toList());
return sizes.stream().reduce(1, (one, two) -> one * ( two / gcd(one, two) ) );
}
// Return the element to which the given number is mapped by the permutation given in cycle form.
private int next(int number, List<List<Integer>> cycles) {
for ( List<Integer> cycle : cycles ) {
if ( cycle.contains(number) ) {
return cycle.get(( cycle.indexOf(number) + 1 ) % cycle.size());
}
}
return number;
}
// Return the greatest common divisor of the two given numbers.
private int gcd(int one, int two) {
return ( two == 0 ) ? one : gcd(two, one % two);
}
private final int lettersCount;
}
</syntaxhighlight>
{{ 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
MONDAY: HANDYCOILSERUPT
TUESDAY: SPOILUNDERYACHT
WEDNESDAY: DRAINSTYLEPOUCH
THURSDAY: DITCHSYRUPALONE
FRIDAY: SOAPYTHIRDUNCLE
SATURDAY: SHINEPARTYCLOUD
SUNDAY: 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:
MONDAY: -1
TUESDAY: -1
WEDNESDAY: +1
THURSDAY: -1
FRIDAY: -1
SATURDAY: +1
SUNDAY: +1
These are the orders of the permutations:
MONDAY: 18
TUESDAY: 30
WEDNESDAY: 12
THURSDAY: 30
FRIDAY: 10
SATURDAY: 33
SUNDAY: 40
Applying the Friday cycle to a string 10 times:
0 STOREDAILYPUNCH
1 DNPYAOETISLCRUH
2 ORLSEPANTDIUYCH
3 PYIDALERNOTCSUH
4 LSTOEIAYRPNUDCH
5 IDNPATESYLRCOUH
6 TORLENADSIYUPCH
7 NPYIAREODTSCLUH
8 RLSTEYAPONDUICH
9 YIDNASELPROCTUH
10 STOREDAILYPUNCH
</pre>
=={{header|jq}}==
{{Works with|jq}}
'''Works with gojq, the Go implementation of jq'''
The following is adapted from [[#Wren|Wren]]
but the shelf length is not hard-coded in any way.
It is, however, assumed throughout that strings are nonempty
and consist of distinct upper case letters.
<syntaxhighlight lang="jq">
### Generic utility functions
def lpad($len): tostring | ($len - length) as $l | (" " * $l) + .;
def count(s): reduce s as $i (0; . + 1);
# Least common multiple
def lcm($m; $n):
# Define the helper function to take advantage of jq's tail-recursion optimization
def _lcm:
# state is [m, n, i]
if (.[2] % .[1]) == 0 then .[2] else (.[0:2] + [.[2] + $m]) | _lcm end;
[$m, $n, $m] | _lcm;
# Rotate an array $n places to the left assuming 0 <= $n < length
def rotateLeft($n):
.[$n:] + .[:$n];
def days: ["Mon", "Tue", "Wed", "Thu", "Fri", "Sat", "Sun"];
### Cycles of a Permutation
# Arrange a cycle so the least element is first.
def smallestFirst:
. as $cycle
| reduce range(1; length) as $i ( {min: .[0], minIx: 0};
if $cycle[$i] < .min
then .min = $cycle[$i]
| .minIx = $i
end )
| .minIx as $minIx
| $cycle | rotateLeft($minIx) ;
# Converts a list in one-line notation to a space-separated string.
def oneLineToString: join(" ");
# Converts a list in cycle notation to a string where each cycle is space-separated
# and enclosed in parentheses.
def cyclesToString:
map( "(" + join(" ") + ")" ) | "[" + join(" ") + "]";
# Returns a list in one-line notation derived from two equal-length strings s and t.
def oneLineNotation($s; $t):
($s|length) as $len
| reduce range(0; $len) as $i ([]; .[$i] = ($s|index($t[$i:$i+1])) + 1)
| {i: ($len-1), res: .}
| until( .i == -1;
if .res[.i] != .i + 1
then .i=-1
else .i as $i
| .res |= del(.[$i])
| .i += -1
end )
| .res ;
# Returns a list in cycle notation derived from two equal-length strings s and t.
def cycleNotation($s; $t):
{ used: [range(0; $s|length) | false],
cycles: [] }
| reduce range(0; $s|length) as $i (.;
if .used[$i] then .
else .cycle = []
| .used[$i] = true
| .ix = ($t|index($s[$i:$i+1]))
| if $i == .ix then .
else .cycle += [$i+1]
| .done = false
| until (.done;
.cycle += [.ix + 1]
| .used[.ix] = true
| .ix as $j
| .ix = ($t|index($s[$j:$j+1]))
| if .cycle[0] == .ix + 1
then .cycles += [.cycle | smallestFirst ]
| .done = true
else .
end )
end
end )
| .cycles ;
# Converts a list in one-line notation to its inverse
# assuming $targetLength specifies the full length
def oneLineInverse($targetLength):
. as $oneLine
| length as $c
| {s: (map(. + 64) | implode) }
| if $c < $targetLength
then reduce range($c; $targetLength + 1) as $i (.;
.s += ([$c + 65]|implode) )
end
| ([range(0; $targetLength) | . + 65] | implode) as $t
| oneLineNotation(.s; $t) ;
# Converts a list of cycles to its inverse.
def cycleInverse:
map(reverse | smallestFirst) ;
# Permutes input string using perm in one-line notation.
def oneLinePermute($perm):
. as $s
| ($perm|length) as $c
| reduce range(0; $c) as $i ({t:[]};
($perm[$i]-1) as $j
| .t[$i] = $s[$j:$j+1] )
| (.t | join(""))
+ if $c < ($s|length)
then $s[$c:]
else ""
end ;
# Permutes input string in accordance with the permutation specified
# by $cycles
def cyclePermute($cycles):
. as $s
| reduce $cycles[] as $cycle ( [];
reduce range(0;$cycle|length-1) as $i (.;
($cycle[$i]-1) as $j
| .[$cycle[$i+1]-1] = $s[$j:$j+1] )
| ($cycle[-1]-1) as $j
| .[$cycle[0]-1] = $s[$j:$j+1] )
| reduce range(0; $s|length) as $i (.;
if .[$i] == null then .[$i] = $s[$i:$i+1] end)
| join("") ;
# Returns a single permutation in cycle notation resulting from applying
# $cycles1 first and then $cycles2.
def cycleCombine($cycles1; $cycles2; $targetLength):
{s: ([range(0; $targetLength) | . + 65] | implode)}
| .t = (.s | cyclePermute($cycles1))
| .t |= cyclePermute($cycles2)
| cycleNotation(.s; .t);
# Converts a list in one-line notation to cycle notation relative to $targetLength
def oneLineToCycle($targetLength):
. as $oneLine
| length as $c
| { t: ($oneLine | map(. + 64) | implode) }
| if $c < $targetLength
then reduce range($c; $targetLength+1) as $i (.; ## ??
.t += ([$c + 65]|implode) ) ## ??
end
| ([range (0; $targetLength) | . + 65] | implode) as $s
| cycleNotation($s; .t);
# Converts a list in cycle notation to one-line notation.
def cycleToOneLine($targetLength):
. as $cycles
| ([range(0; $targetLength) | . + 65 ] | implode)
| cyclePermute($cycles) as $t
| oneLineNotation(.; $t);
# The order of a permutation specified by its cycles
def order:
def lcm: reduce .[] as $x (1; lcm(.; $x));
map(length) | lcm;
# Returns the signature of a permutation specified by its cycles
def signature:
count(.[] | select(length % 2 == 0))
| if . % 2 == 0 then 1 else -1 end ;
### The task at hand
def letters: [
"HANDYCOILSERUPT", # Monday
"SPOILUNDERYACHT", # Tuesday
"DRAINSTYLEPOUCH", # Wednesday
"DITCHSYRUPALONE", # Thursday
"SOAPYTHIRDUNCLE", # Friday
"SHINEPARTYCLOUD", # Saturday
"RADIOLUNCHTYPES" # Sunday
];
def cycles: cycleNotation(letters[2]; letters[3]);
def prev: "STOREDAILYPUNCH";
cycles
| . as $cycles
| (letters[0] | length) as $targetLength
| cycleToOneLine($targetLength) as $oneLine
| ($oneLine | oneLineInverse($targetLength)) as $oneLine2
| cycleNotation(letters[3]; letters[4]) as $cycles3
| cycleCombine($cycles; $cycles3; $targetLength) as $cycles4
| "On Thursdays Alf and Betty should rearrange their letters using these cycles:",
cyclesToString,
"So that \(letters[2]) becomes \( letters[2] | cyclePermute($cycles) )",
"\nOr they could use the one-line notation:",
($oneLine | oneLineToString),
"\nTo revert to the Wednesday arrangement they should use these cycles:",
(cycleInverse | cyclesToString),
"\nOr with the one-line notation:",
($oneLine2|oneLineToString),
"So that \(letters[3]) becomes \( letters[3] | oneLinePermute($oneLine2))",
"\nStarting with the Sunday arrangement and applying each of the daily arrangements",
"consecutively, the arrangements will be:",
"\n \(letters[6])\n",
(range(0; days|length) as $j
| (if $j == (days|length) - 1 then "" else empty end),
days[$j] + ": " +
( (if $j == 0 then (days|length-1) else $j - 1 end) as $i
| oneLineNotation(letters[$i]; letters[$j]) as $ol
| letters[$i] | oneLinePermute($ol))),
"\nTo go from Wednesday to Friday in a single step they should use these cycles:",
($cycles4|cyclesToString),
"So that \(letters[2]) becomes \( letters[2] | cyclePermute($cycles4))",
"\nThese are the signatures of the permutations:",
(days | join(" ")),
([ range(0; days|length) as $j
| (if $j == 0 then 6 else $j - 1 end) as $i
| (cycleNotation(letters[$i]; letters[$j]) | signature)
| tostring | lpad(3) ] | join(" ")
),
"\nThese are the orders of the permutations:",
(days |join(" ")),
([ range( 0; days|length) as $j
| (if $j == 0 then 6 else $j - 1 end) as $i
| cycleNotation(letters[$i]; letters[$j]) | order]
| map(lpad(3)) | join(" ")),
"\nApplying the Friday cycle to a string 10 times:",
( foreach range (0;11) as $i ( {prev: prev};
.emit = "\($i | lpad(2)) \(.prev)"
| .prev |= cyclePermute($cycles3) )
| .emit )
</syntaxhighlight>
{{output}}
<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:
0 STOREDAILYPUNCH
1 DNPYAOETISLCRUH
2 ORLSEPANTDIUYCH
3 PYIDALERNOTCSUH
4 LSTOEIAYRPNUDCH
5 IDNPATESYLRCOUH
6 TORLENADSIYUPCH
7 NPYIAREODTSCLUH
8 RLSTEYAPONDUICH
9 YIDNASELPROCTUH
10 STOREDAILYPUNCH
</pre>
=={{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 below so as to fit to either format, and the test function's code is specified so as to
duplicate the cycles as written in examples given in the task.
<syntaxhighlight 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 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)
""" 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 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])
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()
</syntaxhighlight> {{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|Nim}}==
{{trans|Python}}
{{trans|Julia}}
<syntaxhighlight lang="Nim">import std/[algorithm, math, sequtils, setutils, strutils, sugar, tables]
type
Perm* = object
a: seq[int]
Cycle* = seq[int]
template isEven(n: int): bool = (n and 1) == 0
func newPerm*(len: Natural = 0): Perm =
## Create a Perm with given length.
result.a = newSeq[int](len)
func newPerm*(a: openArray[int]): Perm =
## Create a Perm with given values.
assert sorted(a) == toSeq(1..a.len), "Perm should be a shuffled 1-based range"
result.a = a.toSeq
template len*(perm: Perm): int = perm.a.len
template `[]`*(perm: Perm; idx: Natural): int =
## Return the element at given one base index.
perm.a[idx - 1]
template `[]=`*(perm: var Perm; idx: Natural; val: int) =
## Set the element at given one base index.
perm.a[idx - 1] = val
iterator pairs*(perm: Perm): (int, int) =
## Yield the couples (one-based-index, val).
for i in 1..perm.len:
yield (i, perm[i])
func inv*(perm: Perm): Perm =
## Return the inverse of a Perm.
result = newPerm(perm.len)
for i in 1..perm.len:
let j = perm[i]
result[j] = i
func cycles*(perm: Perm; includeSingles = false): seq[Cycle] =
## Get cycles of a Perm permutation as a sequence of integer
## sequences, optionally with singles.
var ptable = collect(for (i, val) in perm.pairs: {i: val})
for i in 1..perm.len:
var j: int
if ptable.pop(i, j):
var c = @[i]
while i != j:
c.add j
discard ptable.pop(j, j)
if includeSingles or c.len > 1:
result.add c
func cycleFormat*(perm: Perm; alfBettyForm = false): string =
## Stringify the Perm as its cycles, optionally in Rosetta Code task format.
let p = if alfBettyForm: inv(perm) else: perm
let cyclestrings = collect:
for c in p.cycles:
'(' & c.join(" ") & ')'
result = cycleStrings.join(" ")
func oneLineFormat*(perm: Perm): string =
## Stringify the Perm in one-line permutation format.
result = "[ " & perm.a.join(" ") & " ]"
func sign*(perm: Perm): int =
## Return the sign of the permutation.
var sum = 0
for c in perm.cycles:
sum += ord(c.len.isEven)
result = if sum.isEven: 1 else: -1
func order*(perm: Perm): int =
## Return the order of permutation for Perm.
lcm(perm.cycles.mapIt(it.len))
func `*`*(p1, p2: Perm): Perm =
## Return the composition of Perm permutations with the * operator.
assert p1.len == p2.len, "permutations must be of same length"
result = newPerm(collect(for i in 1..p1.len: p1[p2[i]]))
func toPerm*(cycles: seq[Cycle]; addSingles = true): Perm =
## Create a Perm from a sequence of cycles.
var cycles = cycles
var elements = collect:
for c in cycles:
for e in c: e
let allPossible = toSeq(1..elements.len)
if addSingles:
let missings = collect:
for x in allPossible:
if x notin elements: x
for elem in missings:
cycles.add @[elem]
elements.add elem
assert sorted(elements) == allPossible, "invalid cycles for creating a Perm"
result = newPerm(elements.len)
for c in cycles:
let length = c.len
for i in 1..length:
let j = c[i]
let n = c[(i + 1) mod length]
result[j] = n
func toPerm*(s: string): Perm =
## Create a Perm from a string with only one of each of its letters.
let letters = sorted(s).deduplicate(true)
result = newPerm(collect(for c in s: letters.find(c) + 1))
func toPerm*(s1, s2: string): Perm =
## Create a Perm from two strings permuting first string to the second one.
result = newPerm(collect(for c in s2: s1.find(c) + 1))
func permutedString*(s: string; p: Perm): string =
## Create a permuted string from another string using Perm p.
collect(for i in p.a: s[i - 1]).join("")
when isMainModule:
let
days = ["Mon", "Tue", "Wed", "Thu", "Fri", "Sat", "Sun"]
dayStrings = ["HANDYCOILSERUPT", "SPOILUNDERYACHT", "DRAINSTYLEPOUCH",
"DITCHSYRUPALONE", "SOAPYTHIRDUNCLE", "SHINEPARTYCLOUD", "RADIOLUNCHTYPES"]
dayPerms = collect:
for i in 0..6:
(toPerm(dayStrings[(i + 6) mod 7], dayStrings[i]))
echo "On Thursdays Alf and Betty should rearrange"
echo "their letters using these cycles: ", dayPerms[3].cycleFormat(true), '\n'
echo "So that ", dayStrings[2], " becomes ", daystrings[3], '\n'
echo "or they could use the one-line notation: ", dayPerms[3].oneLineFormat(), "\n\n"
echo "To revert to the Wednesday arrangement they"
echo "should use these cycles: ", inv(dayPerms[3]).cycleformat(true), '\n'
echo "or with the one-line notation: ", inv(dayperms[3]).oneLineFormat(), '\n'
echo "So that ", dayStrings[3], " becomes ", dayStrings[2], "\n\n"
echo "Starting with the Sunday arrangement and applying each of the daily"
echo "permutations consecutively, the arrangements will be:\n\n ", dayStrings[6]
for i in 0..6:
if i == 6: echo()
echo days[i], ": ", permutedString(daystrings[(i + 6) mod 7], dayPerms[i])
echo "\n\nTo go from Wednesday to Friday in a single step they should use these cycles: "
echo toPerm(dayStrings[2], dayStrings[4]).cycleformat(true), '\n'
echo "So that ", dayStrings[2], " becomes ", dayStrings[4], "\n\n"
echo "These are the signatures of the permutations:\n"
echo " Mon Tue Wed Thu Fri Sat Sun"
for i in 0..6:
stdout.write align($toPerm(dayStrings[(i + 6) mod 7], daystrings[i]).sign, 4)
echo "\n\nThese are the orders of the permutations:\n"
echo " Mon Tue Wed Thu Fri Sat Sun"
for i in 0..6:
stdout.write align($dayPerms[i].order, 4)
echo "\n\nApplying the Friday cycle to a string 10 times:\n"
let pFri = dayperms[4]
var spe = "STOREDAILYPUNCH"
echo " ", spe
for i in 1..10:
spe = permutedString(spe, pFri)
echo align($i, 2), ' ', spe, if i == 9: "\n" else: ""
</syntaxhighlight>
{{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|Phix}}==
{{trans|Wren}}
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #7060A8;">requires</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"1.0.2"</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- (tagstart)</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">smallest_first</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">cycle</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- Rearrange a cycle so the lowest element is first.</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">mdx</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">smallest</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cycle</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">cycle</span><span style="color: #0000FF;">[</span><span style="color: #000000;">mdx</span><span style="color: #0000FF;">..$]</span> <span style="color: #0000FF;">&</span> <span style="color: #000000;">cycle</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">mdx</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">one_line_to_string</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">one_line</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- Converts a list in one line notation to a space separated string.</span>
<span style="color: #008080;">return</span> <span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">one_line</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" "</span><span style="color: #0000FF;">,</span><span style="color: #000000;">fmt</span><span style="color: #0000FF;">:=</span><span style="color: #008000;">"%d"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">cycles_to_string</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">cycles</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- Converts a list in cycle notation to a string where each cycle
-- is space separated and enclosed in parentheses.</span>
<span style="color: #008080;">return</span> <span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">apply</span><span style="color: #0000FF;">(</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">cycles</span><span style="color: #0000FF;">,{</span><span style="color: #008000;">" "</span><span style="color: #0000FF;">},{</span><span style="color: #008000;">" "</span><span style="color: #0000FF;">},{</span><span style="color: #008000;">"%d"</span><span style="color: #0000FF;">}}),</span><span style="color: #000000;">fmt</span><span style="color: #0000FF;">:=</span><span style="color: #008000;">"(%s)"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">one_line_notation</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- Returns a list in one line notation derived from two strings s and t.</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">l</span> <span style="color: #008080;">do</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">l</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]!=</span><span style="color: #000000;">i</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..-</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">cycle_notation</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- Returns a list in cycle notation derived from two strings s and t.</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">used</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #004600;">false</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)),</span>
<span style="color: #000000;">cycles</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">used</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">used</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">used</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">ix</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span><span style="color: #000000;">t</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">ix</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">i</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">cycle</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">i</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">cycle</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">ix</span>
<span style="color: #000000;">used</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ix</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span>
<span style="color: #000000;">ix</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ix</span><span style="color: #0000FF;">],</span><span style="color: #000000;">t</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">ix</span><span style="color: #0000FF;">=</span><span style="color: #000000;">i</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">cycle</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">smallest_first</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cycle</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">cycles</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cycles</span><span style="color: #0000FF;">,</span><span style="color: #000000;">cycle</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">exit</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">cycles</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">one_line_inverse</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">one_line</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- Converts a list in one line notation to its inverse.</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">one_line</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">' '</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">tagstart</span><span style="color: #0000FF;">(</span><span style="color: #008000;">'A'</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">l</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">one_line</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]+</span><span style="color: #008000;">'A'</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">one_line_notation</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #000000;">t</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">cycle_inverse</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">cycles</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- Converts a list of cycles to its inverse.</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">cycles2</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cycles</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cycles</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">cycle</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">cycles</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">cycles2</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">cycle</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">&</span> <span style="color: #7060A8;">reverse</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cycle</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">..$])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">cycles2</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">one_line_permute</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">perm</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- Permutes a string using perm in one line notation.</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">perm</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">perm</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]]</span> <span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">t</span>
<span style="color: #000080;font-style:italic;">--alternative one-liner:
-- return reinstate(s,tagset(length(perm)),extract(s,perm))</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">cycle_permute</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">cycles</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- Permutes a string using perm in cycle notation.</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">cycle</span> <span style="color: #008080;">in</span> <span style="color: #000000;">cycles</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cycle</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">t</span><span style="color: #0000FF;">[</span><span style="color: #000000;">cycle</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">cycle</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000000;">t</span><span style="color: #0000FF;">[</span><span style="color: #000000;">cycle</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">cycle</span><span style="color: #0000FF;">[$]]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">t</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">cycle_combine</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">cycles1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">cycles2</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">// Returns a single perm in cycle notation resulting
// from applying cycles1 first and then cycles2.</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">m</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">max</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">max</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">flatten</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cycles1</span><span style="color: #0000FF;">)),</span>
<span style="color: #7060A8;">max</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">flatten</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cycles1</span><span style="color: #0000FF;">)))</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">tagstart</span><span style="color: #0000FF;">(</span><span style="color: #008000;">'A'</span><span style="color: #0000FF;">,</span><span style="color: #000000;">m</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">cycle_permute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">cycles1</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">cycle_permute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">cycles2</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">cycle_notation</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">one_line_to_cycle</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">one_line</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">// Converts a list in one line notation to cycle notation.</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">one_line</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">tagstart</span><span style="color: #0000FF;">(</span><span style="color: #008000;">'A'</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">' '</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">l</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">t</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">one_line</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]+</span><span style="color: #008000;">'A'</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">cycle_notation</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">cycle_to_one_line</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">cycles</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- Converts a list in cycle notation to one line notation.</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">tagstart</span><span style="color: #0000FF;">(</span><span style="color: #008000;">'A'</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">max</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">flatten</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cycles</span><span style="color: #0000FF;">))),</span>
<span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">cycle_permute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">cycles</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">one_line_notation</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">cycle_order</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">cycles</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- Returns the order of a permutation.</span>
<span style="color: #008080;">return</span> <span style="color: #7060A8;">lcm</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">apply</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cycles</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">cycle_signature</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">cycles</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- Returns the signature of a permutation.</span>
<span style="color: #008080;">return</span> <span style="color: #7060A8;">even</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sum</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">apply</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">apply</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cycles</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">even</span><span style="color: #0000FF;">)))*</span><span style="color: #000000;">2</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">DAYS</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span>
<span style="color: #000000;">MON</span> <span style="color: #0000FF;">:=</span> <span style="color: #008000;">"HANDYCOILSERUPT"</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">TUE</span> <span style="color: #0000FF;">:=</span> <span style="color: #008000;">"SPOILUNDERYACHT"</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">WED</span> <span style="color: #0000FF;">:=</span> <span style="color: #008000;">"DRAINSTYLEPOUCH"</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">THU</span> <span style="color: #0000FF;">:=</span> <span style="color: #008000;">"DITCHSYRUPALONE"</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">FRI</span> <span style="color: #0000FF;">:=</span> <span style="color: #008000;">"SOAPYTHIRDUNCLE"</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">SAT</span> <span style="color: #0000FF;">:=</span> <span style="color: #008000;">"SHINEPARTYCLOUD"</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">SUN</span> <span style="color: #0000FF;">:=</span> <span style="color: #008000;">"RADIOLUNCHTYPES"</span>
<span style="color: #0000FF;">}</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"On Thursdays Alf and Betty should rearrange their letters using these cycles:\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">cycle_wt</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">cycle_notation</span><span style="color: #0000FF;">(</span><span style="color: #000000;">WED</span><span style="color: #0000FF;">,</span><span style="color: #000000;">THU</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">cycles_to_string</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cycle_wt</span><span style="color: #0000FF;">)})</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"So that %s becomes %s\n\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">WED</span><span style="color: #0000FF;">,</span><span style="color: #000000;">cycle_permute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">WED</span><span style="color: #0000FF;">,</span><span style="color: #000000;">cycle_wt</span><span style="color: #0000FF;">)})</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">one_line</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">cycle_to_one_line</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cycle_wt</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">assert</span><span style="color: #0000FF;">(</span><span style="color: #000000;">one_line_to_cycle</span><span style="color: #0000FF;">(</span><span style="color: #000000;">one_line</span><span style="color: #0000FF;">)==</span><span style="color: #000000;">cycle_wt</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Or they could use the one line notation:\n%s\n\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">one_line_to_string</span><span style="color: #0000FF;">(</span><span style="color: #000000;">one_line</span><span style="color: #0000FF;">)})</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"To revert to the Wednesday arrangement they should use these cycles:\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s\n\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">cycles_to_string</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cycle_inverse</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cycle_wt</span><span style="color: #0000FF;">))})</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Or with the one line notation:\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">one_line2</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">one_line_inverse</span><span style="color: #0000FF;">(</span><span style="color: #000000;">one_line</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">one_line_to_string</span><span style="color: #0000FF;">(</span><span style="color: #000000;">one_line2</span><span style="color: #0000FF;">))</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"So that %s becomes %s\n\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">THU</span><span style="color: #0000FF;">,</span><span style="color: #000000;">one_line_permute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">THU</span><span style="color: #0000FF;">,</span><span style="color: #000000;">one_line2</span><span style="color: #0000FF;">)})</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Starting with the Sunday arrangement and applying each of the daily arrangements\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"consecutively, the arrangements will be:\n\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" %s\n\n"</span><span style="color: #0000FF;">,{(</span><span style="color: #000000;">SUN</span><span style="color: #0000FF;">)})</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">signatures</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{},</span> <span style="color: #000000;">orders</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">yesterday</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">DAYS</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">today</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">DAYS</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">td</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">DAYS</span><span style="color: #0000FF;">[</span><span style="color: #000000;">today</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">yd</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">DAYS</span><span style="color: #0000FF;">[</span><span style="color: #000000;">yesterday</span><span style="color: #0000FF;">]</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">ol</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">one_line_notation</span><span style="color: #0000FF;">(</span><span style="color: #000000;">yd</span><span style="color: #0000FF;">,</span><span style="color: #000000;">td</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">cy</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">cycle_notation</span><span style="color: #0000FF;">(</span><span style="color: #000000;">yd</span><span style="color: #0000FF;">,</span><span style="color: #000000;">td</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s: %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">td</span><span style="color: #0000FF;">,</span><span style="color: #000000;">one_line_permute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">yd</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ol</span><span style="color: #0000FF;">)})</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">today</span><span style="color: #0000FF;">>=</span><span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">SAT</span><span style="color: #0000FF;">,</span><span style="color: #000000;">DAYS</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">signatures</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">cycle_signature</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cy</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">orders</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">cycle_order</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cy</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">yesterday</span> <span style="color: #0000FF;">:=</span> <span style="color: #000000;">today</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"To go from Wednesday to Friday in a single step they should use these cycles:\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">cycles_tf</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">cycle_notation</span><span style="color: #0000FF;">(</span><span style="color: #000000;">THU</span><span style="color: #0000FF;">,</span><span style="color: #000000;">FRI</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">cycles_wf</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">cycle_combine</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cycle_wt</span><span style="color: #0000FF;">,</span><span style="color: #000000;">cycles_tf</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">cycles_to_string</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cycles_wf</span><span style="color: #0000FF;">)})</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"So that %s becomes %s\n\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">WED</span><span style="color: #0000FF;">,</span><span style="color: #000000;">cycle_permute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">WED</span><span style="color: #0000FF;">,</span><span style="color: #000000;">cycles_wf</span><span style="color: #0000FF;">)})</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">FMT</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"""
These are the %s of the permutations:
Mon Tue Wed Thu Fri Sat Sun
%s
"""</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">FMT</span><span style="color: #0000FF;">,{</span><span style="color: #008000;">"signatures"</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">signatures</span><span style="color: #0000FF;">,</span><span style="color: #000000;">fmt</span><span style="color: #0000FF;">:=</span><span style="color: #008000;">"%2d "</span><span style="color: #0000FF;">)})</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">FMT</span><span style="color: #0000FF;">,{</span><span style="color: #008000;">"orders"</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">orders</span><span style="color: #0000FF;">,</span><span style="color: #000000;">fmt</span><span style="color: #0000FF;">:=</span><span style="color: #008000;">"%3d"</span><span style="color: #0000FF;">)})</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Applying the Friday cycle to a string 10 times:\n\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">prev</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"STOREDAILYPUNCH"</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" %s\n\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">prev</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">10</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">prev</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">cycle_permute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">prev</span><span style="color: #0000FF;">,</span><span style="color: #000000;">cycles_tf</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%2d %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">prev</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">9</span> <span style="color: #008080;">then</span> <span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</syntaxhighlight>-->
Output identical to Julia/Wren
=={{header|Python}}==
{{trans|Julia}}
<syntaxhighlight lang="python">""" For Rosetta Code task Cycles_of_a_permutation """
from math import lcm # in python 3.9+
class Perm:
""" 1 -based permutations of range of integers """
def __init__(self, range_or_list):
""" make a perm from a list or range of integers """
self.a = list(range_or_list)
assert sorted(self.a) == list(range(1, len(self.a) + 1)),\
'Perm should be a shuffled 1-based range'
def __repr__(self):
return 'Permutation class Perm'
def cycleformat(self, AlfBettyForm = False):
""" stringify the Perm as its cycles, optionally if Rosetta Code task format """
p = self.inv() if AlfBettyForm else self
cyclestrings = ["(" + " ".join([str(i) for i in c]) + ")" for c in p.cycles()]
return '( ' + ' '.join(cyclestrings) + ' )'
def onelineformat(self):
""" stringify the Perm in one-line permutation format """
return '[ ' + ' '.join([str(i) for i in self.a]) + ' ]'
def len(self):
""" length """
return len(self.a)
def sign(self):
""" sign """
return 1 if sum([len(c) % 2 == 0 for c in self.cycles()]) % 2 == 0 else -1
def order(self):
""" order of permutation for Perm """
return lcm(*[len(c) for c in self.cycles()])
def __mul__(self, p2):
""" Composition of Perm permutations with the * operator """
length = len(self.a)
assert length == len(p2.a), 'Permutations must be of same length'
return Perm([self.a[p2.a[i] - 1] for i in range(len(self.a))])
def inv(self):
""" inverse of a Perm """
length = len(self.a)
newa = [0 for _ in range(length)]
for idx in range(length):
jidx = self.a[idx]
newa[jidx - 1] = idx + 1
return Perm(newa)
def cycles(self, *, includesingles = False):
"""
Get cycles of a Perm permutation as a list of integer lists,
optionally with single cycles included, otherwise omitiing singles
"""
v = self.a
length = len(v)
unchecked = [True] * length
foundcycles = []
for idx in range(length):
if unchecked[idx]:
c = [idx + 1]
unchecked[idx] = False
jidx = idx
while unchecked[v[jidx] - 1]:
jidx = v[jidx]
c.append(jidx)
jidx -= 1
unchecked[jidx] = False
if len(c) > 1 or includesingles:
foundcycles.append(c)
return sorted(foundcycles)
def cycles_to_Perm(cycles, *, addsingles = True):
""" Create a Perm from a vector of cycles """
elements = [e for c in cycles for e in c]
allpossible = list(range(1, len(elements) + 1))
if addsingles:
missings = [x for x in allpossible if not x in elements]
for elem in missings:
cycles.append([elem])
elements.append(elem)
assert sorted(elements) == allpossible, 'Invalid cycles for creating a Perm'
a = [0 for _ in range(len(elements))]
for c in cycles:
length = len(c)
for idx in range(length):
jidx, n = c[idx], c[(idx + 1) % length]
a[jidx - 1] = n
return Perm(a)
def string_to_Perm(s):
""" Create a Perm from a string with only one of each of its letters """
letters = sorted(list(set(list(s))))
return Perm([letters.index(c) + 1 for c in s])
def two_string_to_Perm(s1, s2):
""" Create a Perm from two strings permuting first string to the second one """
return Perm([s1.index(c) + 1 for c in s2])
def permutestring(s, p):
""" Create a permuted string from another string using Perm p """
return ''.join([s[i - 1] for i in p.a])
if __name__ == '__main__':
# Testing code
days = ['Mon', 'Tue', 'Wed', 'Thu', 'Fri', 'Sat', 'Sun']
daystrings = ['HANDYCOILSERUPT', 'SPOILUNDERYACHT', 'DRAINSTYLEPOUCH',
'DITCHSYRUPALONE', 'SOAPYTHIRDUNCLE', 'SHINEPARTYCLOUD', 'RADIOLUNCHTYPES']
dayperms = [two_string_to_Perm(daystrings[(i - 1) % 7], daystrings[i]) for i in range(7)]
print('On Thursdays Alf and Betty should rearrange\ntheir letters using these cycles:',
' ', dayperms[3].cycleformat(True), '\n\n\nSo that ', daystrings[2], ' becomes ',
daystrings[3], '\n\nor they could use the one-line notation: ',
dayperms[3].onelineformat(),
'\n\n\n\nTo revert to the Wednesday arrangement they\nshould use these cycles: ',
dayperms[3].inv().cycleformat(True), '\n\n\nor with the one-line notation: ',
dayperms[3].inv().onelineformat(), '\n\n\nSo that ', daystrings[3], ' becomes ',
daystrings[2],
'\n\n\n\nStarting with the Sunday arrangement and applying each of the daily',
'\npermutations consecutively, the arrangements will be:\n\n ',
daystrings[6], '\n')
for i in range(7):
if i == 6:
print()
print(days[i], ': ', permutestring(daystrings[(i - 1) % 7], dayperms[i]))
print('\n\n\nTo go from Wednesday to Friday in a single step they should use these cycles: ')
print(two_string_to_Perm(daystrings[2], daystrings[4]).cycleformat(True))
print('\n\nSo that ', daystrings[2], ' becomes ', daystrings[4])
print('\n\n\nThese are the signatures of the permutations:\n\n Mon Tue Wed Thu Fri Sat Sun')
for i in range(7):
j = 6 if i == 0 else i - 1
print(str(two_string_to_Perm(daystrings[(i - 1) % 7],
daystrings[i]).sign()).rjust(4), end='')
print('\n\n\nThese are the orders of the permutations:\n\n Mon Tue Wed Thu Fri Sat Sun')
for i in range(7):
print(str(dayperms[i].order()).rjust(4), end='')
print("\n\nApplying the Friday cycle to a string 10 times:\n")
PFRI, SPE = dayperms[4], 'STOREDAILYPUNCH'
print(" ", SPE, '\n')
for i in range(10):
SPE = permutestring(SPE, PFRI)
print(str(i+1).rjust(2), ' ', SPE, '\n' if i == 8 else '')
</syntaxhighlight> {{out}}
<pre>
Same as Quackery.
</pre>
=={{header|Quackery}}==
<
--------
Line 217 ⟶ 2,041:
a, b and c are permutations in ZBCN. c is equal to applying first b
and then a to a string i.e.
recompose ( a --> b );
Line 494 ⟶ 2,318:
echo sp
friday cycle cypermute dup echo$ cr ]
drop</
{{out}}
Line 546 ⟶ 2,370:
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|Raku}}==
<syntaxhighlight lang="raku" line>
# one-line
sub infix:<➜> ($start, $end) {$start.fc.comb(/\w/).antipairs.hash{ $end.fc.comb(/\w/) } »+» 1}
# cycle
sub infix:<➰> ($start, $end) {
my @one-line = flat ($end ➜ $start);
my @index = flat 1..+@one-line;
my ($index, @cycles) = 0;
for @index {
my $this = $_ - 1;
while @one-line[$this] {
my $next = @one-line[$this];
@cycles[$index].push: @index[$this];
@one-line[$this] = Nil;
$this = $next - 1;
}
++$index;
}
@cycles.grep: *.elems > 1
}
# order of a cycle
sub order (@cycles) { [lcm] @cycles }
# signature of a cycle
sub signature (@cycles) {
(@cycles.elems %% 2 and all @@cycles».elems %% 2) ?? 1 !! -1
}
# apply a one-line transform
sub apply-o ($string, @oneline) { $string.comb[@oneline].join }
# apply a cyclical transform
sub apply-c ($string, @cycle) {
my @string = flat '', $string.comb;
@cycle.map: { @string[|$_].=rotate(-1) }
@string.join
}
# Alf & Bettys letter arrangements
my %arrangment =
:Mon<HANDYCOILSERUPT>,
:Tue<SPOILUNDERYACHT>,
:Wed<DRAINSTYLEPOUCH>,
:Thu<DITCHSYRUPALONE>,
:Fri<SOAPYTHIRDUNCLE>,
:Sat<SHINEPARTYCLOUD>,
:Sun<RADIOLUNCHTYPES>;
# some convenience variables
my @days = <Sun Mon Tue Wed Thu Fri Sat Sun>;
my @o = @days.rotor(2 => -1).map: { (%arrangment{.[0]} ➜ %arrangment{.[1]}) »-» 1 }
my @c = @days.rotor(2 => -1).map: { (%arrangment{.[0]} ➰ %arrangment{.[1]}) }
my $today;
# The task
say qq:to/ALF&BETTY/;
On Thursdays Alf and Betty should rearrange
their letters using these cycles: {gist %arrangment<Wed> ➰ %arrangment<Thu>}
So that {%arrangment<Wed>} becomes {%arrangment<Wed>.&apply-o: (%arrangment<Wed> ➜ %arrangment<Thu>) »-» 1}
or they could use the one-line notation: {gist %arrangment<Wed> ➜ %arrangment<Thu>}
To revert to the Wednesday arrangement they
should use these cycles: {gist %arrangment<Thu> ➰ %arrangment<Wed>}
or with the one-line notation: {gist %arrangment<Thu> ➜ %arrangment<Wed>}
So that {%arrangment<Thu>} becomes {%arrangment<Thu>.&apply-o: (%arrangment<Thu> ➜ %arrangment<Wed>) »-» 1}
Starting with the Sunday arrangement and applying each of the daily
permutations consecutively, the arrangements will be:
{$today = %arrangment<Sun>}
{join "\n", @days[1..*].map: { sprintf "%s: %s", $_, $today = $today.&apply-o: @o[$++] } }
To go from Wednesday to Friday in a single step they should use these cycles:
{gist %arrangment<Wed> ➰ %arrangment<Fri>}
So that {%arrangment<Wed>} becomes {%arrangment<Fri>}
These are the signatures of the permutations:
Mon Tue Wed Thu Fri Sat Sun
{@c.map(&signature)».fmt("%2d").join: ' '}
These are the orders of the permutations:
Mon Tue Wed Thu Fri Sat Sun
{@c.map(&order)».fmt("%2d").join: ' '}
Applying the Friday cycle to a string 10 times:
{$today = 'STOREDAILYPUNCH'}
{join "\n", (1..10).map: {sprintf "%2d %s", $_, $today = $today.&apply-c: @c[4]} }
ALF&BETTY
say 'and one last transform:';
say 'STOREDAILYPUNCH'.&apply-c: [[<1 6 12 2 3 4 13 15 9 11 5 14 8 10 7>],];</syntaxhighlight>
{{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
and one last transform:
AUTOPSYCHILDREN
</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.
<syntaxhighlight lang="wren">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)
}</syntaxhighlight>
{{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:
| |||