August 2, 2011
(Back to the Previous Post in the Series) (Forward to the Next Post in the Series)
In the previous article in this series we tried to develop different methods for identifying special numbers between 1 and 1,000,000, such that the number formed by reversing the order of the digits will evenly divide into the original number. I initially predicted that there would be at least three unique solutions provided before the undocumented REVERSE function was mentioned. A fellow Oak Table member quickly provided a solution using the REVERSE function, which happens to be the fastest of the various approaches. Another reader noticed a pattern that helps find those special numbers – if that pattern identifies all of the special numbers, it is easily the most efficient approach to finding these special numbers.
Today’s blog article also is on the topic of finding special numbers, determined as special after changing the order of the number’s digits. I used my fancy, on-point introduction for this article in the earlier article (letters on the dice, trying to form words from those letters), so I thought that I would jump the little pony over the edge of the cliff in search of another introduction (there are probably five readers with an odd image stuck in their head at this moment). 😉
—
Have you ever noticed the disparity between the Environment Protection Agency’s (EPA or the equivalent in other countries) estimates for fuel efficiency and the actual fuel efficiency calculated with the hand held calculator? Take for instance a car that I own – that car has never achieved the EPA’s estimated fuel efficiency rating. A 412 horsepower (at the flywheel as claimed by the manufacturer, other tests have concluded that it might be higher) V8 achieving 25 miles per U.S. gallon (MPG) of fuel?
Time for the Oracle Database test case. On a frigid 32 degree day (in Celsius, that is a hot 90 degrees Fahrenheit), I lowered the windows, topped off the fuel tank with premium grade fuel, reset the car’s fuel efficiency gauge (the MPG gauge… oddly, this gauge always reads 6% to 8% lower than the actual fuel efficiency), and then set out on a roughly 117 mile (188 KM) drive down the highway with the radar detector on the dash board. While I have heard that the car’s speed limit is set at the factory to roughly 160 miles per hour (258 KM/H), the posted speed limit was typically 55 MPH (miles per hour) except in the roughly half-dozen or so cities along the way. The car never did hit the EPA’s estimated fuel efficiency rating. Somebody was playing with the numbers a bit, I think. 🙂
–
–
–
–
–
–
–
–
Along the route selected for the 117 mile test loop, I captured cell phone pictures showing the car’s fuel efficiency gauge (MPG gauge). Below are the cell phone pictures captured at 15 miles into the drive, roughly half way through the drive, and near the end of the 117 mile drive.
So, how does Oracle Database play a part in the introduction to this blog article? Let’s take a guess at the car’s actual fuel efficiency using a SQL statement:
SELECT 29.5 CAR, ROUND(29.5 * 1.06, 2) LOW_ACTUAL, ROUND(29.5 * 1.08, 2) HIGH_ACTUAL FROM DUAL; CAR LOW_ACTUAL HIGH_ACTUAL ---------- ---------- ----------- 29.5 31.27 31.86
So much for EPA estimates – between 25.08% and 27.44% lower than the actual fuel efficiency. Does this test case then suggest that if we do not use all of the features that are available in a tool, that we are then more efficient than expected? I think that I need another test case to decide. 😉
Side note: For the tank of fuel when the car rolled over the 1,000 mile mark, the car achieved 28.75 miles per gallon while touring some of the sites around Michigan, specifically the hills and curves along the north-west shoreline of the lower peninsula (several of those hills were steep – for one hill in particular the car downshifted three gears to maintain speed going down the hill). The car’s overall fuel efficiency since it left the factory is 25.58 MPG (excluding the 117 mile test case), so I guess that one could argue that if you TRUNC the fuel efficiency number, at the root the EPA is right. Make like a tree and leave (that was a movie quote from “Back to the Future”).
After returning from the test case I set out on my other 412 HP vehicle… cough, that would be a 4 cylinder 12 horsepower 1946 Farmall A tractor. Time to mow the lawn in second gear. Cutting a 6 foot (1.83 meter) wide path through grass that is up to 12 inches (30.48 cm) high, and capable of mowing down 2 inch diameter trees as necessary. Oh, the power of the horse…
—
—
—
OK, now that we have drifted far from the topic of this article and have had a chance to play with numbers in the long introduction, on to the challenge. Consider the four digit integer numbers between 1,000 and 9,999. There are 4! (1 * 2 * 3 * 4 = 24) possible combinations of the four digits of each of these numbers. For example, consider the number 8712 – the 24 possible combinations are:
1278 1287 1728 1782 1827 1872 2178 2187 2718 2781 2817 2871 7128 7182 7218 7281 7812 7821 8127 8172 8217 8271 8712 8721
The objective is to find all combinations of the four digit numbers between 1,000 and 9,999 that evenly divide into the original number. For the above example with the original number 8712, the combination 2178 evenly divides into 8712. Thus, the output would include:
ORIGINAL COMBINATION
-------- -----------
8712 2178
The restrictions:
- The four digit original numbers between 1,000 and 9,999 should not be included in the output if the last digit of those numbers is 0 – the combination number may end with 0 if the original number included a 0 digit. Thus, do not include the original numbers 1000, 1010, 1020, 1030, 1040, etc.
- The original value cannot be equal to the combination value (in the above example, it is not valid to output the combination value 8712).
- Each original number and combination pair should be output at most one time.
- You may not reuse a digit position twice; all digit positions must be used once. For example, the number 7141 includes the digit 1 twice, therefore, all generated combinations of that number must include two number 1 digits.
This challenge is a bit more difficult than was the challenge in part 1 of this series. The greatest difficulty likely involves creating the 23 valid digit combinations (there are 24, but one of those combinations will always be invalid) of the four digit numbers.
The problem is solvable – will your solution be the same as mine? I will give the readers a couple of days to ponder the thoughts of why a horse entered a race between a car and a tractor before sharing my approach to solving the problem.
Charles Hooper's Oracle Notes 
Here is my attempt … as mentioned in the code, Anagram credit goes to Laurent. Due to use of pl/sql, this is not a pure-sql solution but at-least an attempt.
-- anagram code taken from Laurent Schneider's Anagram solution posted at -- url http://forums.oracle.com/forums/thread.jspa?messageID=1791550 -- shamelessly reused with full credit to Laurent for that code. Hope he won't mind the reuse ... :) -- -- we treat numbers as char to generate anagrams (as possible combinations) -- raj (rjamya@gmail.com) -- please suggest anything i missed or improvements -- create or replace type table_of_varchar2 as table of varchar2(255); / create or replace package anagram is procedure p(x varchar2, y varchar2 default null); function f(x varchar2) return table_of_varchar2; end; / create or replace package body anagram is t table_of_varchar2; procedure p(x varchar2, y varchar2 default null) is begin if (length(x) = 1) then t.extend(1); t(t.last):=y||x; else for i in 1..length(x) loop p(substr(x,1,i-1)||substr(x,i+1),y||substr(x,i,1)); end loop; end if; end p; function f(x varchar2) return table_of_varchar2 is begin t := new table_of_varchar2(); p(x); return t; end f; end; / set timing on declare procedure p (p_msg in varchar2) is begin -- dbms_output.put_line(to_char(systimestamp,'hh24:mi:ss.ff6') || ': ' || p_msg); dbms_output.put_line(p_msg); end; -- begin p('Original Combination'); p('-------- -----------'); for f in (select r r0 from (select rownum r from dual connect by level = 1000 and mod(r,10) 0) loop for a in (select distinct column_value as c0 from table(anagram.f(f.r0))) loop if f.r0 a.c0 and f.r0 > a.c0 and mod(f.r0,a.c0) = 0 then -- p(f.r0 || ' : ' || a.c0 || ' : ' || (f.r0/a.c0)); p(lpad(f.r0,8,' ') || ' ' || lpad(a.c0,11,' ')); end if; end loop ; end loop; end; / commit / Output is ... Original Combination -------- ----------- 1001 0011 1005 0015 1008 0018 1053 0351 2002 0022 2016 0126 2025 0225 2079 0297 2106 0162 3003 0033 3024 0432 3042 0234 3045 0435 3105 0135 3105 1035 3402 0243 4004 0044 4005 0045 5005 0055 5049 0459 6006 0066 6031 0163 6045 0465 6048 0864 6072 0276 6075 0675 6084 0468 6105 0165 6804 0486 7007 0077 7011 0171 7128 1782 7425 2475 8008 0088 8019 0891 8092 0289 8316 1386 8712 2178 9009 0099 9016 0196 9021 0291 9108 0198 9207 0279 9207 0297 9405 0495 9504 0594 9513 1359 9801 0891 9801 1089I think i am missing at-last one more combinations (9009 and 0099), will check my code (it is w-i-p).
sorry about incovenience. here are the original 2 replies (unaltered):
1:
select * from ( select nr original, to_number(substr(ch,d1,1)||substr(ch,d2,1)||substr(ch,d3,1)||substr(ch,d4,1)) combination from (select d1,d2,d3,d4 from (select level d1 from dual connect by level<=4), (select level d2 from dual connect by level<=4), (select level d3 from dual connect by level<=4), (select level d4 from dual connect by level<=4) where d1!=d2 and d1!=d3 and d1!=d4 and d2!=d3 and d2!=d4 and d3!=d4 and (d1,d2,d3,d4) not in(select 1,2,3,4 from dual) ) comb, (select * from (select level nr, to_char(level) ch from dual connect by level<=9999) where nr>1000 and mod(nr,10)!=0) numbers where mod(nr, to_number(substr(ch,d1,1)||substr(ch,d2,1)||substr(ch,d3,1)||substr(ch,d4,1)))=0 and substr(ch,d1,1)!='0' ) where original!=combination2:
select * from ( select nr original, to_number(substr(ch,d1,1)||substr(ch,d2,1)||substr(ch,d3,1)||substr(ch,d4,1)) combination from (select substr(ch,2,1) d1,substr(ch,4,1) d2,substr(ch,6,1) d3,substr(ch,8,1) d4 from (select SYS_CONNECT_BY_PATH(5-l,' ') ch from (select level l from dual connect by level<=4) connect by nocycle prior l<5) where length(ch)=8 and ch!=' 1 2 3 4' ) digits, (select * from (select level nr, to_char(level) ch from dual connect by level<=9999) where nr>1000 and mod(nr,10)!=0) numbers where substr(ch,d1,1)!='0' ) where original!=combination and mod(original, combination)=0p.s. pls delete the older ones
There have been a couple of possible solutions posted so far, and there has been no more suggestions posted in the last 36 hours, so I thought that I would share the solution that I developed.
First, we need to find a way to build all 24 combinations of the 4 digits in the 4 digit numbers. For instance, we might arrange the 4 digits into the 24 combinations using a SQL statement like the following (the numbers represent the original positions of the digits):
WITH N AS (SELECT ROWNUM RN FROM DUAL CONNECT BY LEVEL<=4) SELECT N1.RN P1, N2.RN P2, N3.RN P3, N4.RN P4 FROM N N1, N N2, N N3, N N4 WHERE N1.RN<>N2.RN AND N1.RN<>N3.RN AND N1.RN<>N4.RN AND N2.RN<>N3.RN AND N2.RN<>N4.RN AND N3.RN<>N4.RN ORDER BY P1, P2, P3, P4; P1 P2 P3 P4 --- --- --- --- 1 2 3 4 1 2 4 3 1 3 2 4 1 3 4 2 1 4 2 3 1 4 3 2 2 1 3 4 2 1 4 3 2 3 1 4 2 3 4 1 2 4 1 3 2 4 3 1 3 1 2 4 3 1 4 2 3 2 1 4 3 2 4 1 3 4 1 2 3 4 2 1 4 1 2 3 4 1 3 2 4 2 1 3 4 2 3 1 4 3 1 2 4 3 2 1 24 rows selected.Now for the easy part, use the above matrix to simply pull out the digits in the specified order from the list of numbers between 1000 and 9999:
SELECT DISTINCT * FROM (SELECT N.RN, TO_NUMBER(SUBSTR(N.RNC,P.P1,1)||SUBSTR(N.RNC,P.P2,1)||SUBSTR(N.RNC,P.P3,1)||SUBSTR(N.RNC,P.P4,1)) RND FROM (SELECT ROWNUM+1000 RN, TO_CHAR(ROWNUM+1000) RNC FROM DUAL CONNECT BY LEVEL<=8999) N, (WITH N AS (SELECT ROWNUM RN FROM DUAL CONNECT BY LEVEL<=4) SELECT N1.RN P1, N2.RN P2, N3.RN P3, N4.RN P4 FROM N N1, N N2, N N3, N N4 WHERE N1.RN<>N2.RN AND N1.RN<>N3.RN AND N1.RN<>N4.RN AND N2.RN<>N3.RN AND N2.RN<>N4.RN AND N3.RN<>N4.RN) P WHERE RN/10<>TRUNC(RN/10)) WHERE RN<>RND AND RN/RND=TRUNC(RN/RND) ORDER BY RN, RND; RN RND ----- ----- 1001 11 1005 15 1008 18 1053 351 2002 22 2016 126 2025 225 2079 297 2106 162 3003 33 3024 432 3042 234 3045 435 3105 135 3105 1035 3402 243 4004 44 4005 45 5005 55 5049 459 6006 66 6031 163 6045 465 6048 864 6072 276 6075 675 6084 468 6105 165 6804 486 7007 77 7011 171 7128 1782 7425 2475 8008 88 8019 891 8092 289 8316 1386 8712 2178 9009 99 9016 196 9021 291 9108 198 9207 279 9207 297 9405 495 9504 594 9513 1359 9801 891 9801 1089 49 rows selected.Any other solutions?
what about a very short one? (disregard the timing 🙂 ) :
with nr as (select level+1000 n1,level n2 from dual connect by level<9000) select a.n1 original,b.n2 combination from nr a, nr b where mod(a.n1,b.n2)=0 and a.n1>b.n2 and mod(a.n1,10)>0 and cast(multiset(select substr(a.n1,level,1) from dual connect by level<5) as KU$_OBJNUMSET)= cast(multiset(select substr(lpad(b.n2,4,0),level,1) from dual connect by level<5) as KU$_OBJNUMSET)I didn’t succeed right now to have a pure SQL solution. I have however created a pipelined function giving me the four digit combinations as follows
mhouri.world >select * from table(f_get_number(8712)); COLUMN_VALUE ------------ 8712 8721 8172 8127 8271 8217 7812 7821 7182 7128 7281 7218 1872 1827 1782 1728 1287 1278 2871 2817 2781 2718 2187 2178 24 rows selected. mhouri.world >select * from table(f_get_number(7141)); COLUMN_VALUE ------------ 7141 7114 7411 7411 7114 7141 1741 1714 1471 1417 1174 1147 4711 4711 4171 4117 4171 4117 1714 1741 1174 1147 1471 1417 24 rows selected.and have started figuring out how to use this function with the original numbers selected as follows
mhouri.world > SELECT original 2 FROM 3 ( select rownum original 4 from dual connect by level <= 9999 5 ) 6 WHERE original >= 1000 7 AND SUBSTR(original,4,1) != 0 8 ; ORIGINAL ---------- 1001 1002 1003 1004 1005 1006 1007 1008 1009 1011 1012 1013 1014 1015 1016 1017 1018 1019 1021 1022 1023 1024 ....I Still have not found the solution
Mohamed,
Good idea to try a pipelined function. I have not worked with those very much.
As an experiment, I quickly put together an Excel macro/Visual Basic 6 program that accepts a number as input and outputs to the debug window all combinations of the digits in that number:
Private Function Combinations(lngNumber As Long) As Long Dim i As Integer Dim intFlag As Integer Dim intDigits As Integer Dim intDigit(20) As Integer Dim intDigitIndex(20) As Integer Dim intAdjustmentPosition As Integer intDigits = Len(CStr(lngNumber)) intAdjustmentPosition = intDigits For i = 1 To intDigits intDigitIndex(i) = i Next i Do While intAdjustmentPosition > 0 intFlag = 0 For i = 1 To intAdjustmentPosition - 1 If intDigitIndex(i) = intDigitIndex(intAdjustmentPosition) Then 'Found a duplicate index position in the other values to the left intFlag = 1 End If Next i If intFlag = 1 Then 'Try the next index position in this element intDigitIndex(intAdjustmentPosition) = intDigitIndex(intAdjustmentPosition) + 1 Else If intAdjustmentPosition = intDigits Then 'Output For i = 1 To intDigits Debug.Print intDigitIndex(i); Next i Debug.Print "" intDigitIndex(intAdjustmentPosition) = 1 intAdjustmentPosition = intAdjustmentPosition - 1 intDigitIndex(intAdjustmentPosition) = intDigitIndex(intAdjustmentPosition) + 1 Else 'No duplicate so prepare to check the next position intAdjustmentPosition = intAdjustmentPosition + 1 End If End If Do While (intAdjustmentPosition > 0) And (intDigitIndex(intAdjustmentPosition) > intDigits) 'Roll back one index position as many times as necessary intDigitIndex(intAdjustmentPosition) = 1 intAdjustmentPosition = intAdjustmentPosition - 1 intDigitIndex(intAdjustmentPosition) = intDigitIndex(intAdjustmentPosition) + 1 Loop Loop End FunctionNow let’s convert that VB 6 code into a function that will eventually return pipelined rows (is SYS.AQ$_MIDARRAY the correct type, I borrowed it from another example posted by someone to this blog – it appears that we *could* use this to return VARCHAR strings:
CREATE OR REPLACE FUNCTION COMBINATIONS(SNUMBER IN NUMBER) RETURN SYS.AQ$_MIDARRAY PIPELINED AS TYPE MY_ARRAY IS TABLE OF NUMBER INDEX BY PLS_INTEGER; intDigit MY_ARRAY; intDigitIndex MY_ARRAY; intDigits NUMBER; intAdjustmentPosition NUMBER; intFlag NUMBER; strOutput VARCHAR2(100); BEGIN intDigits := LENGTH(TO_CHAR(SNUMBER)); intAdjustmentPosition := intDIGITS; FOR I IN 1 .. intDigits LOOP intDigitIndex(I) := I; END LOOP; WHILE intAdjustmentPosition > 0 LOOP intFlag := 0; FOR I IN 1 .. intAdjustmentPosition - 1 LOOP IF intDigitIndex(I) = intDigitIndex(intAdjustmentPosition) Then -- Found a duplicate index position in the other values to the left intFlag := 1; END IF; END LOOP; IF intFlag = 1 Then -- Try the next index position in this element intDigitIndex(intAdjustmentPosition) := intDigitIndex(intAdjustmentPosition) + 1; ELSE IF intAdjustmentPosition = intDigits Then -- Output strOutput := ''; FOR i IN 1 .. intDigits LOOP strOutput := strOutput || SUBSTR(TO_CHAR(SNUMBER),intDigitIndex(i),1); END LOOP; DBMS_OUTPUT.PUT_LINE(strOutput); intDigitIndex(intAdjustmentPosition) := 1; intAdjustmentPosition := intAdjustmentPosition - 1; intDigitIndex(intAdjustmentPosition) := intDigitIndex(intAdjustmentPosition) + 1; ELSE -- No duplicate so prepare to check the next position intAdjustmentPosition := intAdjustmentPosition + 1; END IF; END IF; WHILE (intAdjustmentPosition > 0) And (intDigitIndex(intAdjustmentPosition) > intDigits) LOOP -- Roll back one index position as many times as necessary intDigitIndex(intAdjustmentPosition) := 1; intAdjustmentPosition := intAdjustmentPosition - 1; intDigitIndex(intAdjustmentPosition) := intDigitIndex(intAdjustmentPosition) + 1; END LOOP; END LOOP; END; /As can be seen by the above output, if we input the 4 digit number 1234, the function outputs all combinations of the digits 1234. It will work with numbers with 1, 2, 3, 4, 5, 6, 7, 8, 9, and etc. digits. Let’s fix the function so that it returns pipelined rows:
CREATE OR REPLACE FUNCTION COMBINATIONS(SNUMBER IN NUMBER) RETURN SYS.AQ$_MIDARRAY PIPELINED AS TYPE MY_ARRAY IS TABLE OF NUMBER INDEX BY PLS_INTEGER; intDigit MY_ARRAY; intDigitIndex MY_ARRAY; intDigits NUMBER; intAdjustmentPosition NUMBER; intFlag NUMBER; strOutput VARCHAR2(100); BEGIN intDigits := LENGTH(TO_CHAR(SNUMBER)); intAdjustmentPosition := intDIGITS; FOR I IN 1 .. intDigits LOOP intDigitIndex(I) := I; END LOOP; WHILE intAdjustmentPosition > 0 LOOP intFlag := 0; FOR I IN 1 .. intAdjustmentPosition - 1 LOOP IF intDigitIndex(I) = intDigitIndex(intAdjustmentPosition) Then -- Found a duplicate index position in the other values to the left intFlag := 1; END IF; END LOOP; IF intFlag = 1 Then -- Try the next index position in this element intDigitIndex(intAdjustmentPosition) := intDigitIndex(intAdjustmentPosition) + 1; ELSE IF intAdjustmentPosition = intDigits Then -- Output strOutput := ''; FOR i IN 1 .. intDigits LOOP strOutput := strOutput || SUBSTR(TO_CHAR(SNUMBER),intDigitIndex(i),1); END LOOP; PIPE ROW (strOutput); intDigitIndex(intAdjustmentPosition) := 1; intAdjustmentPosition := intAdjustmentPosition - 1; intDigitIndex(intAdjustmentPosition) := intDigitIndex(intAdjustmentPosition) + 1; ELSE -- No duplicate so prepare to check the next position intAdjustmentPosition := intAdjustmentPosition + 1; END IF; END IF; WHILE (intAdjustmentPosition > 0) And (intDigitIndex(intAdjustmentPosition) > intDigits) LOOP -- Roll back one index position as many times as necessary intDigitIndex(intAdjustmentPosition) := 1; intAdjustmentPosition := intAdjustmentPosition - 1; intDigitIndex(intAdjustmentPosition) := intDigitIndex(intAdjustmentPosition) + 1; END LOOP; END LOOP; END; /Now the interesting thing is that if we input 1234, we are able to use the first, second, third, and fourth characters in the returned values to determine how to reorganize the digits in the original numbers that are supplied by the CONNECT BY syntax:
SELECT DISTINCT N, D FROM (SELECT N.N, TO_NUMBER(SUBSTR(TO_CHAR(N.N), SUBSTR(P.COLUMN_VALUE,1,1),1) || SUBSTR(TO_CHAR(N.N), SUBSTR(P.COLUMN_VALUE,2,1),1) || SUBSTR(TO_CHAR(N.N), SUBSTR(P.COLUMN_VALUE,3,1),1) || SUBSTR(TO_CHAR(N.N), SUBSTR(P.COLUMN_VALUE,4,1),1)) D FROM (SELECT * FROM TABLE(COMBINATIONS(1234))) P, (SELECT ROWNUM+1000 N FROM DUAL CONNECT BY LEVEL<=8999) N WHERE N/10 <> TRUNC(N/10)) WHERE N>D AND N/D = TRUNC(N/D) ORDER BY N;I am not sure if the above helps – maybe someone can figure out how to directly feed the numbers from the N inline view into the COMBINATIONS function.