How to generate permutations of the elements in an array

Backtracking technique can be employed to generate a list of permutations of the elements in an array.

For every iteration, we choose an element as a prefix and recursively permute the remaining elements. The order of growth of algorithm is O(n!).

import java.util.Arrays;

public class ArrayPermutation {

    private static void exch(Comparable[] a, int i, int j) {
        Comparable t = a[i];
        a[i] = a[j];
        a[j] = t;
    }

    private static void permute(Comparable[] a, int lo, int hi) {
        if (hi <= lo) {
            System.out.println(Arrays.toString(a));
            return;
        }
        for (int i = lo; i <= hi; i++) {
            exch(a, lo, i);
            permute(a, lo + 1, hi);
            exch(a, i, lo);
        }
    }

    public static void permute(Comparable[] a) {
        permute(a, 0, a.length - 1);
    }

    // == Test Client =========================================================
    public static void main(String[] args) {
        // 1. Permute characters in an array.
        Character[] ch = { 'A', 'B', 'C', 'D' };
        permute(ch);

         // 2. Permute Integers in an array.
         Integer[] in = { 1, 2, 3, 4, 5 };
         permute(in);
    }
}

Programmatic solution to convert Roman numerals to Decimals

It has been a long weekend. While browsing around, I came across the Alien Numbers1 problem which is part of the Google Code Jam practice problem set.

Though I am yet to figure out a right algorithm to solve the ‘Alien Numbers’ problem, it turns out that it is similar to a problem of converting numerals into different base systems.

This drove me to think on a possiblity of programming a solution to convert Roman Numerals2 into their respective decimal notation. Here is the algorithm that I ended up with.

  1. Create a dictionary of critical mappings.
    • The critical Roman numerals are I, V, X, L, C, D, M which represent 1, 5, 10, 50, 100, 500 and 1000 respectively.
  2. Understand the numbering sequence.
    • A Roman numeral written before another indicates substraction of value where as a Roman numeral after the current one indicates addition.
    • For example:
      • XC is 90 i.e. C=100, X=10; since X is before C, substract 10 from 100 resulting in 90.
      • Similarly, XCX is 100 because the first two characters, XC result in 90 which is followed by X, therefore, add 10 to 90 resulting in 100.
  3. To support the logic mentioned in point 2 above, I decided to use a stack.
    • Whenever the input contains a Roman numeral whose value is less than the next Roman numeral in the input sequence, it is pushed to the stack.
  4. If the current Roman numeral is greater than the next one, the contents of the stack are popped and the cumulative sum of the values of the Roman numerals popped from the stack is substracted from the value of the current Roman numeral under consideration.
    • For example:
      • Consider the Roman numerals to be converted to decimal as XCV.
      • The input pointer starts reading input from X and finds that the next numeral is C whose value is greater than X. Therefore, X is pushed to the stack.
      • During the next iteration, the input pointer reads C and finds V as the next successive numeral.
      • Since V is lesser than C in value, the contents of the stack are popped, the value X is substracted from C and the result is stored in a variable (named, output in the program below).
  5. If you have some suggestions for improvement, please feel free to share your thoughts as comments to this post.
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class NumberSystem {
    public static long romanToBaseTen(String roman) {
        Map<Character, Integer> m = new HashMap<>();
        long output = 0;

        // Stack to store numerals that should be considered to be substracted.
        Stack<Character> s = new Stack<>();

        // Store decimal values of critical Roman Numerals.
        m.put('I', 1);
        m.put('V', 5);
        m.put('X', 10);
        m.put('L', 50);
        m.put('C', 100);
        m.put('D', 500);
        m.put('M', 1000);

        for (int i = 0; i < roman.length(); i++) {
            int curCharValue = m.get(roman.charAt(i));
            int nextCharValue = 0;

            // Boundary check - so that we do not cause an exception testing
            // beyond array limits.
            if (i < roman.length() - 1) {
                nextCharValue = m.get(roman.charAt(i + 1));
            }

            if (curCharValue < nextCharValue) {
                s.push(roman.charAt(i));
            } else {
                long temp = 0;
                while (s.isEmpty() == false) {
                    temp += m.get(s.pop());
                }

                // Safety check. Cumulative sum of the contents of the stack
                // should never be more than the current char value. If its
                // true, we have an invalid Roman Numeral representation.
                if (temp > curCharValue) {
                    System.err
                            .println("Invalid Roman Numeral representation found while scanning the Roman Numeral: "
                                    + roman.charAt(i)
                                    + " at position: "
                                    + i
                                    + ".");
                    System.exit(1);
                }
                curCharValue -= temp;
                output += curCharValue;
            }
        }
        return output;
    }

    // Test the conversation logic.
    public static void main(String[] args) {
        org.junit.Assert.assertEquals(romanToBaseTen("I"), 1);
        org.junit.Assert.assertEquals(romanToBaseTen("II"), 2);
        org.junit.Assert.assertEquals(romanToBaseTen("III"), 3);
        org.junit.Assert.assertEquals(romanToBaseTen("IV"), 4);
        org.junit.Assert.assertEquals(romanToBaseTen("V"), 5);
        org.junit.Assert.assertEquals(romanToBaseTen("VI"), 6);
        org.junit.Assert.assertEquals(romanToBaseTen("VII"), 7);
        org.junit.Assert.assertEquals(romanToBaseTen("VIII"), 8);
        org.junit.Assert.assertEquals(romanToBaseTen("IX"), 9);
        org.junit.Assert.assertEquals(romanToBaseTen("X"), 10);
        org.junit.Assert.assertEquals(romanToBaseTen("XI"), 11);
        org.junit.Assert.assertEquals(romanToBaseTen("XII"), 12);
        org.junit.Assert.assertEquals(romanToBaseTen("XIII"), 13);
        org.junit.Assert.assertEquals(romanToBaseTen("XIV"), 14);
        org.junit.Assert.assertEquals(romanToBaseTen("XV"), 15);
        org.junit.Assert.assertEquals(romanToBaseTen("XVI"), 16);
        org.junit.Assert.assertEquals(romanToBaseTen("XVII"), 17);
        org.junit.Assert.assertEquals(romanToBaseTen("XVIII"), 18);
        org.junit.Assert.assertEquals(romanToBaseTen("XIX"), 19);
        org.junit.Assert.assertEquals(romanToBaseTen("XX"), 20);
        org.junit.Assert.assertEquals(romanToBaseTen("XXI"), 21);
        org.junit.Assert.assertEquals(romanToBaseTen("XXII"), 22);
        org.junit.Assert.assertEquals(romanToBaseTen("XXIII"), 23);
        org.junit.Assert.assertEquals(romanToBaseTen("XXIV"), 24);
        org.junit.Assert.assertEquals(romanToBaseTen("XXV"), 25);
        org.junit.Assert.assertEquals(romanToBaseTen("XXVI"), 26);
        org.junit.Assert.assertEquals(romanToBaseTen("XXVII"), 27);
        org.junit.Assert.assertEquals(romanToBaseTen("XXVIII"), 28);
        org.junit.Assert.assertEquals(romanToBaseTen("XXIX"), 29);
        org.junit.Assert.assertEquals(romanToBaseTen("XXX"), 30);
        org.junit.Assert.assertEquals(romanToBaseTen("XXXI"), 31);
        org.junit.Assert.assertEquals(romanToBaseTen("XXXII"), 32);
        org.junit.Assert.assertEquals(romanToBaseTen("XXXIII"), 33);
        org.junit.Assert.assertEquals(romanToBaseTen("XXXIV"), 34);
        org.junit.Assert.assertEquals(romanToBaseTen("XXXV"), 35);
        org.junit.Assert.assertEquals(romanToBaseTen("XXXVI"), 36);
        org.junit.Assert.assertEquals(romanToBaseTen("XXXVII"), 37);
        org.junit.Assert.assertEquals(romanToBaseTen("XXXVIII"), 38);
        org.junit.Assert.assertEquals(romanToBaseTen("XXXIX"), 39);
        org.junit.Assert.assertEquals(romanToBaseTen("XL"), 40);
        org.junit.Assert.assertEquals(romanToBaseTen("XLI"), 41);
        org.junit.Assert.assertEquals(romanToBaseTen("XLII"), 42);
        org.junit.Assert.assertEquals(romanToBaseTen("XLIII"), 43);
        org.junit.Assert.assertEquals(romanToBaseTen("XLIV"), 44);
        org.junit.Assert.assertEquals(romanToBaseTen("XLV"), 45);
        org.junit.Assert.assertEquals(romanToBaseTen("XLVI"), 46);
        org.junit.Assert.assertEquals(romanToBaseTen("XLVII"), 47);
        org.junit.Assert.assertEquals(romanToBaseTen("XLVIII"), 48);
        org.junit.Assert.assertEquals(romanToBaseTen("XLIX"), 49);
        org.junit.Assert.assertEquals(romanToBaseTen("L"), 50);
        org.junit.Assert.assertEquals(romanToBaseTen("LI"), 51);
        org.junit.Assert.assertEquals(romanToBaseTen("LII"), 52);
        org.junit.Assert.assertEquals(romanToBaseTen("LIII"), 53);
        org.junit.Assert.assertEquals(romanToBaseTen("LIV"), 54);
        org.junit.Assert.assertEquals(romanToBaseTen("LV"), 55);
        org.junit.Assert.assertEquals(romanToBaseTen("LVI"), 56);
        org.junit.Assert.assertEquals(romanToBaseTen("LVII"), 57);
        org.junit.Assert.assertEquals(romanToBaseTen("LVIII"), 58);
        org.junit.Assert.assertEquals(romanToBaseTen("LIX"), 59);
        org.junit.Assert.assertEquals(romanToBaseTen("LX"), 60);
        org.junit.Assert.assertEquals(romanToBaseTen("LXI"), 61);
        org.junit.Assert.assertEquals(romanToBaseTen("LXII"), 62);
        org.junit.Assert.assertEquals(romanToBaseTen("LXIII"), 63);
        org.junit.Assert.assertEquals(romanToBaseTen("LXIV"), 64);
        org.junit.Assert.assertEquals(romanToBaseTen("LXV"), 65);
        org.junit.Assert.assertEquals(romanToBaseTen("LXVI"), 66);
        org.junit.Assert.assertEquals(romanToBaseTen("LXVII"), 67);
        org.junit.Assert.assertEquals(romanToBaseTen("LXVIII"), 68);
        org.junit.Assert.assertEquals(romanToBaseTen("LXIX"), 69);
        org.junit.Assert.assertEquals(romanToBaseTen("LXX"), 70);
        org.junit.Assert.assertEquals(romanToBaseTen("LXXI"), 71);
        org.junit.Assert.assertEquals(romanToBaseTen("LXXII"), 72);
        org.junit.Assert.assertEquals(romanToBaseTen("LXXIII"), 73);
        org.junit.Assert.assertEquals(romanToBaseTen("LXXIV"), 74);
        org.junit.Assert.assertEquals(romanToBaseTen("LXXV"), 75);
        org.junit.Assert.assertEquals(romanToBaseTen("LXXVI"), 76);
        org.junit.Assert.assertEquals(romanToBaseTen("LXXVII"), 77);
        org.junit.Assert.assertEquals(romanToBaseTen("LXXVIII"), 78);
        org.junit.Assert.assertEquals(romanToBaseTen("LXXIX"), 79);
        org.junit.Assert.assertEquals(romanToBaseTen("LXXX"), 80);
        org.junit.Assert.assertEquals(romanToBaseTen("LXXXI"), 81);
        org.junit.Assert.assertEquals(romanToBaseTen("LXXXII"), 82);
        org.junit.Assert.assertEquals(romanToBaseTen("LXXXIII"), 83);
        org.junit.Assert.assertEquals(romanToBaseTen("LXXXIV"), 84);
        org.junit.Assert.assertEquals(romanToBaseTen("LXXXV"), 85);
        org.junit.Assert.assertEquals(romanToBaseTen("LXXXVI"), 86);
        org.junit.Assert.assertEquals(romanToBaseTen("LXXXVII"), 87);
        org.junit.Assert.assertEquals(romanToBaseTen("LXXXVIII"), 88);
        org.junit.Assert.assertEquals(romanToBaseTen("LXXXIX"), 89);
        org.junit.Assert.assertEquals(romanToBaseTen("XC"), 90);
        org.junit.Assert.assertEquals(romanToBaseTen("XCI"), 91);
        org.junit.Assert.assertEquals(romanToBaseTen("XCII"), 92);
        org.junit.Assert.assertEquals(romanToBaseTen("XCIII"), 93);
        org.junit.Assert.assertEquals(romanToBaseTen("XCIV"), 94);
        org.junit.Assert.assertEquals(romanToBaseTen("XCV"), 95);
        org.junit.Assert.assertEquals(romanToBaseTen("XCVI"), 96);
        org.junit.Assert.assertEquals(romanToBaseTen("XCVII"), 97);
        org.junit.Assert.assertEquals(romanToBaseTen("XCVIII"), 98);
        org.junit.Assert.assertEquals(romanToBaseTen("XCIX"), 99);
        org.junit.Assert.assertEquals(romanToBaseTen("C"), 100);
        org.junit.Assert.assertEquals(romanToBaseTen("DI"), 501);
        org.junit.Assert.assertEquals(romanToBaseTen("DL"), 550);
        org.junit.Assert.assertEquals(romanToBaseTen("DXXX"), 530);
        org.junit.Assert.assertEquals(romanToBaseTen("DCCVII"), 707);
        org.junit.Assert.assertEquals(romanToBaseTen("DCCCXC"), 890);
        org.junit.Assert.assertEquals(romanToBaseTen("MD"), 1500);
        org.junit.Assert.assertEquals(romanToBaseTen("MDCCC"), 1800);
        org.junit.Assert.assertEquals(romanToBaseTen("CM"), 900);

        System.out.println("All done!");
    }
}

References: