‘D’atabases : The Hidden ‘D’NA of our lives

February 15th, 2011

Almost TSP!! : Travelling Salesman Problem Solution through PL/SQL

Posted by Ritesh Anand in Uncategorized

Hi!!!!

 

/* PROBLEM STATEMENT

Here, the salesman is given the distance chart by his/her manager based on which

(s)he has to cover all the cities in the distance chart but ensure that (s)he

covers the MINIMUM DISTANCE. For better text, read http://en.wikipedia.org/wiki/Travelling_salesman_problem.

*/

 

 

 

 

/

drop table salesmans_scrambled_dist_chart;

create table salesmans_scrambled_dist_chart

(

      source      varchar2(5),

      destination varchar2(5),

      distance    number(5,0)

);

truncate table salesmans_scrambled_dist_chart;

insert into salesmans_scrambled_dist_chart values (‘-AGR-’,‘-DEL-’,250);

insert into salesmans_scrambled_dist_chart values (‘-AGR-’,‘-PTN-’,700);

insert into salesmans_scrambled_dist_chart values (‘-AGR-’,‘-GYA-’,800);

insert into salesmans_scrambled_dist_chart values (‘-AGR-’,‘-ALD-’,300);

insert into salesmans_scrambled_dist_chart values (‘-GYA-’,‘-ALD-’,500);

insert into salesmans_scrambled_dist_chart values (‘-ALD-’,‘-PTN-’,333);

insert into salesmans_scrambled_dist_chart values (‘-ALD-’,‘-DEL-’,601);

insert into salesmans_scrambled_dist_chart values (‘-GYA-’,‘-PTN-’,100);

insert into salesmans_scrambled_dist_chart values (‘-PTN-’,‘-DEL-’,1050);

insert into salesmans_scrambled_dist_chart values (‘-DEL-’,‘-GYA-’,1100);

commit;

create or replace view v_distance_chart as

select distinct

      source,

      destination,

      distance

FROM

      (

      SELECT

            source,

            destination,

            distance

      FROM

            salesmans_scrambled_dist_chart

      UNION ALL

      SELECT

            destination AS source,

            source  AS destination,

            distance

      FROM

            salesmans_scrambled_dist_chart);

/

 

create or replace view v_all_cities as

select

      city,

      rownum as sno

from

(select distinct

      source as city

from

      v_distance_chart);

/

 

drop table all_cities;

create table all_cities

(

      sno   number(2,0),

      city  varchar2(5)

);

truncate table all_cities;

 

insert into all_cities(sno, city) select sno, city from v_all_cities;

commit;

/

create or replace package pkg_salesman_scramble is

      procedure scramble_cities;

      function get_sql_city_sequence return varchar2;

end pkg_salesman_scramble;

/

 

create or replace package body pkg_salesman_scramble is

      procedure scramble_cities is

            v_retval    number(2,0);

      begin

            dbms_output.put_line(‘uninplemented!!!’);

      end scramble_cities;

     

      function get_sql_city_sequence return varchar2 is

            v_sql_stmt        varchar2(4000);

            v_sql_col1        varchar2(1000);

            v_sql_col2        varchar2(1000);

            v_sql_tbl         varchar2(500);

            v_sql_where       varchar2(1500);

            v_no_of_elements  number(2,0);

            v_index                 number(2,0);

            v_inner_index           number(2,0);

            v_bool                  number(1,0);

            v_pipe                  varchar2(4);

            v_add             varchar2(4);

            v_comma                 varchar2(3);

            v_and             varchar2(5);

      begin

            v_bool := 0;

            select count(*) into v_no_of_elements from all_cities;

            v_pipe := ;

            v_add := ;                             

            v_comma := ;

            v_and := ;

            for v_index in 1..v_no_of_elements

            loop

                  –if v_index = v_no_of_elements

                  –then

                      v_index_X := 1;

                  –else

                      v_index_X := v_index + 1;

                  –end if;

 

                  v_sql_col1 := v_sql_col1 || v_pipe || ‘nvl(t’ || v_index || ‘.CITY,””)’;

                  if v_index > 1 then

                        v_sql_col2 := v_sql_col2 || v_add || ‘distance_between_cities(t’ ||  v_index || ‘.city, t’ || to_char(v_index - 1) || ‘.city)’;

                  else

                        v_sql_col2 := 0;

                  end if;

                  v_sql_tbl := v_sql_tbl || v_comma || ‘all_cities t’ || v_index;

 

                  v_inner_index := v_index + 1;            

                  for v_inner_index in v_index + 1 .. v_no_of_elements

                  loop

                        if v_bool = 1 then

                              v_pipe := ‘ || ‘;

                              v_add := ‘ + ‘;

                              v_comma := ‘ , ‘;

                              v_and := ‘ AND ‘;

                        end if;

                        v_sql_where :=  v_sql_where || v_and || ‘ t’|| v_index ||‘.SNO != t’|| v_inner_index ||‘.SNO ‘;

                        v_bool := 1;

                  end loop;

            end loop;

 

            –v_sql_stmt := ’select CITY as combinations from scrambler_2011 where sno != 0 union all ‘;

            v_sql_stmt :=  v_sql_stmt ||‘ select ‘ || v_sql_col1 ||‘ as route, ‘ || v_sql_col2 ||‘ as distance_to_be_covered FROM ‘ || v_sql_tbl || ‘ WHERE ‘ || v_sql_where || ‘ order by distance_to_be_covered’;

 

            return(v_sql_stmt);

      end get_sql_city_sequence;

end pkg_salesman_scramble;

/

 

create or replace function distance_between_cities( v_city1 varchar, v_city2 varchar) return number is

      v_retval    number(5,0);

begin

      select

            distance into v_retval

      from v_distance_chart

      where      

            source = v_city1

      and   destination = v_city2;

           

      return v_retval;

end distance_between_cities;

/

           

– select pkg_salesman_scramble.get_sql_city_sequence() from dual; — pick the output and execute the dynamic sql, say str_dyn_sql so generated.

– execute str_dyn_sql

February 14th, 2011

Oracle Package / Stored Procedure to generate distinct scrambled combination of given elements

Posted by Ritesh Anand in Uncategorized

Due to my ‘lazy’ mind fidgeting around, I came up with the following :-)

  1. the following article gives the complete code (yes, it’s redistributable!) to generate the distinct alphabets that are possible, if the list of alphabets to be used are known [in the table - elements_for_scramble] (through Oracle PL/SQL - pkg_scrambler )
  2. as a part of solving the business problem, you will also learn the basics of SQL and  PL/SQL in oracle).

So, without further ado, here it goes:

 

 

–=: LOADER :=

/

drop table elements_for_scramble;

/

create table elements_for_scramble

(

      sno     number(5,0),

      avlbl_alphabet  varchar2(5)

);

/

truncate table elements_for_scramble;

insert into elements_for_scramble values (0,NULL); - THIS IS THE CRITICAL PIECE. SPEND SOME TIME TO UNDERSTAND THIS ENTRY.

insert into elements_for_scramble values (1,‘O’);

insert into elements_for_scramble values (2,‘N’);

insert into elements_for_scramble values (3,‘E’);

insert into elements_for_scramble values (4,‘K’);

commit;

/*

 

=: FRAMEWORK - for 3 elements in the elements_for_scramble table. :=

select

      AVLBL_ALPHABET as combinations

from

      elements_for_scramble

where

      sno   != 0

union all

select distinct

      t1.AVLBL_ALPHABET|| t2.AVLBL_ALPHABET || t3.AVLBL_ALPHABET as combinations

from

      elements_for_scramble t1,

      elements_for_scramble t2,

      elements_for_scramble t3

where

(     t1.sno != t2.sno

AND   t1.sno != t3.sno

AND   t2.sno != t3.sno);

*/

 

–=: GENERIC :=

create or replace package pkg_scrambler is

      procedure load_elements;

      procedure scramble_elements;

      function get_sql_stmt return varchar2;

end pkg_scrambler;

/

 

create or replace package body pkg_scrambler is

      procedure load_elements is

            v_no_elements     number(2,0);

      begin      

            dbms_output.put_line(‘Hello!’);          

      end load_elements;

     

      procedure scramble_elements is

            v_sql_stmt        varchar2(4000);

      begin

            v_sql_stmt := get_sql_stmt();

            execute immediate v_sql_stmt;

      end scramble_elements;

     

      function get_sql_stmt return varchar2 is

            v_sql_stmt        varchar2(4000);

            v_sql_col1        varchar2(1000);

            v_sql_col2        varchar2(1000);

            v_sql_tbl         varchar2(500);

            v_sql_where       varchar2(1500);

            v_no_of_elements  number(2,0);

            v_index                 number(2,0);

            v_inner_index           number(2,0);

            v_bool                  number(1,0);

            v_pipe                  varchar2(4);

            v_comma                 varchar2(3);

            v_and             varchar2(5);

      begin

            v_bool := 0;

            select count(*) - 1 into v_no_of_elements from elements_for_scramble;

            for v_index in 1..v_no_of_elements

            loop

                  –if v_index = v_no_of_elements

                  –then

                      v_index_X := 1;

                  –else

                      v_index_X := v_index + 1;

                  –end if;

                 

                  v_sql_col1 := v_sql_col1 || v_pipe || ‘nvl(t’ || v_index || ‘.AVLBL_ALPHABET,””)’;

                  v_sql_col2 := v_sql_col2 || v_pipe || ‘to_char(t’ || v_index || ‘.SNO)’;

                  v_sql_tbl := v_sql_tbl || v_comma || ‘elements_for_scramble t’ || v_index;

 

                  v_inner_index := v_index + 1;            

                  for v_inner_index in v_index + 1 .. v_no_of_elements

                  loop

                        if v_bool = 1 then

                              v_pipe := ‘ || ‘;

                              v_comma := ‘ , ‘;

                              v_and := ‘ AND ‘;

                        else

                              v_pipe := ;

                              v_comma := ;

                              v_and := ;

                        end if;

                        v_sql_where :=  v_sql_where || v_and || ‘ (t’|| v_index ||‘.SNO != t’|| v_inner_index ||‘.SNO OR t’|| v_index ||‘.SNO = 0)’;

                        v_bool := 1;

                  end loop;

            end loop;

           

            –v_sql_stmt := ’select AVLBL_ALPHABET as combinations from elements_for_scramble where sno != 0 union all ‘;

            v_sql_stmt :=  v_sql_stmt ||‘ select distinct ‘ || v_sql_col1 || ‘ as combination_AVLBL_ALPHABET,’ || v_sql_col2 ||‘ as SNO FROM ‘ || v_sql_tbl || ‘ WHERE ‘ || v_sql_where ;

            v_sql_stmt := ’select distinct combination_AVLBL_ALPHABET from (’ || v_sql_stmt || ‘) where combination_AVLBL_ALPHABET IS NOT NULL ORDER BY length(combination_AVLBL_ALPHABET), combination_AVLBL_ALPHABET;’;

            return(v_sql_stmt);

      end get_sql_stmt;

end pkg_scrambler;

/

Bad Behavior has blocked 0 access attempts in the last 7 days.