## 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)
```

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 Coding`1 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">
<meta charset="UTF-8">
<title>Document</title>
<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.

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]: *** [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)
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'
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]: 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()```

## 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

# As an example, let me download the 64-bit Ubuntu tar.gz image.

# 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: