Cycles of a permutation: Difference between revisions
→{{header|jq}}
(Minor code improvements.) |
|||
| (3 intermediate revisions by one other user not shown) | |||
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}}==
Line 142 ⟶ 500:
import java.util.stream.Stream;
public final class CyclesOfAPermutation {
public static void main(String[] args) {
Line 476 ⟶ 834:
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>
| |||