- Added solutions to the task "Permutation Ranking" of week 174.

5 files changed, 426 insertions, 0 deletions

diff --git a/challenge-174/mohammad-anwar/java/theweeklychallenge/PermutationRanking.java b/challenge-174/mohammad-anwar/java/theweeklychallenge/PermutationRanking.java
new file mode 100644
index 0000000000..5436f82c01
--- /dev/null
+++ b/challenge-174/mohammad-anwar/java/theweeklychallenge/PermutationRanking.java
@@ -0,0 +1,124 @@
+package theweeklychallenge;
+
+/*
+
+Week 174:
+
+    https://theweeklychallenge.org/blog/perl-weekly-challenge-174
+
+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.
+
+Compile and Run:
+
+    mohammad-anwar/java$ javac theweeklychallenge/PermutationRanking.java
+    mohammad-anwar/java$ java  theweeklychallenge.PermutationRanking
+
+*/
+
+import java.util.List;
+import java.util.Arrays;
+import java.util.ArrayList;
+import java.util.stream.Collectors;
+import junit.framework.TestCase;
+import static junit.framework.Assert.*;
+
+public class PermutationRanking extends TestCase {
+
+    public static void main(String[] args) {
+        junit.textui.TestRunner.run(
+            theweeklychallenge.PermutationRanking.class);
+    }
+
+    public void test_permutation2rank() {
+        int[]                 n = {1, 0, 2};
+        List<List<Integer>> got = permutation2rank(n);
+        List<List<Integer>> exp = List.of(
+            List.of(0, 1, 2),
+            List.of(0, 2, 1),
+            List.of(1, 0, 2),
+            List.of(1, 2, 0),
+            List.of(2, 0, 1),
+            List.of(2, 1, 0)
+        );
+        assertEquals(exp, got);
+    }
+
+    public void test_rank2permutation() {
+        int[]       n = {1, 0, 2};
+        Integer[] got = rank2permutation(n, 1);
+        Integer[] exp = {0, 2, 1};
+        assertEquals(Arrays.toString(exp), Arrays.toString(got));
+    }
+
+    public static List<List<Integer>> permutation2rank(int[] n) {
+        List<List<Integer>> perm = new ArrayList<>();
+        Permutation(0, n, perm);
+        return sortPermutations(perm);
+    }
+
+    public static Integer[] rank2permutation(int[] n, int r) {
+        List<List<Integer>> rank = permutation2rank(n);
+        List<Integer> p = rank.get(r);
+        return p.toArray(new Integer[p.size()]);
+    }
+
+    private static List<List<Integer>> sortPermutations(List<List<Integer>> perm) {
+        String[] strPerm = new String[perm.size()];
+        int i = 0;
+        for(List<Integer> _perm : perm) {
+            strPerm[i] = _perm.stream()
+                              .map(String::valueOf)
+                              .collect(Collectors.joining(""));
+            i++;
+        }
+
+        Arrays.sort(strPerm);
+
+        List<List<Integer>> sortedPerm = new ArrayList<>();
+        for(int j = 0; j < strPerm.length; j++) {
+            String        str = strPerm[j];
+            String[] strArray = str.split("");
+            int[]    intArray = new int[strArray.length];
+
+            for(int k = 0; k < strArray.length; k++) {
+                intArray[k] = Integer.parseInt(strArray[k]);
+            }
+
+            List<Integer> intList = new ArrayList<Integer>(intArray.length);
+            for(int e : intArray) {
+                intList.add(e);
+            }
+
+            sortedPerm.add(intList);
+        }
+
+        return sortedPerm;
+    }
+
+    // https://www.w3resource.com/java-exercises/array/java-array-exercise-68.php
+    private static void Permutation(int i, int[] nums, List<List<Integer>> result) {
+        if (i == nums.length - 1) {
+            List<Integer> list = new ArrayList<>();
+            for(int n : nums) list.add(n);
+            result.add(list);
+        } else {
+            for(int j = i, l = nums.length; j < l; j++) {
+                int temp = nums[j];
+                nums[j]  = nums[i];
+                nums[i]  = temp;
+                Permutation(i + 1, nums, result);
+                temp     = nums[j];
+                nums[j]  = nums[i];
+                nums[i]  = temp;
+            }
+        }
+    }
+}
diff --git a/challenge-174/mohammad-anwar/perl/ch-2.pl b/challenge-174/mohammad-anwar/perl/ch-2.pl
new file mode 100644
index 0000000000..a681a40460
--- /dev/null
+++ b/challenge-174/mohammad-anwar/perl/ch-2.pl
@@ -0,0 +1,49 @@
+#!/usr/bin/perl
+
+=head1
+
+Week 174:
+
+    https://theweeklychallenge.org/blog/perl-weekly-challenge-174
+
+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.
+
+=cut
+
+use v5.36;
+use Test2::V0;
+use Algorithm::Combinatorics qw(permutations);
+
+is permutation2rank([1, 0, 2]),
+   [ [0, 1, 2],
+     [0, 2, 1],
+     [1, 0, 2],
+     [1, 2, 0],
+     [2, 0, 1],
+     [2, 1, 0],
+   ];
+
+is rank2permutation([0, 1, 2], 1),
+   [0, 2, 1];
+
+done_testing;
+
+#
+#
+# METHODS
+
+sub permutation2rank($array) {
+    return [ permutations([sort @$array]) ];
+}
+
+sub rank2permutation($array, $rank) {
+    return ( @{permutation2rank($array)} )[$rank];
+}
diff --git a/challenge-174/mohammad-anwar/python/ch-2.py b/challenge-174/mohammad-anwar/python/ch-2.py
new file mode 100644
index 0000000000..96b0492d4f
--- /dev/null
+++ b/challenge-174/mohammad-anwar/python/ch-2.py
@@ -0,0 +1,53 @@
+#!/usr/bin/python3
+
+'''
+
+Week 174:
+
+    https://theweeklychallenge.org/blog/perl-weekly-challenge-174
+
+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.
+
+'''
+
+import unittest
+import itertools
+
+def permutation2rank(array):
+    array.sort()
+    return list(itertools.permutations(array))
+
+def rank2permutation(array, rank):
+    p2r = permutation2rank(array)
+    return p2r[rank]
+
+#
+#
+# Unit test class
+
+class TestPermutationRanking(unittest.TestCase):
+    def test_permutation2rank(self):
+        exp = [ (0, 1, 2),
+                (0, 2, 1),
+                (1, 0, 2),
+                (1, 2, 0),
+                (2, 0, 1),
+                (2, 1, 0),
+              ]
+        got = permutation2rank([1, 0, 2])
+        self.assertEqual(exp, got)
+
+    def test_rank2permutation(self):
+        exp = (0, 2, 1)
+        got = rank2permutation([1, 0, 2], 1)
+        self.assertEqual(exp, got)
+
+unittest.main()
diff --git a/challenge-174/mohammad-anwar/raku/ch-2.raku b/challenge-174/mohammad-anwar/raku/ch-2.raku
new file mode 100644
index 0000000000..51bf7b271b
--- /dev/null
+++ b/challenge-174/mohammad-anwar/raku/ch-2.raku
@@ -0,0 +1,47 @@
+#!/usr/bin/env raku
+
+=begin pod
+
+Week 174:
+
+    https://theweeklychallenge.org/blog/perl-weekly-challenge-174
+
+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.
+
+=end pod
+
+use Test;
+
+is permutation2rank([1, 0, 2]),
+   [ [0, 1, 2],
+     [0, 2, 1],
+     [1, 0, 2],
+     [1, 2, 0],
+     [2, 0, 1],
+     [2, 1, 0],
+   ];
+
+is rank2permutation([0, 1, 2], 1),
+   [0, 2, 1];
+
+done-testing;
+
+#
+#
+# METHODS
+
+sub permutation2rank($array) {
+    return [ $array.sort.permutations ];
+}
+
+sub rank2permutation($array, $rank) {
+    return @(permutation2rank($array)).[$rank];
+}
diff --git a/challenge-174/mohammad-anwar/swift/ch-2.swift b/challenge-174/mohammad-anwar/swift/ch-2.swift
new file mode 100644
index 0000000000..3817a18e08
--- /dev/null
+++ b/challenge-174/mohammad-anwar/swift/ch-2.swift
@@ -0,0 +1,153 @@
+import Foundation
+
+/*
+
+Week 174:
+
+    https://theweeklychallenge.org/blog/perl-weekly-challenge-174
+
+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.
+
+ACTION:
+
+    $ swift ch-2.swift "1,0,2" 1
+
+*/
+
+enum ParamError: Error {
+    case missingList
+    case missingRank
+    case invalidList
+    case invalidRank
+}
+
+do {
+    let paramCount:Int = Int(CommandLine.argc)
+
+    if paramCount <= 1 {
+        throw ParamError.missingList
+    }
+
+    if paramCount <= 2 {
+        throw ParamError.missingRank
+    }
+
+    let list:String = CommandLine.arguments[1]
+    let rank:Int    = Int(CommandLine.arguments[2])!
+
+    if isValid(list) {
+        if rank >= 0 {
+            let arrays:[Int] = (list.components(separatedBy: ",")).map { Int($0)! }
+            print(rank2permutation(arrays, rank))
+        }
+        else {
+            throw ParamError.invalidRank
+        }
+    }
+    else {
+        throw ParamError.invalidList
+    }
+}
+catch ParamError.missingList {
+    print("Missing list.")
+}
+catch ParamError.missingRank {
+    print("Missing rank.")
+}
+catch ParamError.invalidList {
+    print("Invalid list.")
+}
+catch ParamError.invalidRank {
+    print("Invalid rank.")
+}
+catch let error {
+    print(error)
+}
+
+//
+//
+// Functions
+
+func permutation2rank(_ arrays:[Int]) -> [[Int]] {
+    return sortPermutations(arrays.allPermutations())
+}
+
+func rank2permutation(_ arrays:[Int], _ rank:Int) -> [Int] {
+    let perms:[[Int]] = permutation2rank(arrays)
+    return perms[rank]
+}
+
+func sortPermutations(_ perms: [[Int]]) -> [[Int]] {
+    var strArrays:[String] = []
+    for entry in perms {
+        strArrays.append(entry.reduce("") { $0 + "\($1)" })
+    }
+
+    strArrays.sort()
+
+    var intArrays:[[Int]] = []
+    for entry in strArrays {
+        intArrays.append(String(entry).compactMap { Int(String($0)) })
+    }
+
+    return intArrays
+}
+
+func isValid(_ list:String) -> Bool {
+    let pattern = "^[\\-?\\d\\,?\\s?]+$"
+    let regex   = try! NSRegularExpression(pattern: pattern)
+    let range   = NSRange(location: 0, length: list.utf16.count)
+
+    if regex.firstMatch(in: list, options: [], range: range) != nil {
+        return true
+    }
+    else {
+        return false
+    }
+}
+
+//
+//
+// Array extension borrowed from SO.
+// https://stackoverflow.com/questions/30586711/order-array-of-objects-into-every-possible-sequence-in-swift
+
+extension Array {
+    private var decompose : (head: Element, tail: [Element])? {
+        return (count > 0) ? (self[0], Array(self[1..<count])) : nil
+    }
+
+    private func between<T>(x: T, ys: [T]) -> [[T]] {
+        if let (head, tail) = ys.decompose {
+            return [[x] + ys] + between(x: x, ys: tail).map { [head] + $0 }
+        } else {
+            return [[x]]
+        }
+    }
+
+    private func permutations<T>(xs: [T]) -> [[T]] {
+        if let (head, tail) = xs.decompose {
+            return permutations(xs: tail) >>= { permTail in
+                self.between(x: head, ys: permTail)
+            }
+        } else {
+            return [[]]
+        }
+    }
+
+    func allPermutations() -> [[Element]] {
+        return permutations(xs: self)
+    }
+}
+
+infix operator >>=
+func >>=<A, B>(xs: [A], f: (A) -> [B]) -> [B] {
+    return xs.map(f).reduce([], +)
+}