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:

How to disable Unity animations in Ubuntu 14.04?

If you are running Ubuntu in VirtualBox or other virtualization platform, disabling all the animations improves the response of the OS to certain extent.

Starting with Ubuntu 12.10, MyUnity integration with the System Settings (as was the case in 12.04) has been removed. In 12.10 and above, which includes 13.04, 13.10 and 14.04, Compiz settings manager can be used to disable the required animations.

  • Step 1: Install Compiz Settings Manager12.
    sudo apt-get install compizconfig-settings-manager
  • Step 2: Disable Animations345
    • Start the application (from the Unity Dash)
    • Traverse to Unity plugin -> Experimental (tab)
    • Disable the animations as required.

References:

How did I improve the performance of my Ubuntu 12.04 system?

There are many web pages that outlines steps to be performed to increase the performance of your Ubuntu system. In this post, I would like to outline the steps that I have followed to increase the overall performance of the system. Most of the tweaks listed below were captured from the websites listed in the References section.

Disclaimer: If you do not know what you are doing, then it would be better to leave your working system as is. There is always a possiblity that you may destablize your system by modifying critical system settings. Please use caution when performing the below outlined steps. I have outlined the steps that I had performed; this by no means indicates that your system would perform better than it is. Use the below listed suggestions at your own risk.

  • Remove unwanted services using Boot-Up Manager (bum)1:
    • Install BUM: sudo apt-get install bum
    • Open BUM using: System -&gt; Administration -&gt; BootUP Manager or search for bum in Ubuntu Dash.
    • Or, execute sudo bum from comand line.
    • Disable the services that you do not prefer to auto-start as part of the system start-up sequence.
    • Refer to the reference links2 for more information on usuage of advanced usage of bum.
  • Remove few more services using sysv-rc-conf3:
    • sysv-rc-conf is a terminal GUI for managing services listed in /etc/rc[runlevel].d folder.
    • Install it using sudo apt-get install sysv-rc-conf
    • Start it using sudo sysv-rc-conf
    • Read about the tool using man sysv-rc-conf4
    • Use arrow keys to navigate and press space to enable or disable a service in a particular runlevel.
    • Press q to save and terminate the program.
    • Press r to revert the settings to the previous state (in case you have not yet saved the changes).
  • Disable/remove unused applications that run as ‘Background services’:
    • Use the solution mentioned at ‘Ask Ubuntu’5 to enable listing of services that auto-start along with Unity Desktop in the ‘Startup Applications’ menu. In summary execute the below commands (courtesy to Todd Partridge ‘Gen2ly’ – Ask Ubuntu)
      mkdir -p ~/.config/autostart # If not already created
      cd ~/.config/autostart
      cp /etc/xdg/autostart/*.desktop .
      sed -i "s/NoDisplay=true/NoDisplay=false/g" *.desktop
    • Click on the ‘Logout/Login’ icon on the ‘top-right’ corner of the Unity screen and select ‘Startup Applications control panel’ and disable the services that you do not use.
  • Remove the ‘indicator-messages’:
    • Its the ‘mail’ icon displayed on the ‘top-right’ corner of the Unity Desktop before the ‘Login/Logout’ and other menu items.
    • If you do not depend on it, you can execute the below commands to uninstall it.
      sudo apt-get autoremove indicator-messages
      sudo apt-get autoremove telepathy-indicator
  • Remove any left-over dependency packages that were not uninstalled when you uninstalled application:
    • Execute sudo apt-get autoremove
  • Use preload6:
    • If you prefer to let the system track the list of most frequently used applications and load them into the RAM before they are demanded, install ‘preload’ by executing sudo apt-get install preload.
    • Read How can I improve overall system performance? for some valuable input on preload.
  • Use BleachBit to unwanted files8:
    • As per the author, ‘BleachBit can be used to free cache, delete cookies, clear Internet history, shred temporary files and delete logs.
    • Install it using, sudo apt-get install bleachbit and run it by searching for the ‘BleachBit’ applition in the Unity Dash.
  • Adjust swappiness9:
    • Read the article – Ask Ubuntu – How do I configure swappiness? for some good insight into what swappiness is and how to configure it.
    • In summary, the swappiness value indicates how often the ‘swap’ file in the hard-disk is used.
    • By default, it may be set to 60 (in my system it was pre-set to 60). This implies that the kernel will swap the contents in the RAM to the disk when the RAM is about half full.
    • Check your the swappiness value set in your system using the command: cat /proc/sys/vm/swappiness
    • To change the value, open /etc/sysctl.conf (as root) and set/add the line, vm.swappiness = 10.
    • A value of 10 indicates that the swap file will only be used when the RAM is about 80% or 90% full.
  • Disable visual effects:
    • You can switch to a 2D desktop environment by installing: gnome-session-fallback using the command: sudo apt-get install gnome-session-fallback
    • You can also consider alternative desktop environments such as XFCE, LXDE etc. These are default in Xubuntu and Lubuntu respectively.

References: