Task 1: Nth Permutation
Write a script to accept two integers $N and $K. It should then return the $K-th permutation sequence of numbers from 1 to $N.
Example Output
Input: $N = 3, $K = 4
Output: 231
Logic
Generate all permutations of numbers from 1 to $N, sort them lexicographically, and select the $K-1-th item (0-indexed).
Perl Solution
ch-1.pl
use Algorithm::Permute;
sub get_nth_permutations {
my ( $n, $k ) = @_;
my @numbers = ( 1 .. $n );
my $p = Algorithm::Permute->new(\@numbers, $n);
my @all_perms;
while (my @res = $p->next) {
push @all_perms, join("", @res);
}
my @sorted_perms = sort @all_perms;
return $sorted_perms[$k-1];
}
Python Solution
ch-1.py
from itertools import permutations
class NthPermut:
def get_nth_permutations(self, n_integers: int, k_permutation: int):
nth_perm = list(permutations(range(1, n_integers+1)))[k_permutation-1]
return nth_perm
Task 2: Collatz Conjecture
Write a script to generate the Collatz sequence for 23, showing it is 16 elements long. Additionally, find the number under 1,000,000 that has the longest sequence length.
Example Output
Collatz sequence for 23: 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1 (Length: 16)
Logic
Collatz logic: if current number is even, divide it by 2. If odd, multiply by 3 and add 1. Repeat until it reaches 1. We can cache the lengths of sub-sequences to optimize calculation for numbers up to 1,000,000.
Perl Solution
ch-2.pl
sub get_next_sequence {
my $seq_pos = shift;
return 0 if $seq_pos == 1;
return 3 * $seq_pos + 1 if $seq_pos % 2 == 1;
return int( $seq_pos / 2 );
}
sub single_sequence {
my $seq_pos = shift;
my @seq;
while ( $seq_pos > 1 ) {
push @seq, $seq_pos;
$seq_pos = get_next_sequence($seq_pos);
}
push @seq, 1;
return \@seq;
}
Python Solution
ch-2.py
class Collatz:
def get_next_sequence(self, seq_pos: int):
if seq_pos % 2 == 0:
return seq_pos // 2
return 3 * seq_pos + 1
def single_sequence(self, seq_pos: int):
seq = []
while seq_pos > 1:
seq.append(seq_pos)
seq_pos = self.get_next_sequence(seq_pos)
seq.append(1)
return seq