Compute the Index of a Permutation in C/C++

I've written a C++ code snippet to compute the index of permutation according to this post:


#include <stdlib.h>
#include <assert.h>
#include <stdio.h>

 * Compute factorial of n. It builds a factorial table lazily.
template <typename T>
T factorial(unsigned int n)
    static T * f = NULL;
    static unsigned int cur_max = 0;

    if (!f)
        f = (T*) malloc(1 * sizeof(T));
        f[0] = 1;

    assert(n >= 0);

    // need to extend the factorial table
    if (n > cur_max)
        f = (T *) realloc(f, (n + 1) * sizeof(T));

        for (unsigned int i = cur_max + 1; i <= n; ++ i)
            f[i] = f[i - 1] * i;

        cur_max = n;

    return f[n];

 * Compute the index of permutation according to
template <typename T, typename TP>
TP compute_index_of_permutation(const T * array, size_t array_size)
    TP permutation(0);

    assert(array_size > 0);

    if (array_size == 1)
        return 0;

    for (size_t i = 0; i < array_size - 1; ++ i)
        size_t count = 0;
        for (size_t j = i + 1; j < array_size; ++ j)
            if (array[i] > array[j])
                ++ count;

        if (count > 0)
            permutation += (array_size - i - 1) * factorial<TP>((unsigned int) count);

    return permutation;

 * A small main function for testing
int main()
#define STRING_A "bac"
#define STRING_B "dacb"

    int x = compute_index_of_permutation<char, int>(STRING_A, sizeof(STRING_A) - 1);
    double y = compute_index_of_permutation<char, double>(STRING_B, sizeof(STRING_B) - 1);

    printf("%d %e\n", x, y);

    return 0;

The code was written to be easily adapted into C code. To adapt the code above to C code, simply replace all template types with the type you want and remove all the template declaration.

Configure Proxy Using PAC Files on Firefox for Android

Firefox for Android does not provide a UI option for users to to configure Firefox to use PAC file for proxy settings, but we can use the about:config page to achieve this goal.

Type about:config into your Firefox address bar, and you'll see a list of options below. In the search box, type proxy to list all options related to proxy. There are two notable options listed here: network.proxy.type and network.proxy.autoconfig_url. Change network.proxy.type to 2 and network.proxy.autoconfig_url to the URL of the PAC file (Tap on the edit box below the configuration option twice to start edit the option). Close the about:config page and now Firefox should use the PAC file for proxy.

/images/configure-proxy-using-pac-files-on-firefox-for-android/1.thumbnail.png /images/configure-proxy-using-pac-files-on-firefox-for-android/2.thumbnail.png

To configure the proxy of Firefox on Android using a given proxy server and port, please see this article.

Control the LED on a USB WiFi Adapter on Linux

First, find the corresponding directory of this LED device in /sys/class/leds, such as /sys/class/leds/device_name, and switch your working directory to this directory. The device_name may be similar to the device driver of your wifi adapter. You should have a file named trigger and a file named brightness in this directory. cat trigger shows you available triggers to trigger the LED light, with the current trigger surrounded by brackets. Different triggers will turn on and off the LED in different cases. Use echo new-trigger > trigger to change trigger. cat brightness shows the current brightness of the LED. Use echo N > brightness to change brightness, where N is an integer.

For example, I have a USB wifi adapter with an Atheros AR9271 chip, which is powered by the driver ath9k_htc on Linux. When I plug in the device, I have a new directory /sys/class/leds/ath9k_htc-phy0 created on my system. cat trigger outputs

none cpu0 cpu1 cpu2 cpu3 usb-gadget usb-host rfkill0 phy0rx phy0tx phy0assoc phy0radio [phy0tpt]

Read more…

How to Insert 1 Bit Into An Integer

Inserting a bit into an integer, means to insert a bit into a specific position of an integer, with the highest bit removed. For example, for a one byte integer 11001010, if I insert a 1 at digit position 4, which is marked here 1100|1010 as |, the most significant bit, which is the left most 1, would be eliminated and the rest of the 3 bits on the left side of | would be shifted to the left for 1 bit.

This is not hard to implement, but surprisingly I cannot find any existing code snippet for such a simple job.

Here is the code snippet I wrote for C++ (which should also work for C with slight modification), and it can be easily translated into most other languages. Here, T is any integer type.

#include <stddef.h> // for size_t
template <typename T> // if used in C, remove this line and replace T with an integer type
T insert_bit(T n,   // The integer we are going to insert into
             size_t position, // position is the position of the new bit to be inserted
             bool new_bit) // whether the newly inserted bit is true or false
    T x = n;
    T y = x;
    x <<= 1;
    if (new_bit)
        x |= (((T) 1) << position);
        x &= ~(((T) 1) << position);
    x &= ((~((T) 0)) << position);
    y &= ~((~((T) 0)) << position);
    x |= y;
    return x;

Don't hesitate to comment if you think there is a better (more elegant or faster) way.

Install PHP Extensions on Shared Hosts

In this post, I will show you a workaround to install additional PHP extensions which are not available on your Linux/BSD shared host. Before you proceed, you should ask whether your shared hosting company has an official way to install or whether they can include the extension you need on their system, as this method is really only a workaround: it probably works, but there is no guarantee of stability, especially your shared hosting company upgrades PHP version.

I'll assume you have the basic knowledge of how to use a UNIX shell.

Read more…

Matching an Arbitrary Number Range in Regular Expression Using Capturing Groups

To match an arbitrary number range in a regular expression, is to match a string with a specific pattern which contains a number range. For example, to match with a pattern test{0..100}, where {0..100} denotes an integer not smaller than 0 and not larger 100, is such a case.

Although we already have some solutions to match a number range in regular expression, but they all make lengthy string and may lead to possible performance issue. In this post, I will provide an alternative solution to this problem, but it requires you to have control over the captured groups of the regex.

Read more…

Back up (Migrate) Homebrew Packages

As one of the most popular package manager on OS X, Homebrew is indeed a very nice tool to manage packages. However, when you want to back up your packages, or migrate the packages onto another machine, Homebrew didn't invent such a tool. If you are moving to an OS X of the same version, you can simply copy the Homebrew directory (default is /usr/local) to your new machine. Otherwise, we need to find a way to install the exactly same packages on your new machine. In order to accomplish the goal, I wrote a small piece of bash script to generate a restore script to install the packages.

Read more…