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:

How did I solve the “TypeError: Cannot read property ‘prototype’ of undefined” (NodeJS-ExpressJS-Redis)?

After installing Redis in our server as outlined in my last post on installation of Redis in CentOS 6.5, it was time for me to setup ExpressJS-NodeJS-Redis(Session Store) setup for the webapp that I am working on.

Everthing seemed perfect until I attempted to start the node server using the command: node app.js. I was welcomed with the below error message which highlighted the fact that connect-redis npm module had falied to connect to my Redis server.

var redis_store = require('connect-redis')(express);
TypeError: Cannot read property 'prototype' of undefined
    at module.exports (/home/nodeuser/node_modules/connect-redis/lib/connect-redis.js:96:41)
    at repl:1:43
    at REPLServer.self.eval (repl.js:110:21)
    at repl.js:249:20
    at REPLServer.self.eval (repl.js:122:7)
    at Interface.<anonymous> (repl.js:239:12)
    at Interface.EventEmitter.emit (events.js:95:17)
    at Interface._onLine (readline.js:202:10)
    at Interface._line (readline.js:531:8)
    at Interface._ttyWrite (readline.js:760:14)

Upon scouting Internet for answers, the solution posted by Andrei Karpushonak at StackOverflow post titled, ‘RedisStore – TypeError: Cannot read property ‘prototype’ of undefined‘ solved the issue.

Since I have used expressjs version 3.4.8 in my application, I had to use a compatible connect-redis npm. As per the StackOverflow post, the version mentioned by Andrei Karpushonak is 1.4.7.

I installed connect-redis-1.4.7 using the command: npm install --save connect-redis@1.4.7 and the webapp started without reporting any failures.

How did I install Zen-Coding in Eclipse?

As I have started creating an AngularJS-ExpressJS-NodeJS-Redis-Couchbase project, I like to utilize the power of Zen Coding1 in Eclipse.

Zen Coding allows for quicker development of HTML, XML, CSS files using custom abbreviations instead of writing all the tags. For example, the below snippet would result in a well formatted basic HTML 5 document structure to be created in your editor.

html:5

Output:

<!doctype html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Document</title>
</head>
<body>

</body>
</html>

On similar lines:

header+(div#container>div#sidebar+div#content>div#row>div#col-md-6+div#col-md-6)+footer

Would result in:

<header></header>
<div id="container">
    <div id="sidebar"></div>
    <div id="content">
        <div id="row">
            <div id="col-md-6"></div>
            <div id="col-md-6"></div>
        </div>
    </div>
</div>
<footer></footer>

Zen-Coding has been renamed as by its author – Sergey Chikuyonok2 as Emmet3 and can be downloaded form the github location https://github.com/emmetio/emmet.

Tutsplus has a good video tutorial on Zen-Coding4, which is worth a watch. Its about 5 minutes in length.

A quick review of the excellent Emmet documentation5 would provide a better insight into the substantial benefits of using Zen-Coding.

Zen-Coding plugin is available for many offline text editors that can be installed in your machine.

Many of the online services such as JSFiddle adn JS Bin also have support for Zen-Coding facility.

To install Zen-Coding (Emmet) in Eclipse, I tried downloading it from Eclipse-Marketplace – and it failed.

The below approch worked for me:
– Open Install New Software... within the Help menu in Eclipse IDE.
– Paste: http://emmet.io/eclipse/updates/ within the text-box after Work with: label.
– Wait for Eclipes to download the available software information and select Emmet from the displayed list.
– Click the Next button and follow the screens. Finally restart Eclipse for the changes to take effect.


References:

How did I solve Redis Installation failure in CentOS 6.5?

I decided to use Redis1 as a session store for my ExpressJS2-NodeJS3-Couchbase4 application.

The first step towards this was to download, compile and install Redis5.

The compressed tar.gz redis package is available at http://redis.io/download. I downloaded this package and extracted it in /opt directory. The installation page5 suggests executing the make command. In my case, the command failed with the below error:

....
make[3]: gcc: Command not found
make[3]: *** [net.o] Error 127
make[3]: Leaving directory `/opt/redis-2.8.9/deps/hiredis'
make[2]: *** [hiredis] Error 2
make[2]: Leaving directory `/opt/redis-2.8.9/deps'
make[1]: [persist-settings] Error 2 (ignored)
    CC adlist.o
/bin/sh: cc: command not found
make[1]: *** [adlist.o] Error 127
make[1]: Leaving directory `/opt/redis-2.8.9/src'
make: *** [all] Error 2

The solution for the above problem was to install gcc and make using the command: yum install gcc make.

Upon completion of the installation, I triggered, make once more. This time around, the make command failed and the errors indicated that few header files were missing.

make[1]: Entering directory `/opt/redis-2.8.9/src'
    CC adlist.o
In file included from adlist.c:34:
zmalloc.h:50:31: error: jemalloc/jemalloc.h: No such file or directory
zmalloc.h:55:2: error: #error "Newer version of jemalloc required"
make[1]: *** [adlist.o] Error 1
make[1]: Leaving directory `/opt/redis-2.8.9/src'
make: *** [all] Error 2

After scouting Internet for solutions67, I finally ended up with the below solution8.

cd /opt/redis-2.8.9/deps
make
cd ..
make

Compiling the contents of the deps (dependencies) folder before the issuing, make in the /opt/redis-2.8.9/ solved the problem.

If the make is successful, the redis-server binary would end up in the src folder (in my case, it would be /opt/redis-2.8.9/src). The server can be started using:

src/redis-server

Its time to start creating a start-up script (daemon process) and configure it to start during the runlevels 2, 3, 4 and 5.


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”

How do I install Eclipse Juno in Ubuntu 12.04?

There are numerous articles on the Internet where the mechanism to be followed to install Eclipse Juno in Ubuntu is well explained. This article is a reminder to myself on the commands that were used to install Eclipse Juno in my Ubuntu 12.04 machine.

# Download the Eclipse Juno package from http://www.eclipse.org/downloads/.
# I usually prefer the 'Eclipse Classic' package out of habit but feel free to grab the one that fits
# your requirement.

# As an example, let me download the 64-bit Ubuntu tar.gz image.
root@labs:~$ cd ~/Downloads
root@labs:~$ wget http://www.eclipse.org/downloads/download.php?file=/eclipse/downloads/drops4/R-4.2.1-201209141800/eclipse-SDK-4.2.1-linux-gtk-x86_64.tar.gz

# Untar the package. Example:
root@labs:~$ tar -zxvf eclipse-SDK-4.2.1-linux-gtk-x86_64.tar.gz

# The net result would be a folder named "eclipse". Lets copy it to /opt.
root@labs:~$ sudo mv "eclipse" /opt

# Lets add a link to the executable - "/opt/eclipse/eclipse" in /usr/bin for easier access.
root@labs:~$ ln -s "/opt/eclipse/eclipse" /usr/bin/eclipse

# Lets create a icon in the Unity Dashboard for convenience.

# Reference: https://ksearch.wordpress.com/2012/10/25/how-do-i-install-sublime-text-2-in-ubuntu-12-04/
# Fire up a text editor. I am using vim here. But, any text editor would do.
root@labs:~$ sudo vim /usr/share/applications/eclipse.desktop

# Add the below content to /usr/share/applications/eclipse.desktop and save it.

  [Desktop Entry]
  Version=1.0
  Name=Eclipse
  
  Exec=eclipse
  Terminal=false
  Icon=/opt/eclipse/icon.xpm
  Type=Application
  Categories=IDE;Development
  X-Ayatana-Desktop-Shortcuts=NewWindow

  [NewWindow Shortcut Group]
  Name=New Window
  Exec=eclipse
  TargetEnvironment=Unity

# All done.


References: