Factorials as summation

The factorial function is defined as

n! = 1, if n = 0

= n(n-1)!, if n > 0

It is recursively defined using products.

It can also be expressed as a recursive summation

Let's see what 3! looks like

3! is simply 3 groups of 2 groups of 1

(1 + 1) +

(1 + 1) +

(1 + 1)

similarly 4! is 4 groups of 3 groups of 2 groups of 1 (I.e. four copies of the above)

((1 + 1) +

(1 + 1) +

(1 + 1) ) +

((1 + 1) +

(1 + 1) +

(1 + 1) ) +

((1 + 1) +

(1 + 1) +

(1 + 1) ) +

((1 + 1) +

(1 + 1) +

(1 + 1) )

Now we can visualize why factorials "grow" like crazy..(10! may take up an entire book)

"Why bats, Master Wayne?"

"Bats frighten me. It's time my enemies shared my dread."

-From Batman Begins

Stack permutation

I was trying to solve a stack permutation problem in taocp. The question asks us to find no: of permutations of n numbers from 1...n that can be generated using a stack. The no:s 1...n can be pushed into the stack in that order only. When an element is popped of the stack, it is appended to an output queue. Once all elements are in output queue, the order of elements in the queue is a permutation obtained using stack.

For ex:- To obtain 2,3,1 from 1,2,3 we follow the sequence of operations
push 1,push 2,pop 2,push 3,pop 3,pop 1
Not all permutations can be obtained using the stack (for ex: - 3,1,2).

Let the no: of permutations of 1...n be a(n) with a(0) = 1 (only empty permutation possible with no numbers).

We have to find a(n+1)

Suppose that nl no:s appear to left of "1" and nr no:s to right of "1" in a permutation. The process of obtaining a permutation for those nl numbers to the left of "1" can be considered as permuting 2...(nl+1) using a stack (The "1" at the bottom of the stack can be ignored). This no: will be the same as no: of permutations possible for 1...nl using a stack(Only the number of numbers matter).

Then no: of permutations possible for nl numbers to the left of "1" = a(nl).

Similarly no: of permutations possible for nr numbers to the right of "1" = a(nr).

For each of a(nl) permutations of numbers to the left, a(nr) permutations are possible for numbers to the right.

So a(nl)a(nr) permutations are possible for a particular position of "1" in the permutation.

Now nr = n - nl

So a(nl)a(nr) = a(nl)a(n-nl)

No: of elements to left of "1" can vary from 0...n.

So total number of permutations a(n+1) = sum(nl, 0, n) {a(nl)a(n-nl)} = a(0)a(n) + a(1)a(n-1) + .... + a(n)a(0)}

The term a(n) is simply the nth catalan number.

"Never believe in history, because history is created by those who win."

Driver's license

I got my driver's license today.....now I've got to learn to drive(properly)..

"I can only ride in 8's and drive in H's.."

- balu

PS: - This post should be dated 3-Sep-2008

Life update

I should start practicing for my driving license test...(breakevide... :-P)

A question to 8-year olds!!:-o

Find the smallest number that when divided by n yields the remainder (n-1) for 2 <= n <= 10 (ie. dividing n by 10 yields 9, by 9 yields 8...).

Believe it or not, this was one of the questions asked for a 3rd standard annual exam (state syllabus).

Design documents

Code and design are maintained as separate files in almost all software projects. A major task faced by all IT firms is ensuring the consistency between the source code and the corresponding design document. Code maintainers confused by inconsistent design documents are commonplace. Literate programming might be the first step towards a solution.

Exposing module internals using seq_file interface

Learn all about seq_file interface here
http://www.xenotime.net/linux/doc/seq_file_howto.txt

The seq_file mechanism provides a more straightforward, non-iterator style, interface. A driver writer may simply define show() with operations that output data to proc file.

First of all, we have to create a file in /proc. For this, we have to call create_proc_entry in our module initialization function.

struct proc_dir_entry *foo = create_proc_entry("foo", 0, NULL); /* This will create "/proc/foo" */

Then initialize the proc file operations structure
foo->proc_fops = &foo_proc_operations;

where foo_proc_operations is defined as,

static struct file_operations foo_proc_operations = {
.open = foo_proc_open,
.read = seq_read,
.llseek = seq_lseek,
.release = single_release,
};
seq_read, seq_lseek, and single_release are functions defined by Linux seq_file core.

Within foo_proc_open we have to call single_open() and pass it "show()", the function performing actual display.

return single_open(file, foo_proc_show, NULL);

Within foo_proc_show, we can use seq_{putc|puts|printf} to output data to "/proc/foo". These functions work like normal putc|puts|printf.

static int foo_proc_show(struct seq_file *m, void *v)
{
seq_puts(m, "Hello from foo\n"); /* write to our proc file */
return 0;
}

And finally don't forget to remove the proc file by calling,

remove_proc_entry("foo", NULL);