Re: Seeking recursive solution to replace nested for-loops

From: Dave <davidr21_at_hotmail.com>
Date: 8 Mar 2004 20:18:27 -0800
Message-ID: <8244b794.0403082018.65ab69f0_at_posting.google.com>


[Quoted] afilonov_at_yahoo.com (Alex Filonov) wrote in message news:<336da121.0403080804.6fb55fc_at_posting.google.com>...
> davidr21_at_hotmail.com (Dave) wrote in message news:<8244b794.0403051147.281957af_at_posting.google.com>...
> > Cleaned up the code a little....
> >
>
> Looks great. Ever thought of writing LISP interpreter in PL/SQL?

[Quoted] Not sure if you are being sarcastic or not so I'll assume not... :)

[Quoted] I never considered it until now. I admit it was fun, but my implementation quickly breaks when a result is larger than 1999 characters long (I could boost that up to varchar2(4000) of course.) So an implementation utilizing objects, arrays, and/or tables would be better.

I think I would need to see some potential uses for it to consider it being a worthwhile task...but it would be fun.

Dave

>
> > create or replace function nullp(p_list in varchar2) return number
> > is
> > begin
> > if p_list is null or p_list = '()'
> > then
> > return 1;
> > else
> > return -1;
> > end if;
> > end;
> > /
> >
> > create or replace function listp(p_list in varchar2) return number
> > is
> > begin
> > if substr(p_list, 1, 1) = '(' and substr(p_list, -1, 1) = ')'
> > then
> > return 1;
> > else
> > return -1;
> > end if;
> > end;
> > /
> >
> > create or replace function car(p_list in varchar2) return varchar2
> > is
> > l_list varchar2(1999);
> > l_paren_cnt pls_integer;
> > begin
> > if listp(p_list) = -1 -- not a list
> > then
> > raise_application_error(-20101, p_list||' is not a list. Therefore
> > CAR cannot be used.');
> > elsif substr(p_list, 2, 1) != '(' -- first value is an atom
> > then
> > if instr(p_list, ',') > 0 then -- if its the only item in list,
> > return it removing trailing paren.
> > return substr(p_list, 2, instr(p_list, ',')-2);
> > else
> > return substr(p_list, 2, length(p_list)-2); -- else return the
> > first item only.
> > end if;
> > else
> >
> > l_paren_cnt := 0;
> > l_list := substr(p_list, 2);
> >
> > -- count the number of open parens in a row to use as index for
> > finding the correct closing paren.
> > while l_list is not null
> > loop
> > if substr(l_list, 1, 1) = '('
> > then
> > l_paren_cnt := l_paren_cnt + 1;
> > l_list := substr(l_list, 2);
> > else
> > return substr(p_list, 2, instr(p_list, ')', 1, l_paren_cnt)-1);
> > end if;
> > end loop;
> >
> > end if;
> > return null;
> > end;
> > /
> >
> > create or replace function cdr(p_list in varchar2) return varchar2
> > is
> > l_car varchar2(50);
> > l_result varchar2(1999);
> > begin
> > if listp(p_list) = -1
> > then
> > raise_application_error(-20102, p_list||' is not a list. Therefore
> > CDR cannot be used.');
> > else
> > l_car := car(p_list);
> > l_result := '('||substr(p_list, instr(p_list,
> > l_car)+length(l_car)+1);
> > if length(l_result) <= 2
> > then
> > return null; -- empty set
> > else
> > return l_result;
> > end if;
> > end if;
> > end;
> > /
> >
> > create or replace function list_length(p_list in varchar2) return
> > number
> > is
> > l_result varchar2(1999);
> > l_cnt pls_integer := 0;
> > begin
> > if listp(p_list) = -1
> > then
> > raise_application_error(-20103, p_list||' is not a list. Therefore
> > LENGTH cannot be used.');
> > else
> > l_result := p_list;
> > while nullp(l_result) = -1
> > loop
> > l_result := cdr(l_result);
> > l_cnt := l_cnt + 1;
> > end loop;
> > end if;
> >
> > return l_cnt;
> > end;
> > /
> >
> > create or replace function list(p_atom in varchar2) return varchar2
> > is
> > begin
> > return '('||p_atom||')';
> > end;
> > /
> >
> > create or replace function cons(p_list in varchar2, p_atom in
> > varchar2) return varchar2
> > is
> > begin
> > if nullp(p_list) = 1
> > then
> > return list(p_atom);
> > elsif nullp(p_atom) = 1
> > then
> > return p_list;
> > else
> > return substr(p_list, 1, length(p_list)-1)||','||p_atom||')';
> > end if;
> > end;
> > /
> >
> > create or replace procedure generate_combos(p_cnt in number, p_items
> > in varchar2, p_visited in varchar2, p_answer in out varchar2)
> > is
> > l_tmp_atom varchar2(50) := 'DUMMY';
> > l_rest_items varchar2(1999);
> > begin
> >
> > if p_cnt = 1
> > then
> > l_rest_items := p_items;
class="quotelev2">> > while nullp(l_rest_items) = -1
> > loop
> > l_tmp_atom := car(l_rest_items);
> > l_rest_items := cdr(l_rest_items);
> > p_answer := cons(p_answer, cons(p_visited, l_tmp_atom));
> > end loop;
> > else
> > l_rest_items := p_items;
> > while nullp(l_rest_items) = -1
> > loop
> > l_tmp_atom := car(l_rest_items);
> > l_rest_items := cdr(l_rest_items);
> > generate_combos(p_cnt-1, l_rest_items,
> > cons(p_visited,l_tmp_atom), p_answer);
> > end loop;
> > end if;
> > end;
> > /
> >
> > create or replace function get_combos_varchar(p_cnt in number, p_items
> > in varchar2) return varchar2
> > is
> > l_answer varchar2(1999);
> > begin
> >
> > if p_cnt <= 0
> > then
> > raise_application_error(-20103, 'Count cannot be less than 1.');
> > end if;
> >
> > if listp(p_items) = -1
> > then
> > raise_application_error(-20104, 'Items '||p_items||' must be in a
> > valid list.');
> > end if;
> >
> > if p_cnt > list_length(p_items)
> > then
> > raise_application_error(-20105, 'Count cannot be greater than the
> > length of the list.');
> > end if;
> >
> > generate_combos(p_cnt, p_items, null, l_answer);
> > return l_answer;
> > end;
> > /
> >
> > select get_combos_varchar(4, '(1,2,3,4,5,6)') from dual;
> >
> > create type list_type as object
> > (
> > list varchar2(50)
> > );
> > /
> >
> > create type list_table_type as table of list_type;
> > /
> >
> > CREATE OR REPLACE function get_combos_row(p_cnt in number, p_items in
> > varchar2) return list_table_type
> > pipelined
> > is
> > l_answer varchar2(1999);
> > begin
> > generate_combos(p_cnt, p_items, null, l_answer);
> > while nullp(l_answer) = -1
> > loop
> > pipe row ( list_type(car(l_answer)) );
> > l_answer := cdr(l_answer);
> > end loop;
> > return;
> > end;
> > /
> >
> > select get_combos_row(4, '(1,2,3,4,5,6)') from dual;
> >
> >
> >
> >
> > davidr21_at_hotmail.com (Dave) wrote in message news:<8244b794.0403050628.7cd47d0f_at_posting.google.com>...
> > > Now that your scalability issues are solved, ;) here is something on
> > > the subject.
> > >
> > > I got a little carried away with this because it was interesting. I
> > > ended up creating some LISP-like utility functions and processing this
> > > at the string level. But it is the algorithm I think you are after
> > > anyway....
> > >
> > > The bulk of the algorithm is in GENERATE_COMBOS and honestly, I didn't
> > > test it a lot or use the most efficient coding methods...but figured I
> > > would send it out to you.
> > >
> > > Let me know if this isn't what you were after...
> > >
> > > -- determines if string is a list
> > > create or replace function listp(p_list in varchar2) return number
> > > is
> > > begin
> > > if substr(p_list, 1, 1) = '(' and substr(p_list, -1, 1) = ')'
> > > then
> > > return 1;
> > > else
> > > return -1;
> > > end if;
> > > end;
> > > /
> > >
> > > -- pops first atom off of list
> > > create or replace function car(p_list in varchar2) return varchar2
> > > is
> > > l_list varchar2(500);
> > > l_paren_cnt number;
> > > begin
> > > if listp(p_list) = -1
> > > then
> > > return null;
> > > elsif substr(p_list, 2, 1) != '('
> > > then
> > > if instr(p_list, ',') > 0 then
> > > return substr(p_list, 2, instr(p_list, ',')-2);
> > > else
> > > return substr(p_list, 2, length(p_list)-2);
> > > end if;
> > > else
> > >
> > > l_paren_cnt := 0;
> > > l_list := substr(p_list, 2);
> > > while l_list is not null
> > > loop
> > > if substr(l_list, 1, 1) = '('
> > > then
> > > l_paren_cnt := l_paren_cnt + 1;
> > > l_list := substr(l_list, 2);
> > > else
> > > return substr(p_list, 2, instr(p_list, ')', 1, l_paren_cnt)-1);
> > > end if;
> > > end loop;
> > >
> > > end if;
> > > return null;
> > > end;
> > > /
> > >
> > > -- pops first atom off list and returns rest of list
> > > create or replace function cdr(p_list in varchar2) return varchar2
> > > is
> > > l_car varchar2(50);
> > > l_result varchar2(500);
> > > begin
> > > if listp(p_list) = -1
> > > then
> > > return null;
> > > else
> > > l_car := car(p_list);
> > > l_result := '('||substr(p_list, instr(p_list,
> > > l_car)+length(l_car)+1);
> > > if length(l_result) <= 2
> > > then
> > > return null;
> > > else
> > > return l_result;
> > > end if;
> > > end if;
> > > end;
> > > /
> > >
> > > -- creates a list by enclosing an atom in list parens
> > > create or replace function list(p_atom in varchar2) return varchar2
> > > is
> > > begin
> > > return '('||p_atom||')';
> > > end;
> > > /
> > >
> > > -- appends an atom to the end of an existing list
> > > create or replace function cons(p_list in varchar2, p_atom in
> > > varchar2) return varchar2
> > > is
> > > begin
> > > if p_list is null
> > > then
> > > return list(p_atom);
> > > elsif p_atom is null
> > > then
> > > return p_list;
> > > else
> > > return substr(p_list, 1, length(p_list)-1)||','||p_atom||')';
> > > end if;
> > > end;
> > > /
> > >
> > > CREATE OR REPLACE procedure GENERATE_COMBOS(p_cnt in number, p_items
> > > in varchar2, p_visited in varchar2 := null, p_answer in out varchar2)
> > > is
> > > l_tmp_atom_1 varchar2(32) := 'DUMMY';
> > > l_tmp_atom_2 varchar2(32) := 'DUMMY';
> > > l_rest_items_1 varchar2(500);
> > > l_rest_items_2 varchar2(500);
> > > begin
> > > if p_cnt = 1
> > > then
> > > l_rest_items_1 := p_items;
> > > while l_rest_items_1 is not null
> > > loop
> > > l_tmp_atom_1 := car(l_rest_items_1);
> > > l_rest_items_1 := cdr(l_rest_items_1);
> > > p_answer := cons(p_answer, cons(p_visited, l_tmp_atom_1));
> > > end loop;
> > > else
> > > l_rest_items_2 := p_items;
> > > while l_tmp_atom_2 is not null
> > > loop
> > > l_tmp_atom_2 := car(l_rest_items_2);
> > > l_rest_items_2 := cdr(l_rest_items_2);
> > > generate_combos(p_cnt-1, l_rest_items_2,
> > > cons(p_visited,l_tmp_atom_2), p_answer);
> > > end loop;
> > > end if;
> > >
> > > end;
> > > /
> > >
> > > CREATE OR REPLACE function get_combos_varchar(p_cnt in number, p_items
> > > in varchar2) return varchar2
> > > is
> > > l_answer varchar2(1999);
> > > begin
> > > generate_combos(p_cnt, p_items, null, l_answer);
> > > return l_answer;
> > > end;
> > > /
> > >
> > > select get_combos_varchar(4, '(1,2,3,4,5,6)') from dual;
> > >
> > > ((1,2,3,4),(1,2,3,5),(1,2,3,6),(1,2,4,5),(1,2,4,6),(1,2,5,6),(1,3,4,5),(1,3,4,6),(1,3,5,6),(1,4,5,6),(2,3,4,5),(2,3,4,6),(2,3,5,6),(2,4,5,6),(3,4,5,6))
> > >
> > > Dave
> > >
> > > Daniel Morgan <damorgan_at_x.washington.edu> wrote in message news:<1078335382.500969_at_yasure>...
> > >
> > >
> > >
> > > > Michelle Romano wrote:
> > > >
> > > > >>Ah...I see. Would you mind posting your current nested-loop solution
> > > > >>as a starting point?
> > > > >>
> > > > >>Thanks,
> > > > >>Dave
> > > > >
> > > > >
> > > > > Not at all...here it is. Note that this is a scaled down version,
> > > > > which will basically generate each combination via parm_list. This
> > > > > version will just display the pair combinations (using put_text). You
> > > > > will notice that I need to comment out the outer loop to prevent
> > > > > generating individual parameters. That is one of the issues with the
> > > > > nested for-loop solution. Within the loop, I also run a function
> > > > > against each combination generated (normally resides where I've added
> > > > > the comment "Run function against parm list here"). My goal is to
> > > > > create a function to return combination values to replace parm_list
> > > > > values currently generated by the for-loop.
> > > > >
> > > > > CREATE OR REPLACE procedure run_combo is
> > > > >
> > > > > parm_count pls_integer := 0;
> > > > > parm_list varchar2(500);
> > > > >
> > > > > Type parmArrayType is table of varchar2(100)
> > > > > index by pls_integer;
> > > > > parm_array parmArrayType;
> > > > > cursor ptx_cur is
> > > > > select parm
> > > > > from parm_table_xref
> > > > > order by parm;
> > > > >
> > > > > ptx_rec ptx_cur%rowtype;
> > > > >
> > > > > begin
> > > > > open ptx_cur;
> > > > >
> > > > > loop
> > > > > fetch ptx_cur into ptx_rec;
> > > > > exit when (ptx_cur%notfound);
> > > > >
> > > > > parm_count := parm_count + 1;
> > > > > parm_array(parm_count) := ptx_rec.parm;
> > > > >
> > > > > end loop;
> > > > >
> > > > > close ptx_cur;
> > > > >
> > > > > for i in 1..parm_count loop
> > > > >
> > > > > -- parm_list := parm_array(i);
> > > > > -- put_text(parm_list);
> > > > >
> > > > > -- Run function against parm list here --
> > > > >
> > > > > for j in i+1..parm_count loop -- parameter pairs
> > > > >
> > > > > parm_list:= parm_array(i)||', '||parm_array(j);
> > > > > put_text(parm_list);
> > > > >
> > > > > -- Run function against parm list here --
> > > > >
> > > > > end loop; -- j loop
> > > > >
> > > > > end loop; -- i loop
> > > > >
> > > > > end run_combo;
> > > > > /
> > > >
> > > > This appears to be an example of using version 7 PL/SQL when newer
> > > > constructs would greatly improve performance and scalability. Look
> > > > at this for comparison.
> > > >
> > > > CREATE OR REPLACE PROCEDURE nrows_at_a_time (
> > > > p_array_size IN PLS_INTEGER DEFAULT 100)
> > > > IS
> > > >
> > > > TYPE ARRAY IS TABLE OF all_objects%ROWTYPE;
> > > > l_data ARRAY;
> > > >
> > > > CURSOR c IS
> > > > SELECT *
> > > > FROM all_objects;
> > > >
> > > > BEGIN
> > > > OPEN c;
> > > > LOOP
> > > > FETCH c BULK COLLECT INTO l_data LIMIT p_array_size;
> > > >
> > > > FORALL i IN 1..l_data.COUNT
> > > > INSERT INTO t2 VALUES l_data(i);
> > > >
> > > > EXIT WHEN c%NOTFOUND;
> > > > END LOOP;
> > > > CLOSE c;
> > > > END nrows_at_a_time;
> > > > /
Received on Tue Mar 09 2004 - 05:18:27 CET

Original text of this message