Saturday, October 01, 2005

May be now time to test ;)

This will really test our potential...(Just kidding)
How do you create a permutation & combination in sql

A permutation is an ordered arrangement of elements of a set.
For example, if I have the set {1, 2, 3}, the permutations of those elements are
(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), and (3, 2, 1).
The rule is that for n elements, you have a factorial n! number of permutations.

Try to make the answer easy to generalize for more numbers like suppose i give {1,2,3,4,5} i shud get the permutation of the numbers [ in total 5! ].

Let us try a basic one.

           CREATE TABLE Elements (i INTEGER NOT NULL);

i'm trying for the set {1,2,3}.
so inserting three values in the table

INSERT INTO Elements VALUES (1);
INSERT INTO Elements VALUES (2);
INSERT INTO Elements VALUES (3);

don't read more. try at ur hand in machine infront of u,
take it as challenge to do this ;)

FIRST ANSWER
SELECT e1.i A,e2.i B,e3.i C
FROM Elements e1,Elements e2,Elements e3
WHERE e1.i NOT IN (e2.i,e3.i)
AND e2.i NOT IN (e1.i,e3.i)
AND e3.i NOT IN (e2.i,e1.i)

This looks obvious and horrible answer. isn't ?.
This monster predicate will guarantee that all column values
in a row are unique.An improvement on this query can be made
by adding one more predicate to the where clause

FIRST ANSWER [ with modification ]
SELECT e1.i A,e2.i B,e3.i C
FROM Elements e1,Elements e2,Elements e3
WHERE (E1.i + E2.i + E3.i) = 6
AND e1.i NOT IN (e2.i,e3.i)
AND e2.i NOT IN (e1.i,e3.i)
AND e3.i NOT IN (e2.i,e1.i)

This improves things because most optimizers will see a predicate
of the structure [EXPRESSION] = [CONSTANT] and will execute it
before the and-ed chain of in() predicates. While not all rows
that total 6 are a permutation, all permutations will total to 6
for this set of integers.
It will definetly improve the query performance , agreed ?

Do you think this will be the solution ? No ,
we can try to write in different way.
Let's carry the totals trick one step further.
First,
redefine the Elements table to have a weight for each element
in the set: The weights are powers of two of the elements.

CREATE TABLE Elements_with_wgt(
i INTEGER NOT NULL ,
wgt INTEGER NOT NULL);

INSERT INTO Elements_with_wgtVALUES (1, 1);
INSERT INTO
Elements_with_wgtVALUES (2, 2);
INSERT INTO
Elements_with_wgtVALUES (3, 4);

Now, see the where clause how it becomes:

SECOND ANSWER
SELECT e1.i A,e2.i B,e3.i C
FROM Element1 e1,Element1 e2,Element1 e3
WHERE (E1.wgt + E2.wgt + E3.wgt) = 7

This does the whole filtering job for you and the in() predicates
are all unnecessary. In the previous solution we have seen the
elements shud be numbers as we are summming the value & adding
that to predicate, so the elements cant be other than numbers.
But this second answer also has another beneficial effect:
The elements can now be of any data type and
are not limited just to numbers.

1 comments:

Anonymous said...

Good Job done vetri. You are proving your interests. Do post such interesting things ,more frequently.

Good Learning for Me !

-Sathya