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);
    }
}
Advertisements

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:

Django-nonrel + VirtualEnv + uWSGI + Nginx + ImportError: No module named wsgi

If your uWSGI configuration is causing the below error to be displayed in the logs:

from django.core.wsgi import get_wsgi_application>
ImportError: No module named wsgi

Check if you are using Django 1.3 or below. If yes, confirm if the below lines are listed in your wsgi.py file:

from django.core.wsgi import get_wsgi_application
application = get_wsgi_application()

Continue reading “Django-nonrel + VirtualEnv + uWSGI + Nginx + ImportError: No module named wsgi”

Is there a easier mechanism to parse arbitrary date strings in several different formats in Python?

I was in-need of parsing a date string value returned by PostgreSQL into something that can be manipulated in Python. After several hours of searching, I found a mechanism to accomplish this and have documented it here to help others who may encounter a similar situation in future.

# Install the python-dateutil library.

# In virtualenv environments:
pip install python-dateutil

# If you prefer to install system wide:
sudo pip install python-dateutil

# If you are using Ubuntu or an Ubuntu derived OS:
sudo apt-get install python-dateutil

# After installation, fire up the Python terminal and import dateutil parser.

>>>from dateutil.parser import parse
>>>parse("2012-08-16 14:25:05.265739")
datetime.datetime(2012, 8, 16, 14, 25, 5, 265739)

# The parse command converted the date time string into a valid datetime object.

Checkout http://labix.org/python-dateutil for more examples.


References:

Installation of psycopg2 fails within virtualenv folder in Ubuntu 12.04 – how do I fix this?

Recently, when I attempted to install the PostgreSQL adapter for Python ( psycopg2 ), in a virtualenv folder in Ubuntu 12.04, it failed. Upon attempting several solutions, I have boiled down to a fix that worked and decided to document it in an effort to help others resolve similar issue.

# Install the PostgreSQL development files (if you haven't installed them already).
sudo apt-get install postgresql-server-dev-all

# Install other required libraries
sudo apt-get install libpq-dev python-dev

# Attempt installation of psycopg2 within the virtualenv folder.
source /bin/activate
pip install psycopg2

# The installation of psycopg2 should proceed smoothly by now. If it still fails, try installing the postgresql-client libraries.
sudo apt-get install postgresql-client-common

# Attempt installation of psycopg2 again and hopefully it should work without issues.


References:

How to install Cassandra in Ubuntu Server 12.04?

Installation of Cassandra in the Ubuntu Server 12.04 can be performed in multiple ways. In this article, I will focus on utilizing the ‘apt-get’ command line utility to install ‘Cassandra’. This information is also documented at the ‘Cassanda Wiki’.

Please note that its recommended to have ‘Oracle JDK at-least version 6’ installed in the machine before installing Cassandra.

Step 1: Add the required repositories.

sudo echo "deb http://www.apache.org/dist/cassandra/debian 11x main" >> /etc/apt/sources.list;
sudo echo "deb-src http://www.apache.org/dist/cassandra/debian 11x main" >> /etc/apt/sources.list

Step 2: Update.

Continue reading “How to install Cassandra in Ubuntu Server 12.04?”

How to fix the Django error displayed when loading Twissandra for the first time?

Twissandra is a beautiful example project that can be used to learn the features of Cassandra. Its maintained by ‘Tyler Thobbs’. Please see https://github.com/twissandra/twissandra for more details on the Twissandra project.

This article attempts to provide a solution for the Django error that is displayed when you complete all the steps listed at the Twissandra GitHub Readme document and attempt to visit the Twissandra site for first time. When I came across this issue for the firs time, a through research on the solution led me to the fix posted at :Tod (Play Cassandra).

Error reported by the web page:

Error importing template source loader django.template.loaders.filesystem.load_template_source: "'module' object has no attribute 'load_template_source'"

One of the possible solution:

Continue reading “How to fix the Django error displayed when loading Twissandra for the first time?”