1 2 Previous Next 29 Replies Latest reply on Jan 24, 2013 7:33 PM by AdamMartin Go to original post
• ###### 15. Re: Need the best way to solve this problem
It is like picking up available digits from the string and drop into numbered boxes......

Here are two given conditions (correct me if wrong),

1. a collection of digits in the string from 0 to 9, which can be built into a look up table as count(0), ..., count(9)

2. pick up any available digit(s) from the look up and drop into the current number box, if possible, but ONLY if all left digits can be put into a valid number larger than current number.

Now time for break before starting loop... :)
• ###### 16. Re: Need the best way to solve this problem
Nicely done!

There might still be an issue with some inputs, for example:

76721==>1,2,6,7 | 7

76721==>1,2,6,77

Also, currently it returns: 11==>1,10 when it should be 11==>11
• ###### 17. Re: Need the best way to solve this problem
Nicely done!

There might still be an issue with some inputs, for example:

76721==>1,2,6,7 | 7

76721==>1,2,6,77

Also, currently it returns: 11==>1,10 when it should be 11==>11
Yes, the 'requirement' is flawed, because it would have to traverse all recursive tree options until it finds all possibilities that use up all the digits, and then out of the potentially multiple solution paths, it would have to pick the 'best' of those, based on some criteria (which would need specifying).

I'm a bit late coming to this thread myself (was off-forum for a few days).
Anyway, allowing for the aforementioned issue, I've had a go myself using recursive subquery factoring in 11gR2...
``````SQL> ed
Wrote file afiedt.buf

1  with t as (select '1124567801030904' as str from dual)
2  --
3      ,r(last, val, instr, outstr) as
4            (/* Anchor Query */
5             select 0 as last
6                   ,0 as val
7                   ,str as instr
8                   ,cast('' as varchar2(100)) as outstr
9             from t
10             union all
11             /* Recursive Query */
12             select case when instr = to_char(val+1,'fm99')
13                           or val > to_number(regexp_replace(instr, to_char(val+1,'fm9999999'),'',1,1))
14                         then 1
15                    else 0
16                    end as last
17                   ,val+1 as val
18                   ,regexp_replace(instr, to_char(val+1,'fm9999999'),'',1,1) as instr
19                   ,trim(',' from outstr||case when instr(instr,to_char(val+1,'fm9999999'))>0
20                                               then ','||to_char(val+1,'fm9999999')
21                                          else null
22                                          end) as outstr
23             from   r
24             where  regexp_replace(instr, to_char(val+1,'fm9999999'),'',1,1) is not null
25             and    val <= to_number(instr)
26            )
27  select t.str as orig_string
28        ,r.outstr as result_string
29        ,r.instr as remainder_string
30        ,r.val as iterations
31  from t, r
32* where last = 1
SQL> /

ORIG_STRING                    RESULT_STRING                  REMAINDER_STRING     ITERATIONS
------------------------------ ------------------------------ -------------------- ----------
1124567801030904               1,2,3,4,5,6,7,8,9,10,100       04                          100``````
The "remainder" string is what's left because after picking out the occurences of values from the string in a 'left to right' order of ascending values, we're left with "04" which can't possibly be found in any further iterations.

As already mentioned above, a 'better' result can be got if the digits are ordered from high to low first....
``````SQL> ed
Wrote file afiedt.buf

1  with t_orig as (select '1124567801030904' as str from dual)
2      ,t as (select listagg(digit) within group (order by rn) as str
3             from (
4                   select digit, row_number() over (order by digit desc) as rn
5                    from (
6                          select substr(str,level,1) as digit
7                          from   t_orig
8                          connect by level <= length(str)
9                         )
10                  )
11             )
12  --
13      ,r(last, val, instr, outstr) as
14            (/* Anchor Query */
15             select 0 as last
16                   ,0 as val
17                   ,str as instr
18                   ,cast('' as varchar2(100)) as outstr
19             from t
20             union all
21             /* Recursive Query */
22             select case when instr = to_char(val+1,'fm99')
23                           or val > to_number(regexp_replace(instr, to_char(val+1,'fm9999999'),'',1,1))
24                         then 1
25                    else 0
26                    end as last
27                   ,val+1 as val
28                   ,regexp_replace(instr, to_char(val+1,'fm9999999'),'',1,1) as instr
29                   ,trim(',' from outstr||case when instr(instr,to_char(val+1,'fm9999999'))>0
30                                               then ','||to_char(val+1,'fm9999999')
31                                          else null
32                                          end) as outstr
33             from   r
34             where  regexp_replace(instr, to_char(val+1,'fm9999999'),'',1,1) is not null
35             and    val <= to_number(instr)
36            )
37  select t.str as orig_string
38        ,r.outstr as result_string
39        ,r.instr as remainder_string
40        ,r.val as iterations
41  from t_orig t, r
42* where last = 1
SQL> /

ORIG_STRING                    RESULT_STRING                  REMAINDER_STRING     ITERATIONS
------------------------------ ------------------------------ -------------------- ----------
1124567801030904               1,2,3,4,5,6,7,8,9,10,41        000                          41``````
In this case we still end up with a remainder string of "000", but now it's only taking 41 iterations to use up most of the digits.
However, the problem with this is that, by moving the digits into an order, we can prevent certain values from appearing e.g. in the following input string...
``````SQL> ed
Wrote file afiedt.buf

1  with t_orig as (select '11234567801030904' as str from dual)
2      ,t as (select listagg(digit) within group (order by rn) as str
3             from (
4                   select digit, row_number() over (order by digit desc) as rn
5                    from (
6                          select substr(str,level,1) as digit
7                          from   t_orig
8                          connect by level <= length(str)
9                         )
10                  )
11             )
12  --
13      ,r(last, val, instr, outstr) as
14            (/* Anchor Query */
15             select 0 as last
16                   ,0 as val
17                   ,str as instr
18                   ,cast('' as varchar2(100)) as outstr
19             from t
20             union all
21             /* Recursive Query */
22             select case when instr = to_char(val+1,'fm99')
23                           or val > to_number(regexp_replace(instr, to_char(val+1,'fm9999999'),'',1,1))
24                         then 1
25                    else 0
26                    end as last
27                   ,val+1 as val
28                   ,regexp_replace(instr, to_char(val+1,'fm9999999'),'',1,1) as instr
29                   ,trim(',' from outstr||case when instr(instr,to_char(val+1,'fm9999999'))>0
30                                               then ','||to_char(val+1,'fm9999999')
31                                          else null
32                                          end) as outstr
33             from   r
34             where  regexp_replace(instr, to_char(val+1,'fm9999999'),'',1,1) is not null
35             and    val <= to_number(instr)
36            )
37  select t.str as orig_string
38        ,r.outstr as result_string
39        ,r.instr as remainder_string
40        ,r.val as iterations
41  from t_orig t, r
42* where last = 1
SQL> /

ORIG_STRING                    RESULT_STRING                  REMAINDER_STRING     ITERATIONS
------------------------------ ------------------------------ -------------------- ----------
11234567801030904              1,2,3,4,5,6,7,8,9,10,31,40     00                           40``````
(I've added the first 3 to the string)
... the original string had a "30" in it, but this wasn't picked up because the 0's have been moved.

No solution is really ideal, as nothing can cater for all possibilities, without a true recursive solution that examines all possibilities.
• ###### 18. Re: Need the best way to solve this problem
It does not need to try "all possibilities" as you suggest. It simply needs to fill in the smallest integers in order and check to see if there is a remainder at the end (a remainder from which a greater integer cannot be formed). If there is a remainder, then the prior integer is invalid, and it must go upwards from there.

For your input of '11234567801030904' the correct solution is 1,2,3,4,5,6,7,8,9,10,13,4000

Although the integer 40 would have been next in line after 13, the number 40 must be ruled invalid because it would leave remaining digits that cannot form a greater integer.
• ###### 19. Re: Need the best way to solve this problem
My version is posted below. It seems to work for all inputs tested.
``````declare
v_input varchar2(50) := '11234567801030904'; -- <-----INPUT HERE
v_sorted_input varchar2(50);
v_output varchar2(100);
v_digit_check varchar2(50);
v_comma varchar2(1);
--character sort function
function sort_chars(p_chars varchar2) return varchar2 is
v_chars varchar2(50) := p_chars;
v_retval varchar2(50);
v_keep_searching boolean := true;
v_cnt number := 0;
begin
for i in reverse 0..9 loop
v_keep_searching := true;
while v_keep_searching loop
if instr(v_chars,to_char(i)) > 0 then
v_retval := v_retval || to_char(i);
v_chars := regexp_replace(v_chars,to_char(i),'',1,1);
else
v_keep_searching := false;
end if;
end loop;
end loop;
return v_retval;
end;
--digit checking function
function all_digits_exist(p_int varchar2, p_input_string varchar2) return varchar2 is
v_instr number;
v_input_string varchar2(50) := p_input_string;
begin
for a in 1..length(p_int) loop
v_instr := instr(v_input_string, substr(p_int,a,1));
if v_instr > 0 then
v_input_string := regexp_replace(v_input_string,substr(p_int,a,1),'',1,1);
else
end if;
end loop;
return v_input_string;
end;
begin
dbms_output.put_line('Input= ' || v_input);
if nvl(to_number(v_input),0) < 1 then
dbms_output.put_line('Input must be greater than or equal to 1.');
return;
end if;
--sort digits in descending order
v_sorted_input := sort_chars(v_input);
--loop through integers (with upper limits)
for i in 1..least(to_number(v_sorted_input),1000000) loop
--check if i works as next smallest integer
v_digit_check := all_digits_exist(i,v_sorted_input);
continue; --go to the next integer
else
--integer found, but must check for remainders
if nvl(length(v_digit_check),0) > 0 then
if to_number(v_digit_check) > to_number(i) then --a greater integer can be found
v_output := v_output || v_comma || to_char(i);
v_comma := ',';
for j in 1..length(to_char(i)) loop
v_sorted_input := regexp_replace(v_sorted_input,substr(to_char(i),j,1),'',1,1);
end loop;
else
continue; --no greater integer found so continue with next highest
end if;
else
v_output := v_output || v_comma || to_char(i);
exit; --done when no more digits exist
end if;
end if;
end loop;
dbms_output.put_line('Output= '||v_output);
end;
/

Result:
-------------------
Input= 11234567801030904
Output= 1,2,3,4,5,6,7,8,9,10,13,4000``````
And it works for the inputs that Steve's code does not handle:
``````Input= 11
Output= 11

Input= 76721
Output= 1,2,6,77``````
• ###### 20. Re: Need the best way to solve this problem
Updated to handle larger input strings (and inputs with lots of zeroes):
``````declare
v_input varchar2(150) := '456564231164684864864651153350000064006006456486894897897894560006456066468908000898977890660601061568044064066510308648084898900000064545456333217770';
v_sorted_input varchar2(150);
v_output varchar2(1100);
v_digit_check varchar2(150);
v_comma varchar2(1);
--character sort function
function sort_chars(p_chars varchar2) return varchar2 is
v_chars varchar2(150) := p_chars;
v_retval varchar2(150);
v_keep_searching boolean := true;
v_cnt number := 0;
begin
for i in reverse 0..9 loop
v_keep_searching := true;
while v_keep_searching loop
if instr(v_chars,to_char(i)) > 0 then
v_retval := v_retval || to_char(i);
v_chars := regexp_replace(v_chars,to_char(i),'',1,1);
else
v_keep_searching := false;
end if;
end loop;
end loop;
dbms_output.put_line('Sorted='||v_retval);
return v_retval;
end;
--digit checking function
function all_digits_exist(p_int varchar2, p_input_string varchar2) return varchar2 is
v_instr number;
v_input_string varchar2(150) := p_input_string;
begin
for a in 1..length(p_int) loop
v_instr := instr(v_input_string, substr(p_int,a,1));
if v_instr > 0 then
v_input_string := regexp_replace(v_input_string,substr(p_int,a,1),'',1,1);
else
end if;
end loop;
return v_input_string;
end;
begin
dbms_output.put_line('Input= ' || v_input);
if nvl(to_number(v_input),0) < 1 then
dbms_output.put_line('Input must be greater than or equal to 1.');
return;
end if;
--sort digits in descending order
v_sorted_input := sort_chars(v_input);
--loop through integers (with upper limits)
for i in 1..least(to_number(v_sorted_input),100000) loop
--check if i works as next smallest integer
v_digit_check := all_digits_exist(i,v_sorted_input);
continue; --go to the next integer
else
--integer found, but must check for remainders
if nvl(length(v_digit_check),0) > 0 then
if to_number(v_digit_check) > to_number(i) then --a greater integer can be found
v_output := v_output || v_comma || to_char(i);
v_comma := ',';
for j in 1..length(to_char(i)) loop
v_sorted_input := regexp_replace(v_sorted_input,substr(to_char(i),j,1),'',1,1);
end loop;
else
continue; --no greater integer found so continue with next highest
end if;
else
v_output := v_output || v_comma || to_char(i);
for j in 1..length(to_char(i)) loop
v_sorted_input := regexp_replace(v_sorted_input,substr(to_char(i),j,1),'',1,1);
end loop;
exit; --done when no more digits exist
end if;
end if;
end loop;
if v_sorted_input is not null then
v_output := v_output || v_comma || v_sorted_input; --to handle inputs with lots of zeroes
end if;
dbms_output.put_line('Output='||v_output);
end;
/

Result:
-------------------------
Input= 456564231164684864864651153350000064006006456486894897897894560006456066468908000898977890660601061568044064066510308648084898900000064545456333217770
Sorted=999999999988888888888888888887777777666666666666666666666666666665555555555555444444444444444444444333333322111111110000000000000000000000000000000000
Output=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,30,33,34,35,40,44,45,46,47,48,49,50,54,55,56,57,58,59,60,64,65,66,67,68,69,70,74,76,80,84,86,88,89,90,94,96,98,400,404,406,408,600,606,608,609,660,666,668,680,688,800,8000000000000  ``````
• ###### 21. Re: Need the best way to solve this problem
Just one word.... WOW!
BluShadow, open up an oracle teaching institute, and I will be your first disciple :)

I know the requirement is fuzzy, incomplete, may be impossible, just because its an insane thought of mine put into forum ;) but still you guys put forward some solutions which is just awesome..
Thanks to all the participants... Really appreciated!!!!

Cheers,
Manik.
• ###### 22. Re: Need the best way to solve this problem
This "fuzzy" problem solved, somehow, reminds me of [url http://littlebobeep.com/wp-content/uploads/2010/05/Calvinball1.gif]CalvinBall
"The score is still Q to 12!"
:-)

[url http://calvinandhobbes.wikia.com/wiki/Calvinball](an attempt to describe calvinball)
• ###### 23. Re: Need the best way to solve this problem
Manik wrote:
Just one word.... WOW!
Thanks! It was a lot of fun.
• ###### 24. Re: Need the best way to solve this problem
Tried something similar but got stuck on repeating numbers. I'm afraid yours seems to suffer similarly, e.g.

Input= 22222222222222222222
Sorted=22222222222222222222
Output=2,22,222,2222,2222222222
• ###### 25. Re: Need the best way to solve this problem
Tried something similar but got stuck on repeating numbers. I'm afraid yours seems to suffer similarly, e.g.

Input= 22222222222222222222
Sorted=22222222222222222222
Output=2,22,222,2222,2222222222
That is the correct output. Where is the problem?

If you are suggesting that it is missing the integer 22222, then that would leave a remainder of exactly 22222, and remainders are not allowed. Therefore, 22222 is not a valid integer and it must be skipped. Likewise, 6 twos must be skipped, and 7 twos, and so on. The correct solution is shown in your post, which uses all the digits provided, leaving no remainder, and showing the lowest possible integers.

Also, note that the following line has a looping limit which can be raised (but performance would suffer if looping into the hundreds of millions):

for i in 1..least(to_number(v_sorted_input),100000) loop <----------------- limit of 100000 but it can be set higher

But if you want to see 22222, then add one more '2' to the input:

Input= 222222222222222222222
Sorted=222222222222222222222
Output=2,22,222,2222,22222,222222
• ###### 26. Re: Need the best way to solve this problem
Sorry posted wrong example, but issue is there - and you are right it is caused by looping limit.

Another example.

Input= 2222222222222222222222222222222222
Sorted=2222222222222222222222222222222222
Output=2,22,222,2222,22222,2222222222222222222

Should be?=2,22,222,2222,22222,222222,2222222222222

I'm wondering if generating number sequence based on only the numbers in the input would solve this. Not sure whether this is a likely input - I suppose you could just raise an error if the search expires.
• ###### 27. Re: Need the best way to solve this problem
Yes, that's a victim of the looping limit. You're right that it is an unlikely input. For inputs like these it seems like there is a more intelligent way of solving it than looping through all integers. I am thinking that it would be much more efficient to rearrange the digits into the possible integers that can be formed from the input. But the looping works very well for most other scenarios. My 150 digit input (above) completed in less than a second. But I am tempted now to see if I can do it again without the upward-counting integer loop. Seems like a great idea.
• ###### 28. Re: Need the best way to solve this problem
Just for fun.... (cos I felt like it and had a few minutes spare)

Here's a version that uses a recursive function to achieve the result...
``````SQL> create or replace function sequence_values(p_instr in varchar2, v_limit in number := 100000) return varchar2 is
3    function check_digits(p_instr in varchar2, p_val in number) return varchar2 is
4      /* Checks if the digits of the current value are available in the remaining string */
6      v_str varchar2(200) := p_instr;
7    begin
8      for i in 1..length(v_val)
9      loop
10        if instr(v_str,substr(v_val,i,1)) > 0 then
11          v_str := regexp_replace(v_str,substr(v_val,i,1),'',1,1);
12        else
13          v_str := p_instr;
14          exit;
15        end if;
16      end loop;
17      return v_str;
18    end;
19    function max_val(p_instr in varchar2) return number is
20      /* Determines the maximum possible value left in the remaining string */
21      v_sorted varchar2(200) := '';
22    begin
23      for i in reverse 0..9
24      loop
25        v_sorted := v_sorted||regexp_replace(p_instr,'[^'||to_char(i)||']');
26      end loop;
28    end;
29    function is_valid(p_instr in varchar2, p_val in number) return varchar2 is
30      /* Recurses the string to build up the result */
31      v_chk varchar2(200);
32    begin
33      if p_val > v_limit then
34        /* Allow a limit to prevent stupidity */
35        return ' - Recursive Depth Limit Reached.';
36      end if;
37      /* Extract the current value from the string if possible */
38      v_chk := check_digits(p_instr, p_val);
39      if v_chk is null then
40        /* No remaining string, so we have reached a solution */
41        /* Pass back the current value */
43      elsif v_chk = p_instr or max_val(v_chk) <= p_val then
44        /* The current value wasn't found in the remaining string     */
45        /* Or the remaining string after finding it will be too small */
46        /* So just search on for the next possible matching value     */
47        return is_valid(p_instr, p_val+1);
48      else
49        /* We found a value but we have more to do                    */
50        /* Pass back the current value and the result of recursing    */
51        /* the remainder of the string                                */
53      end if;
54    end;
55  begin
56    return is_valid(p_instr, 1);
57  end;
58  /

Function created.

SQL>
SQL> select sequence_values('1124567801030904') from dual;

SEQUENCE_VALUES('1124567801030904')
------------------------------------------------------------------------------------------------------------------------
1,2,3,4,5,6,7,8,9,10,40,100

SQL>
SQL> select sequence_values('11234567801030904') from dual;

SEQUENCE_VALUES('11234567801030904')
------------------------------------------------------------------------------------------------------------------------
1,2,3,4,5,6,7,8,9,10,13,4000

SQL>
SQL> select sequence_values('11275324765324234567801030904') from dual;

SEQUENCE_VALUES('11275324765324234567801030904')
------------------------------------------------------------------------------------------------------------------------
1,2,3,4,5,6,7,8,9,10,12,20,23,30,34,40,45,56,77

SQL>
SQL> select sequence_values('222222222222222222222',1000000) from dual;

SEQUENCE_VALUES('222222222222222222222',1000000)
------------------------------------------------------------------------------------------------------------------------
2,22,222,2222,22222,222222``````
I've put a recursive depth limit on there (which can be overridden as required) to help prevent accidental hang-ups from really bad inputs.
Hopefully I've included enough comments to make it easy to follow.

Enjoy. :)