Re: Project Programmer Wanter - PERMENUM v1.1 anyone?
- Posted by CChris <christian.cuvier at agric?l?ure.gouv.fr> Feb 28, 2008
- 644 views
Fernando Bauer wrote: > > 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 The final file size, if all goes well, is number_of_records*size_of_records., possibly *2 in mode b. In order to avoid overflow in poer(), I compute log(size) rather than size. The number of records is power(n,length(s)), whose log is log(length(s))*n. The record size is length(s), logarithms add up when miltiplying the numbers and log(length(s)) factors out. > 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). > > }}} <eucode> > 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 <snip>