Perl Weekly Challenge 174: Disarium Numbers and Permutation Rankings
These are some answers to the Week 174 of the Perl Weekly Challenge organized by Mohammad S. Anwar.
Spoiler Alert: This weekly challenge deadline is due in a few of days from now (on July 24, 2022 at 23:59). This blog post offers some solutions to this challenge, please don’t read on if you intend to complete the challenge on your own.
Task 1: Disarium Numbers
Write a script to generate first 19 Disarium Numbers.
A disarium number is an integer where the sum of each digit raised to the power of its position in the number, is equal to the number.
For example,
518 is a disarium number as (5 ** 1) + (1 ** 2) + (8 ** 3) => 5 + 1 + 512 => 518
In Raku and Perl, we’ll implicitly convert the input number into a string of characters (@digits), split it into an array of characters, and then implicitly convert each character into a digit. In some other languages such as awk, bc, or C, such implicit conversion don’t happen or are tedious, and we will use mathematical computations to get the individual digits.
Disarium Numbers in Raku
This is quite straight forward. We have a is-disarium subroutine which returns a True value is the described sum is equal to the input value, and False otherwise. Then we use it to test each subsequent integer from 0 on and print out the number if it is a disarium number. We stop when we reach 19 disarium numbers.
sub is-disarium($num) {
my @digits = $num.comb;
my $sum = [+] map { $^b ** ($^a + 1) }, @digits.kv;
return $num == $sum;
}
my $count = 0;
my $i = 0;
while $count < 19 {
++$count and say $i if is-disarium($i);
$i++;
# say "i: $i";
}
This program displays the following output:
0
1
2
3
4
5
6
7
8
9
89
135
175
518
598
1306
1676
2427
2646798
This program took 0.4 second to find the first 18 disarium numbers, and then more than 4 minutes to find the 19th one. I have to confess that, for years, I have been too lazy to upgrade my Rakudo installation, which dates from 2019. This time, I decided it was high time to upgrade it and installed version 2022.06 to see what happens.
The good news is that, with this new version, the program ran in about 45 seconds. More than five times faster, that’s a rather impressive improvement. The bad news, though, is that it’s still very slow. The equivalent Perl and Python programs (see below) both took slightly less than 10 seconds, the Julia implementation ran in 3 seconds, and the C program completed in less than half a second. There is definitely a large opportunity for performance improvement. I love Raku, but I must admit that, in terms or performance, it is currently not good at intensive number crunching.
Disarium Numbers in Perl
This is a port to Perl of the Raku program just above, with a is_disarium subroutine to find is the input integer is a disarium number.
use strict;
use warnings;
use feature "say";
sub is_disarium {
my $num = shift;
my @digits = split '', $num;
my $i = 1;
my $sum = 0;
$sum += $_ for map { $_ ** $i++ } @digits;
return $num == $sum;
}
my $i = 0;
my $count = 0;
while ($count < 19) {
say $i and $count++ if is_disarium $i;
$i++;
}
This program displays the following output:
$ time perl ./disarium.pl
0
1
2
3
[Lines omitted for brevity]
1676
2427
2646798
real 0m9,781s
user 0m9,625s
sys 0m0,046s
Disarium Numbers in Julia
Julia has the built-in digits function, which produces a list of digits of the input number (in the wrong order for our purpose), and enumerate iterator, which yields a list of indexes and values. These functions make the is_disarium function very simple (it could easily be written in one single code line).
function is_disarium(n)
s = sum(i ^ p for (p, i) in enumerate(reverse(digits(n))))
return s == n
end
count = 0
i = 0
while count < 19
if is_disarium(i)
println(i)
global count += 1
end
global i += 1
end
Output:
julia ./disarium.jl
0
1
2
3
[Lines omitted for brevity]
1676
2427
2646798
Disarium Numbers in awk
The awk language doesn’t have the powerful string functions of Raku, Perl, or Julia. In the while loop of the is_disarium function, we use the integer division and modulo operators to get each digit of the input integer in turn.
function is_disarium(num) {
n = num
sum = 0
len = length(n)
while (n > 0) {
sum += (n % 10) ^ len
n = int(n/10)
len--
}
return (sum == num)
}
BEGIN {
count = 0
i = 0
while (count < 19) {
if (is_disarium(i)) {
printf("%d\n", i)
count++
}
i++
}
}
Output:
$ awk -f ./disarium.awk
0
1
2
3
[Lines omitted for brevity]
1676
2427
2646798
Disarium Numbers in bc
This program is very similar to the awk program just above, with the same method to access the individual digits.
define is_disarium (num) {
n = num
sum = 0
len = length(n)
while (n > 0) {
sum += (n % 10) ^ len
n = n/10
len -= 1
}
return (sum == num)
}
count = 0
i = 0
while (count < 19) {
if (is_disarium(i)) {
print i, "\n"
count += 1
}
i += 1
}
quit
Output:
$ bc ./disarium.bc
bc 1.06.95
Copyright 1991-1994, 1997, 1998, 2000, 2004, 2006 Free Software Foundation, Inc.
This is free software with ABSOLUTELY NO WARRANTY.
For details type `warranty'.
0
1
2
3
[Lines omitted for brevity]
1676
2427
2646798
Disarium Numbers in dc
The problem can be solved with a dc one-liner (spread over two lines for formatting reasons):
$ dc -e '[10/ll1+sld0<Lx] sL [d10%ll^ls+ss10/ll1-sld0<Dx] sD [lc1+sc
lnp] sP [lisnln0sllLx0ssclnlDxlsln=Pli1+silc18>Ix] sI0si0sclIx'
0
1
2
3
4
5
6
7
8
9
89
135
175
518
598
1306
1676
2427
Note that I only printed 18 numbers because this is getting really slow.
This is not a golf attempt: I could have removed a few spaces if I had wanted to golf it.
But I must admit dc scripts are not easy to read. This is now a much more readable version of the same solution:
# Macro for computing the input number length
[10 # pushes 10 to stack
/ # divides input by 10 and stores result on stack
ll # push length on stack
1+ # add one to stack (length)
# p # prints intermediate length (for debugging)
sl # saves length to register l
d # duplicates value (number) on top of stack
0 # pushes 0 to stack
<Lx # executes length macro (L) if number > 0
] sL # end of length macro, store it in L
# is Disarium macro
[d # duplicates value (number) on top of stack
10 # pushes 10 to stack
% # pushes (number % 10) to stack
ll # pushes length to stack
^ # computes (n % 10) ^ len
ls # pushes sum to stack
+ss # computes new sum and stores it in s
10/ # integer division number / 10
ll # pushes length on stack
1- # subtract 1 froml length
sl # stores new length in l
d # duplicates value (number) on top of stack
0 # pushes 0 to stack
<Dx # executes recursively disarium macro (D) if number > 0
] sD # stores disarium macro in D
# Printing and counting macro
[lc1+sc # increments disarium number counter
lnp # print number
]sP # Stores printing macro in P
# Iteration macro
[li sn # Stores iteration variable in number register
ln # pushes number to stack
0sl # stores 0 in register l (length)
lLx # runs the length macro
0ss # inititialize sum to 0
cln # clear stack and pushes number onto it
# llp # print the length
lDx # runs the Disarium macro once
lsln # pushes sum and number
=P # runs the printing macro if numbers are equal
li # loads iteration variable
1+si # increments iteration variable
lc18 # pushes counter and 18 on stack
>Ix # runs recursively iteration macro if counter < 18
] sI # end of iteration macro, stores it in I
# Main
0si # Initiate iteration variable
0sc # Initiate disarium numbers counter
lIx # running iteration macro the first time
Output:
$ dc disarium.dc
0
1
2
3
[Lines omitted for brevity]
1306
1676
2427
Understanding the solution in details would require a lot more explanations than what I can provide here. If you want to understand better how this program works and, more broadly, how the dc syntax works, you are kindly invited to read this other blog post where I describe the solution in detail.
Disarium Numbers in C
The C programming language doesn’t have a standard exponentiation operator. So I wrote a power function to perform exponentiation of individual digits. There is also no direct way to find the number of digits of an integer. So, I used floor(log10(n)) + 1 to find the size of an integer n, except that it would fail for an input of 0, so I used this method only for integers larger than 9.
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int power (int base, int exponent) {
int result = 1;
for (int i = 1; i <= exponent; i++) {
result *= base;
}
return result;
}
int is_disarium (int num) {
int n = num;
int sum = 0;
int len = n <= 9 ? 1 : floor(log10(n)) + 1;
while (n > 0) {
sum += power(n % 10, len);
n /= 10;
len--;
}
return num == sum;
}
int main() {
int count = 0;
int i = 0;
while (count < 19) {
if (is_disarium(i)) {
printf("%d\n", i);
count++;
}
i++;
}
}
Output:
$ time ./a.out
0
1
2
3
[Lines omitted for brevity]
1676
2427
2646798
real 0m0,475s
user 0m0,280s
sys 0m0,015s
Disarium Numbers in Python
Also using the integer division and modulo operators to get each digit of the input integer.
def is_disarium(num):
n = num
size = len(str(n))
sum = 0
while n > 0:
sum += (n % 10) ** size
n //= 10
size -= 1
return sum == num
i = 0
count = 0
while count < 19:
if is_disarium(i):
print(i)
count += 1
i += 1
Output:
$ python3 disarium.py
0
1
2
3
[Lines omitted for brevity]
1306
1676
2427
2646798
Disarium Numbers in Ruby
def is_disarium(num)
n = num.to_s
sum = 0
for i in 1..(n.length)
sum += n[i-1].to_i**i
end
return sum == num
end
i = 0
count = 0
while count < 19
if is_disarium(i)
printf("%d ", i)
count += 1
end
i += 1
end
print("\n")
From now on, our programs will display the disarium numbers on one line to save space:
0 1 2 3 4 5 6 7 8 9 89 135 175 518 598 1306 1676 2427 2646798
Disarium Numbers in Kotlin
Kotlin has a pow function for exponentiation, but it works with Double and Float leading to numerous time-consuming difficulties. I ended up writing my own power functions for integers.
fun power(n: Int, exp: Int): Int {
return when {
exp > 1 -> n * power(n, exp-1)
exp == 1 -> n
else -> 1
}
}
fun is_disarium(num: Int): Boolean {
val n = num.toString()
var sum = 0
for (i in 1..n.length) {
sum += power (n[i-1] - '0', i)
}
return sum == num
}
fun main() {
var i = 0
var count = 0
while (count < 19) {
if (is_disarium(i)) {
print("$i ")
count++
}
i++
}
println("")
}
Output:
0 1 2 3 4 5 6 7 8 9 89 135 175 518 598 1306 1676 2427 2646798
Disarium Numbers in Rust
I don’t really like Rust because, in my humble opinion, its type system is really an obstructive straitjacket and gets in the way of doing simple things. Just like in Kotlin, I ended up writing my own power functions for exponentiating integers.
fn power(n: i32, exp: i32) -> i32 {
let mut result = 1;
for _i in 0..exp {
result *= n;
}
return result;
}
fn is_disarium(num: i32) -> bool {
let mut n = num;
let mut sum = 0;
let mut i = 1;
let len = num.to_string().len();
while n > 0 {
sum += power(n % 10, len as i32 - i + 1);
n /= 10;
i += 1
}
return sum == num;
}
fn main() {
let mut i = 0;
let mut count = 0;
while count <= 18 {
if is_disarium(i) {
print!("{} ", i);
count += 1;
}
i += 1;
}
println!("{}", " ")
}
Output:
0 1 2 3 4 5 6 7 8 9 89 135 175 518 598 1306 1676 2427 2646798
Disarium Numbers in Java
import java.lang.Math;
public class DisariumNumbers {
public static boolean is_disarium(int num) {
int n = num;
int len = Integer.toString(n).length();
int sum = 0;
int i = 1;
while (n > 0) {
sum += Math.pow(n % 10, len - i + 1);
n /= 10;
i ++;
}
return sum == num;
}
public static void main(String[] args) {
int i = 0;
int count = 0;
while (count <= 18) {
if (is_disarium(i)) {
System.out.printf("%d ", i);
count++;
}
i++;
}
System.out.printf("%s", "\n");
}
}
Output:
0 1 2 3 4 5 6 7 8 9 89 135 175 518 598 1306 1676 2427 2646798
Disarium Numbers in Scala
object Disarium extends App {
def power(base: Int, exp: Int): Int = {
var result = 1
for (i <- 1 to exp) {
result *= base
}
return result
}
def is_disarium(num: Int): Boolean = {
val digits = num.toString.split("")
var sum = 0
for (i <- 0 to (digits.size - 1)) {
sum += power(digits(i).toInt, i + 1)
}
return num == sum
}
var i = 0
var count = 0
while (count < 19) {
if (is_disarium(i)) {
count += 1
printf("%d ", i)
}
i += 1
}
println("")
}
Output:
0 1 2 3 4 5 6 7 8 9 89 135 175 518 598 1306 1676 2427 2646798
Disarium Numbers in Ring
i = 0
count = 0
while count < 19
if is_disarium(i)
see "" + i + " "
count++
ok
i++
end
see nl
func pow (base, exp)
result = 1
for i = 0 to exp - 1
result *= base
next
return result
func is_disarium (num)
n = "" + num
sum = 0
for i = 1 to len(n)
sum += pow (n[i] % 10, i)
next
return sum = num
Output:
$ ring ./disarium.ring
0 1 2 3 4 5 6 7 8 9 89 135 175 518 598 1306 1676 2427 2646798
Disarium Numbers in Nim
import strutils
import math
proc is_disarium(num: int): bool =
let n = intToStr(num)
var sum = 0
for i in 0..len(n)-1:
sum += int((int(n[i])-48) ^ (i+1))
return sum == num
var i = 0
var count = 0
while count < 19:
if is_disarium(i):
stdout.write i, " "
count += 1
i += 1
echo ""
Output:
0 1 2 3 4 5 6 7 8 9 89 135 175 518 598 1306 1676 2427 2646798
Disarium Numbers in Go
package main
import (
"fmt"
"math"
"strconv"
)
func is_disarium(num int) bool {
n := num
i := 0
sum := 0
l := len(strconv.Itoa(n))
for n > 0 {
sum += int(math.Pow(float64(n%10), float64(l-i)))
n /= 10
i++
}
return sum == num
}
func main() {
i := 0
count := 0
for count < 19 {
if is_disarium(i) {
fmt.Printf("%d ", i)
count++
}
i++
}
fmt.Println("")
}
Output:
0 1 2 3 4 5 6 7 8 9 89 135 175 518 598 1306 1676 2427 2646798
Disarium Numbers in Tcl
I used to be a fan of Tcl some 25 to 30 years ago, not that I really loved Tcl itself, but because it came usually bundled with the Tk graphical toolkit, and I really loved Tk, which made fairly easy the design and implementation of graphical interfaces. But I wasn’t really impressed at the time by its shell-looking syntax and, often, I wasn’t quite sure whether I should add a $ sign before a variable name or not, or whether I should use [...], (...), or {...}. Now, more than a quarter of century later, I have forgotten most if not all the details about the syntax, and I find it quite difficult to use and somewhat awkward (but perhaps it is my own prejudice). Still, I’m posting this Tcl implementation as a kind of tribute to John Ousterhout, the blessed creator of Tcl-Tk.
proc is_disarium {num} {
set n num
set sum 0
set i 1
set ch 1
foreach char [split $num {}] {
scan $char %d ch
set sum [ expr ($sum + $ch ** $i)]
incr i
}
return [ expr $num == $sum ? 1 : 0]
}
set i 0
set count 0
while { $count < 19 } {
if [ is_disarium $i ] {
puts -nonewline "${i} "
incr count
}
incr i
}
puts ""
Output:
$ tclsh ./disarium.tcl
0 1 2 3 4 5 6 7 8 9 89 135 175 518 598 1306 1676 2427 2646798
Disarium Numbers in D
import std.stdio;
import std.math;
import std.conv;
bool is_disarium(int num) {
int n = num;
int sum = 0;
ulong len = to!string(num, 10).length;
while (n > 0) {
sum += pow(n % 10, len);
n /= 10;
len--;
}
return num == sum;
}
void main() {
int i = 0;
int count = 0;
while (count < 19) {
if (is_disarium(i)) {
printf("%d ", i);
count++;
}
i++;
}
writeln(" ");
}
Output:
0 1 2 3 4 5 6 7 8 9 89 135 175 518 598 1306 1676 2427 2646798
Disarium Numbers in Dart
import "dart:math";
import "dart:io";
void main() {
var count = 0;
var i = 0;
while (count < 19) {
if (is_disarium(i)) {
stdout.write("$i ");
count++;
}
i++;
}
}
bool is_disarium(numb) {
var n = numb;
var len = n.toString().length;
var sum = 0;
while (n > 0) {
sum += (pow(n % 10, len)).toInt();
n = (n / 10).toInt();
len--;
}
return numb == sum;
}
Output:
0 1 2 3 4 5 6 7 8 9 89 135 175 518 598 1306 1676 2427 2646798
Disarium Numbers in JavaScript
function is_disarium (num) {
let n = num
let len = n.toString().length
let sum = 0
while (n > 0) {
sum += (n % 10) ** len
n = parseInt(n / 10, 10)
len--
}
return num == sum
}
let count = 0
let i = 1
while (count < 18) {
if (is_disarium(i)) {
process.stdout.write(i + " ")
count++
}
i++
}
Output:
1 2 3 4 5 6 7 8 9 89 135 175 518 598 1306 1676 2427 2646798
Task 2: Permutation Ranking
You are given a list of integers with no duplicates, e.g. [0, 1, 2].
Write two functions, permutation2rank() which will take the list and determine its rank (starting at 0) in the set of possible permutations arranged in lexicographic order, and rank2permutation() which will take the list and a rank number and produce just that permutation.
Please checkout this post for more informations and algorithm.
Given the list [0, 1, 2] the ordered permutations are:
0: [0, 1, 2]
1: [0, 2, 1]
2: [1, 0, 2]
3: [1, 2, 0]
4: [2, 0, 1]
5: [2, 1, 0]
and therefore:
permutation2rank([1, 0, 2]) = 2
rank2permutation([0, 1, 2], 1) = [0, 2, 1]
Given that dealing with integers, I do not understand why permutations should be arranged in lexicographic order. I would expect permutation [9, 11] to be before permutation [11, 9], but lexicographic order would arrange them the other way around: [11, 9], [9, 11]. Well, it doesn’t really matter and we will use in our tests only single digit integers to avoid bizarre results. I’ll even use a test with single letters to show that my implementation also works with letters.
The second thing is that since my implementation of permutation2rank creates an ordered array of permutations, we don’t really need the rank2permutation subroutine to find the permutation with rank n, since I only need to lookup the array. I’ll create the rank2permutation subroutine nonetheless, just to abide with the specification.
Permutation Ranking in Raku
In Raku, the permutations method will create permutations in the proper order provided the input permutation is itself in the right order. So we only need to sort the input permutation at the beginning.
my @permut_str;
sub permutation2rank(@in) {
# if the input list is sorted, then permutations will be sorted
# Forcing a lexicographic order (although not really needed here)
my @sorted = sort { $^a leg $^b }, @in;
my @permutations = @sorted.permutations;
@permut_str = map {[join " ", $_]}, @permutations;
my %ranks = map { $^b => $^a }, @permut_str.kv;
}
sub rank2permutations ($rank) {
return @permut_str[$rank];
}
my @tests = (1, 0, 2), (6, 3, 4), <a c d b>;
for @tests -> @test {
my %ranks = permutation2rank(@test);
say @permut_str;
my $test = join " ", @test;
say "[$test] has rank %ranks{$test}";
say "Rank %ranks{$test} is ", rank2permutations(%ranks{$test});
say "Rank {%ranks{$test} - 1} is ", rank2permutations(%ranks{$test} - 1);
say "";
}
Note that we are also printing the sorted permutations to enable easy verification of the results.
This program displays the following output:
$ raku ./permute_ranks.raku
[[0 1 2] [0 2 1] [1 0 2] [1 2 0] [2 0 1] [2 1 0]]
[1 0 2] has rank 2
Rank 2 is [1 0 2]
Rank 1 is [0 2 1]
[[3 4 6] [3 6 4] [4 3 6] [4 6 3] [6 3 4] [6 4 3]]
[6 3 4] has rank 4
Rank 4 is [6 3 4]
Rank 3 is [4 6 3]
[[a b c d] [a b d c] [a c b d] [a c d b] [a d b c] [a d c b] [b a c d] [b a d c] [b c a d] [b c d a] [b d a c] [b d c a] [c a b d] [c a d b] [c b a d] [c b d a] [c d a b] [c d b a] [d a b c] [d a c b] [d b a c] [d b c a] [d c a b] [d c b a]]
[a c d b] has rank 3
Rank 3 is [a c d b]
Rank 2 is [a c b d]
Permutation Ranking in Perl
Perl has no built-in function to create permutations, so we implement the recursive permute subroutine to do that. Note that we designed it in such a way as to create the permutations in the right order, provided the input permutation is itself in the proper order.
use strict;
use warnings;
use feature "say";
use Data::Dumper;
my @permutations;
sub permute {
my ($done, $left) = @_;
if (scalar @$left == 0) {
push @permutations, $done;
return;
}
my @left = @$left;
permute([ @$done, $left[$_]], [@left[0..$_-1], @left[$_+1..$#left]]) for 0..$#left;
}
sub permutation2rank {
# if the input list is sorted, then permutations will be sorted
# This will be in lexicographic order, even for numbers
my @sorted = sort @_;
permute([], [@sorted]);
my @permut_str = map {join " ", @$_} @permutations;
my $count = 0;
my %ranks = map { $_ => $count++ } @permut_str;
}
sub rank2permutations {
return (map {join " ", @$_} @permutations)[$_[0]];
}
my @tests = ( [1, 0, 2], [6, 3, 4], [<a d c b>]);
for my $test (@tests) {
@permutations = ();
my %ranks = permutation2rank (@$test);
my $test_str = join " ", @$test;
say "Rank of [$test_str] is: $ranks{$test_str}";
for my $i (2, 4, 5) {
say "Rank $i is [", rank2permutations ($i), "]";
}
say " ";
}
This program displays the following output:
$ perl ./permute_ranks.pl
Rank of [1 0 2] is: 2
Rank 2 is [1 0 2]
Rank 4 is [2 0 1]
Rank 5 is [2 1 0]
Rank of [6 3 4] is: 4
Rank 2 is [4 3 6]
Rank 4 is [6 3 4]
Rank 5 is [6 4 3]
Rank of [a d c b] is: 5
Rank 2 is [a c b d]
Rank 4 is [a d b c]
Rank 5 is [a d c b]
Permutation Ranking in Julia
Note that Julia array subscripts start at 1, not 0. Therefore, the ranks are shifted by 1 compared to other languages and the output differs accordingly. It would be easy to fix that, but I preferred to keep the Julia semantic.
# Note: Julia array subscripts start at 1, not 0
using Combinatorics
function permute(in_list)
return collect(permutations(sort(in_list), length(in_list)))
end
function permutation2rank(perms, input)
for i in 1:length(perms)
if perms[i] == input
return i
end
end
end
function rank2permutation(perm_list, index)
return perm_list[index]
end
perm_in = [3, 1, 2]
perms = permute(perm_in)
println("Permutations: ", perms)
println("Permutation ", perm_in, " -> rank ", permutation2rank(perms, perm_in))
for i in 1:length(perms)
println("Rank: ", i, " -> permutation ", rank2permutation(perms, i))
end
Output:
$ julia ./permute_ranks.jl
Permutations: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
Permutation [3, 1, 2] -> rank 5
Rank: 1 -> permutation [1, 2, 3]
Rank: 2 -> permutation [1, 3, 2]
Rank: 3 -> permutation [2, 1, 3]
Rank: 4 -> permutation [2, 3, 1]
Rank: 5 -> permutation [3, 1, 2]
Rank: 6 -> permutation [3, 2, 1]
Permutation Ranking in Python
Comparing two arrays with the == operator doesn’t seem to work in Python. There may be a better way to compare arrays, but I decided to stringify the arrays and to compare the resulting strings.
def stringify(input):
return " ".join(map(str, input))
def permute(input):
temp = input.copy() # avoid modifying input perm with the sort
temp.sort()
return list(itertools.permutations(temp))
def permutation2rank(perms, input):
perms_str = map(stringify, perms)
input_str = stringify(input)
for index, value in enumerate(perms_str):
if value == input_str:
return index
def rank2permutation(permutation, rank):
return permutation[rank]
perm = [3, 1, 2]
perms = permute(perm)
print("Permutations: ", str(perms))
rank = permutation2rank(perms, perm)
print("Permutation ", perm, " -> rank ", rank)
for i in range(0, len(perms)):
print("Rank: ", i, " -> permutation ", rank2permutation(perms, i))
Output:
$ python3 ./permute_ranks.py
Permutations: [(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)]
Permutation [3, 1, 2] -> rank 4
Rank: 0 -> permutation (1, 2, 3)
Rank: 1 -> permutation (1, 3, 2)
Rank: 2 -> permutation (2, 1, 3)
Rank: 3 -> permutation (2, 3, 1)
Rank: 4 -> permutation (3, 1, 2)
Rank: 5 -> permutation (3, 2, 1)
Permutation Ranking in Ruby
def permute(in_list)
return in_list.sort.permutation(in_list.length).to_a
end
def permutation2rank(perms, input)
for i in 0..perms.length - 1
if perms[i] == input
return i
end
end
end
def rank2permutation(perms, index)
return perms[index]
end
perm_in = [3, 1, 2]
perms = permute(perm_in)
puts("Permutations: #{perms} \n")
print("Permutation #{perm_in} -> rank #{permutation2rank(perms, perm_in)} \n")
for i in 1..perms.length - 1
print("Rank: #{i} -> permutation #{rank2permutation(perms, i)} \n")
end
Output:
Permutations: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
Permutation [3, 1, 2] -> rank 4
Rank: 1 -> permutation [1, 3, 2]
Rank: 2 -> permutation [2, 1, 3]
Rank: 3 -> permutation [2, 3, 1]
Rank: 4 -> permutation [3, 1, 2]
Rank: 5 -> permutation [3, 2, 1]
Permutation Ranking in Javascript
JavaScript doesn’t seem to have a built-in permutation function. The permute function in the program below is derived from this Stack Overflow page. I liked it because of its functional style. When I used JavaScript around 2003-04 for Web page development, I did not like too much its somewhat clunky syntax. Taking a fresh look at it nowadays really changes my perception, it appears that the language has really improved in the meantime. I’ll try to look deeper into it as soon as I get some free time.
function permute(inputArray) {
let inAry = [...inputArray].sort(); //copy and sort input
return inAry.reduce(function permute(res, item, key, arr) {
return res.concat(arr.length > 1 && arr.slice(0, key)
.concat(arr.slice(key + 1))
.reduce(permute, [])
.map(function (perm) {
return [item].concat(perm);
}) || item);
}, []);
}
function permutation2rank(perms, in_perm) {
let input = JSON.stringify(in_perm)
for (var i = 0; i < perms.length; i++) {
// stringify permutations to enable comparison
if (JSON.stringify(perms[i]) == input) {
return i
}
}
}
function rank2permutation(perm_list, index) {
return perm_list[index]
}
let perm_in = [3, 1, 2];
let perms = permute(perm_in)
console.log(perms)
let rank = permutation2rank(perms, perm_in)
console.log("Permutation", perm_in, "has rank", rank)
for (var i = 0; i < perms.length; i++) {
console.log("Rank: ", i, " -> permutation ", rank2permutation(perms, i))
}
Output:
node /tmp/CUuyiMw4x0.js
[ [ 1, 2, 3 ],
[ 1, 3, 2 ],
[ 2, 1, 3 ],
[ 2, 3, 1 ],
[ 3, 1, 2 ],
[ 3, 2, 1 ] ]
Permutation [ 3, 1, 2 ] has rank 4
Rank: 0 -> permutation [ 1, 2, 3 ]
Rank: 1 -> permutation [ 1, 3, 2 ]
Rank: 2 -> permutation [ 2, 1, 3 ]
Rank: 3 -> permutation [ 2, 3, 1 ]
Rank: 4 -> permutation [ 3, 1, 2 ]
Rank: 5 -> permutation [ 3, 2, 1 ]
Wrapping up
The next week Perl Weekly Challenge will start soon. If you want to participate in this challenge, please check https://perlweeklychallenge.org/ and make sure you answer the challenge before 23:59 BST (British summer time) on July 31, 2022. And, please, also spread the word about the Perl Weekly Challenge if you can.
I am the author of the "Think Perl 6" book (O'Reilly, 2017) and I blog about the Perl 5 and Raku programming languages.
Leave a comment