Cycles of a permutation: Difference between revisions

Content added Content deleted
(New post.)
(Minor code improvements.)
Line 145: Line 145:


public static void main(String[] args) {
public static void main(String[] args) {
⚫
enum Day {
⚫
Permutation permutation = new Permutation();
⚫
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:");
System.out.println("On Thursdays Alf and Betty should rearrange their letters using these cycles:");
Line 166: Line 190:
+ permutation.oneLinePermuteString(Day.THURSDAY.letters(), oneLineThuWed));
+ permutation.oneLinePermuteString(Day.THURSDAY.letters(), oneLineThuWed));
System.out.println("\n" + "Starting with the Sunday arrangement and applying each of the daily arrangements");
System.out.println("\n" + "Starting with the Sunday arrangement and applying each of the daily");
System.out.println("consecutively, the arrangements will be:");
System.out.println("arrangements consecutively, the arrangements will be:");
System.out.println("\n" + " ".repeat(6) + Day.SUNDAY.letters() + "\n");
System.out.println("\n" + " ".repeat(6) + Day.SUNDAY.letters() + "\n");
for ( Day day : Day.values() ) {
for ( Day day : Day.values() ) {
if ( day == Day.SUNDAY ) {
⚫
System.out.println();
⚫
}
⚫
List<Integer> dayOneLine = permutation.createOneLine(day.previous().letters(), day.letters());
List<Integer> dayOneLine = permutation.createOneLine(day.previous().letters(), day.letters());
⚫
String result = permutation.oneLinePermuteString(day.previous().letters(), dayOneLine);
System.out.println(day.name() + ": "
⚫
System.out.println(
⚫
+ permutation.oneLinePermuteString(day.previous().letters(), dayOneLine));
String.format("%11s%s%s", day.name() + ": ", result, ( day == Day.SATURDAY ) ? "\n" : ""));
}
}
Line 187: Line 208:
+ permutation.cyclesPermuteString(Day.WEDNESDAY.letters(), cyclesWedFri));
+ permutation.cyclesPermuteString(Day.WEDNESDAY.letters(), cyclesWedFri));
System.out.println("These are the signatures of the permutations:" + "\n");
System.out.println("\n" + "These are the signatures of the permutations:" + "\n");
System.out.println(" Mon Tue Wed Thu Fri Sat Sun");
for ( Day day : Day.values() ) {
for ( Day day : Day.values() ) {
List<Integer> oneLine = permutation.createOneLine(day.previous().letters(), day.letters());
List<Integer> oneLine = permutation.createOneLine(day.previous().letters(), day.letters());
System.out.print(" " + permutation.signature(oneLine));
System.out.println(String.format("%11s", day.name() + ": ") + permutation.signature(oneLine));
}
}
System.out.println("\n\n" + "These are the orders of the permutations:" + "\n");
System.out.println("\n" + "These are the orders of the permutations:" + "\n");
System.out.println(" Mon Tue Wed Thu Fri Sat Sun");
for ( Day day : Day.values() ) {
for ( Day day : Day.values() ) {
List<Integer> oneLine = permutation.createOneLine(day.previous().letters(), day.letters());
List<Integer> oneLine = permutation.createOneLine(day.previous().letters(), day.letters());
System.out.print(" " + permutation.order(oneLine));
System.out.println(String.format("%11s", day.name() + ": ") + permutation.order(oneLine));
}
}
System.out.println("\n\n" + "Applying the Friday cycle to a string 10 times:");
System.out.println("\n" + "Applying the Friday cycle to a string 10 times:");
String prev = "STOREDAILYPUNCH";
String word = "STOREDAILYPUNCH";
System.out.println("\n " + prev + "\n");
System.out.println("\n" + " 0 " + word + "\n");
for ( int i = 1; i <= 10; i++ ) {
for ( int i = 1; i <= 10; i++ ) {
⚫
word = permutation.cyclesPermuteString(word, cyclesThuFri);
if ( i == 10 ) {
System.out.println();
System.out.println(String.format("%2d%s%s%s", i, " ", word, ( i == 9 ) ? "\n" : ""));
⚫
}
System.out.print(String.format("%2d ", i));
⚫
prev = permutation.cyclesPermuteString(prev, cyclesThuFri);
System.out.println(prev);
}
}
}
}
}
}


final class Permutation {
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'.
// Return the permutation in one line form that transforms the string 'source' into the string 'destination'.
Line 242: Line 262:
if ( index > 0 ) {
if ( index > 0 ) {
List<Integer> cycle = new ArrayList<Integer>();
List<Integer> cycle = new ArrayList<Integer>();
cycle.add(number);
cycle.addLast(number);
while ( number != index ) {
while ( number != index ) {
cycle.add(index);
cycle.addLast(index);
index = oneLine.indexOf(index) + 1;
index = oneLine.indexOf(index) + 1;
}
}
Line 254: Line 274:
used.addAll(cycle);
used.addAll(cycle);
}
}
}
}
}
}
Line 263: Line 282:
// Return the one line notation of the permutation given in cycle form.
// Return the one line notation of the permutation given in cycle form.
public List<Integer> cyclesToOneLine(List<List<Integer>> cycles) {
public List<Integer> cyclesToOneLine(List<List<Integer>> cycles) {
List<Integer> oneLine = IntStream.rangeClosed(1, LETTERS_COUNT).boxed().collect(Collectors.toList());
List<Integer> oneLine = IntStream.rangeClosed(1, lettersCount).boxed().collect(Collectors.toList());
for ( int number = 1; number <= LETTERS_COUNT; number++ ) {
for ( int number = 1; number <= lettersCount; number++ ) {
for ( List<Integer> cycle : cycles ) {
for ( List<Integer> cycle : cycles ) {
final int index = cycle.indexOf(number);
final int index = cycle.indexOf(number);
Line 305: Line 324:
Set<Integer> used = new HashSet<Integer>();
Set<Integer> used = new HashSet<Integer>();
for ( int number = 1; used.size() < LETTERS_COUNT; number++ ) {
for ( int number = 1; used.size() < lettersCount; number++ ) {
if ( ! used.contains(number) ) {
if ( ! used.contains(number) ) {
int combined = next(next(number, cyclesOne), cyclesTwo);;
int combined = next(next(number, cyclesOne), cyclesTwo);
List<Integer> cycle = new ArrayList<Integer>();
List<Integer> cycle = new ArrayList<Integer>();
cycle.addLast(number);
cycle.addLast(number);
Line 313: Line 332:
while ( number != combined ) {
while ( number != combined ) {
cycle.addLast(combined);
cycle.addLast(combined);
combined = next(next(combined, cyclesOne), cyclesTwo);
combined = next(next(combined, cyclesOne), cyclesTwo);
}
}
Line 384: Line 403:
}
}
private static final int LETTERS_COUNT = 15;
private final int lettersCount;
⚫
}
⚫
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 Day next() {
return Objects.requireNonNullElseGet(days.higher(this), days::first);
}
⚫
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));
}
}
Line 431: Line 423:
So that DITCHSYRUPALONE becomes DRAINSTYLEPOUCH
So that DITCHSYRUPALONE becomes DRAINSTYLEPOUCH


Starting with the Sunday arrangement and applying each of the daily arrangements
Starting with the Sunday arrangement and applying each of the daily
consecutively, the arrangements will be:
arrangements consecutively, the arrangements will be:


RADIOLUNCHTYPES
RADIOLUNCHTYPES


MONDAY: HANDYCOILSERUPT
MONDAY: HANDYCOILSERUPT
TUESDAY: SPOILUNDERYACHT
TUESDAY: SPOILUNDERYACHT
WEDNESDAY: DRAINSTYLEPOUCH
WEDNESDAY: DRAINSTYLEPOUCH
THURSDAY: DITCHSYRUPALONE
THURSDAY: DITCHSYRUPALONE
FRIDAY: SOAPYTHIRDUNCLE
FRIDAY: SOAPYTHIRDUNCLE
SATURDAY: SHINEPARTYCLOUD
SATURDAY: SHINEPARTYCLOUD


SUNDAY: RADIOLUNCHTYPES
SUNDAY: RADIOLUNCHTYPES


To go from Wednesday to Friday in a single step they should use these cycles:
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]]
[[1, 10, 15, 7, 6], [2, 9, 14, 13, 11, 4, 8, 5, 12]]
So that DRAINSTYLEPOUCH becomes SOAPYTHIRDUNCLE
So that DRAINSTYLEPOUCH becomes SOAPYTHIRDUNCLE

These are the signatures of the permutations:
These are the signatures of the permutations:


MONDAY: -1
Mon Tue Wed Thu Fri Sat Sun
TUESDAY: -1
-1 -1 +1 -1 -1 +1 +1
WEDNESDAY: +1
THURSDAY: -1
FRIDAY: -1
SATURDAY: +1
SUNDAY: +1


These are the orders of the permutations:
These are the orders of the permutations:


MONDAY: 18
Mon Tue Wed Thu Fri Sat Sun
TUESDAY: 30
18 30 12 30 10 33 40
WEDNESDAY: 12
THURSDAY: 30
FRIDAY: 10
SATURDAY: 33
SUNDAY: 40


Applying the Friday cycle to a string 10 times:
Applying the Friday cycle to a string 10 times:


STOREDAILYPUNCH
0 STOREDAILYPUNCH


1 DNPYAOETISLCRUH
1 DNPYAOETISLCRUH
Retrieved from "https://rosettacode.org/wiki/Cycles_of_a_permutation"