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.

Leave a comment

About laurent_r

user-pic I am the author of the "Think Perl 6" book (O'Reilly, 2017) and I blog about the Perl 5 and Raku programming languages.