Re: Project Programmer Wanter - PERMENUM v1.1 anyone?
- Posted by Fernando Bauer <fmbauer at ?otma?l.com> Feb 28, 2008
- 583 views
CChris wrote: > > The following merges the final file size test with Fernando's code. > On my WinXP pro machine, the drive size is not available (function not > supported). > I incluede a workaround. > If you are running under actual DOS, this may work for you. Otherwise, oyou > have to execute an .exw file using exwc.exe, and replace my code by Windows > API code that fetches available space on drive. Are you stuck with DOS, > really? > [snipped Eu code] Firstly, thanks CChris for your implementation and comments! Secondly, I want to note that I made a mistake in the specification of the limit of the number of variations (permutations). Actually, the limit of index v in function VariationRep is 2^53 (maximum contiguous integer in an atom). There are many powers that are between 2^52 and 2^53 (ex.: 3^33, 21^12, 27^11, 28^11, 37^10, ...). However, in the program, because the argument "a-i" in call to VariationRep, the actual limit would be (2^53)-1, but with the original test "if a+1=a" the final limit is (2^53)-2. Actually, these limits will not be reached because the current storage capacity, so they aren't used in CChris' code. Following is a version based on CChris' code: - I guess that a version of Ret's items a to e is implemented. - A small optimization was made in saving the variations to the file. - I didn't understand CChris' expression "log(length(s))*(n+1)", so I substituted it for another one. - I don't know if CTR-C test (check_break()) works appropriately in DOS. It seems that in WinXP it doesn't (I can't stop after the beginning of the generating process).
include get.e include wildcard.e include graphics.e include misc.e include machine.e include file.e atom mb_drive_space,buffer_lo -- # Mo available on drive, DOS buffer atom file_size_log constant one_meg=1048576 procedure terminate(integer i) puts(1,"\nPlease press any key to terminate the program.\n") if wait_key() then end if abort(i) end procedure function VariationRep(atom v, integer n, sequence s) integer ls sequence p if v < 1 then return {} end if v -= 1 p = repeat(0,n) ls = length(s) for i = n to 1 by -1 do p[i] = s[remainder(v,ls)+1] v = floor(v/ls) end for return p end function integer n,fn atom a,t sequence s,mode,fname,pos function OpenFile(sequence fname, sequence mode) sequence in integer fn if mode[1]='w' then fn = open(fname,"r") if fn >= 0 then puts(1,"That file already exists.\n") while 1 do in = lower(prompt_string("Overwrite and replace the file [y/n]:")) if check_break() then terminate(1) end if if equal(in,"n") then return -1 end if if equal(in,"y") then exit end if puts(1,"Please enter either y or n.\n") end while puts(1,'\n') close(fn) end if end if fn = open(fname,mode) if fn < 0 then printf(1,"Could not open output file: %s\n",{fname}) puts(1,"Maybe that data storage device does not exist or your entry was not written in a proper file name format.\n") end if return fn end function function find_drive_space() -- get drive for output file sequence regs atom buffer_hi,truename_ptr,bytes_per_cluster,num_clusters,result integer seg16,off16_lo,off16_hi,second_char,num_bksp regs=repeat(0,10) buffer_lo=allocate_low(256) buffer_hi=buffer_lo+128 seg16=floor((buffer_lo+256)/#FFFF) -- avoid segment wrap inside buffer off16_lo=buffer_lo-65536*seg16 off16_hi=off16_lo+128 poke(buffer_lo,fname) poke(buffer_lo+length(fname),0) regs[REG_DS]=seg16 -- src buffer address regs[REG_SI]=off16_lo regs[REG_ES]=seg16 -- dst buffer address regs[REG_DI]=off16_hi regs[REG_AX]=#6000 -- request true name regs=dos_interrupt(#21,regs) if and_bits(regs[REG_FLAGS],1) then return -1 end if -- extract drive name second_char=peek(buffer_hi+1) if second_char=':' then -- local drive poke(buffer_hi+3,0) elsif second_char!='\\' then -- unlikely return 0 else -- UNC for network drive -- some versions need extra support truename_ptr=buffer_hi+3 num_bksp=0 while 1 do second_char=peek(truename_ptr) if second_char=0 then exit -- unlikely elsif second_char='\\' then if num_bksp then -- end of second component reached poke(truename_ptr+1,0) exit else -- end of machine name reached, now scan the drive name num_bksp=1 end if end if end while end if -- get cluster size for drive regs[REG_CX]=44 -- <128 so we can reuse original fname buffer regs[REG_DX]=off16_hi regs[REG_DI]=off16_lo regs[REG_AX]=#7303 regs=dos_interrupt(#21,regs) if and_bits(regs[REG_FLAGS],1) or not and_bits(regs[REG_AX],#FF) then return 0 -- error, or unsupported call end if bytes_per_cluster=peek4u(buffer_lo+4)*peek4u(buffer_lo+8) result=floor(bytes_per_cluster/one_meg) bytes_per_cluster=remainder(bytes_per_cluster,one_meg) -- get available cluster count for drive -- In rare cases, this may not be reliable, but reliable -- answers are only guaranteed for local drives using the alternate mechanism. num_clusters=peek4u(buffer_lo+12) mb_drive_space *= num_clusters num_clusters *= bytes_per_cluster return result+floor(num_clusters/one_meg) end function fn = 1 allow_break(0) puts(1,"PERMENUM - Permutation Enumeration Generator v1.0\n\n") puts(1,"Generating \"forward\" or \"forward and reverse paired\", right ordered enumeration\n" & "of every permutation of any number of positions and any length of items.\n\n" & "Program may be halted at any given moment by pressing the CTR-C and then ENTER key.\n") while 1 do mode = lower(prompt_string("\nEnter whether to generate either a) \"forward\" or b) \"forward and reverse pairs\"\n" & "of right ordered enumeration of every permutation [e.g.: a]:\n")) if check_break() then terminate(1) end if if not equal(mode,"a") and not equal(mode,"b") then while 1 do mode = lower(prompt_string("Please enter either a or b:\n")) if check_break() then terminate(1) end if if equal(mode,"a") or equal(mode,"b") then exit end if end while end if n = prompt_number("\nEnter the number of character places for the permutation [e.g.: 4]:\n",{}) if check_break() then terminate(1) end if s = prompt_string("\nEnter the character items to be permutated in the desired forward order for\n" & "the enumeration [e.g.: xyz]:\n") if check_break() then terminate(1) end if while 1 do fname = prompt_string("\nEnter the file name for the enumeration output to be saved as [e.g.: 4toxyz.txt\n" & "or c:\\4toxyz.txt]:\n") if check_break() then terminate(1) end if fn = OpenFile(fname,"w") if fn != -1 then exit end if end while -- start size testing mb_drive_space=find_drive_space() free_low(buffer_lo) -- a = power(length(s),n) + 1 -- if a+1 = a then -- puts(1,"Too many permutations to process. The limit for the total number of forward and reverse paired," & -- "right ordered permutations to be enumerated is 2^52 [n=2, s=52].\n") -- abort(1) -- end if if mb_drive_space=0 then mb_drive_space=prompt_number("\nDo you know how megabytes of free space you have on that drive? If so, please enter that number, else 0.\n",{}) if mb_drive_space=0 then if compare(prompt_string("\nCould no determine available space on drive.\nDo you wish to proceed, AT THE RISK OF OVERRUNNING YOUR DRIVE? (NOT RECOMMENDED)\nIf so, type YES, any other answer exits program.\n") ,"YES") then puts(1,"\nProgram halted by user.\n") terminate(1) end if end if end if -- changed check using logarithms, so as to avoid overflows in power() -- file_size_log=log(length(s))*(n+1) -- if equal(mode,"b") then -- file_size_log+=log(2) -- end if if equal(mode,"a") then -- for mode (a) file_size = power(length(s),n) * (n+2) file_size_log = log(length(s))* n + log(n+2) else -- for mode (b) file_size = power(length(s),n) * (2*n + 3) file_size_log = log(length(s))* n + log(2*n+3) end if if log(one_meg)+log(mb_drive_space) > file_size_log then exit end if-- lhs is expected to be below 53*log(2)~36.736 puts(1,sprintf("Too many permutations to process, given the available space (%dMb) on selected drive.\n\n",mb_drive_space)) end while a = power(length(s),n) + 1 t = floor((a-1)/100) if t=0 then t=1 end if pos = get_position() if equal(mode,"a") then for i = 1 to a-1 do if remainder(i,t) = 0 then position(pos[1],1) printf(1,"%d%% done.",100*i/(a-1)) if check_break() then terminate(1) end if end if puts(fn,VariationRep(i,n,s)& '\n') end for else for i = 1 to a-1 do if remainder(i,t) = 0 then position(pos[1],1) printf(1,"%d %% done.",100*i/(a-1)) if check_break() then terminate(1) end if end if puts(fn,VariationRep(i,n,s)& ' ') puts(fn,VariationRep(a-i,n,s)& '\n') end for end if position(pos[1],1) puts(1,"100% done.\n") terminate(0)
Regards, Fernando