Re: Seeking recursive solution to replace nested for-loops
Date: 5 Mar 2004 11:47:14 -0800
Message-ID: <8244b794.0403051147.281957af_at_posting.google.com>
[Quoted] Cleaned up the code a little....
[Quoted] [Quoted] 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;
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 Fri Mar 05 2004 - 20:47:14 CET