OpenEuphoria

Re: Project Programmer Wanter

• Posted by CChris <christian.cuvier at agric?lture.gouv?fr> Feb 08, 2008
• 910 views

Ret Law wrote:
> 
> That sounds good.
> 
> Basically what I want is to create output, both as a data text file and as
> screen
> display of the full permutation of a given number of items over a given number
> of digits according to a given rule of sucession.
> 
> For example:
> 
> Items:
> A,B,C,D
> 
> # of Digits:
> 3
> 
> Order:
> A,B,C,D, beginning with AAA, ending with DDD and rotating in successive order
> across right to left.
> 
> Output:
> AAA
> AAB
> AAC
> AAD
> ABA
> ABB
> ABC
> ABD
> ACA
> ACB
> ACC
> ACD
> BAA
> BAB
> BAC
> BAD
> BBA
> BBB
> BBC
> BBD
> BCA
> BCB
> BCC
> BCD
> BDA
> BDB
> BDC
> BDD
> CAA
> CAB
> CAC
> CAD
> CBA
> CBB
> CBC
> CBD
> CCA
> CCB
> CCC
> CCD
> CDA
> CDB
> CDC
> CDD
> DAA
> DAB
> DAC
> DAD
> DBA
> DBB
> DBC
> DBD
> DCA
> DCB
> DCC
> DCD
> DDA
> DDB
> DDC
> DDD
> 
> How would that function be implemented to achieve that?

Oh, this is no permutation, but enumeration....

function update_counter(
    sequence counter,  -- counter sequence to increment
    integer start_val, -- usually 1
    integer end_val,   -- usually len
    integer len)       -- counter assumed length
-- increments len counters right to left, returns {} if done or
-- new counter & rank of first value changed.
  if not length(counter) then
    -- main function will make this call at startup
    -- create initial value of counter
    return repeat(start_val,len) & len
  elsif length(counter)!=len+1 then
    return 0 -- shouldn't happen
  end if
-- assert: start_val <= end_val
  for i=len to 1 by -1 do -- all counters have same length, len+1
    if counter[i] < end_val then
      counter[i]+=1
      counter[$]=i -- rank of first value changed
      return counter 
    else
      counter[i] = start_val
    end if
  end for
  return {} -- the end, or len<=0
end function

include misc.e
global procedure enumerate(
    sequence succession, -- list of objects to appear in order
    integer len,         -- number of digits
    sequence outfile)    -- output file name
  sequence counter,result,item
  integer ls,pos
  atom result_len
  
  lc=length(succession)
  result_len=power(ls,n)
  if not integer(result_len) then
    puts(2,"\n\nToo many items - output file not (re)written.\n\n")
    return
  end if
  result=repeat(0,result_len)
  counter=update_counter("",1,ls,n)
  item=repeat(0,n)
  pos=1
  while compare(counter,{})=1 do
    for i=counter[$] to n do
      item[i]=succession[counter[i]]
    end for
    result[pos]=item
    pos+=1
    counter=update_counter(counter,1,ls,n)
  end while
  if sequence(counter) then -- normal termination
    n=open(outfile,"w")
    if n>=0 then
      puts(n,sprint(result)&' ') 
      close(n)
    end if
  else
    puts(2,"\n\nInternal error - output file not (re)written.\n\n")
  end if
end procedure

According to the precise output format desired, and to whether the total number
of output items is above 1 billion, variants can be designed.
With this variant, you can retrieve the result in one sweep using 
get(output_file_once_open_for_read).
succession can contain any assortment of objects.
I didn't try to guard against any tampering with counters - there's always  a
tradeoff between defensiveness and performance. Counters are sequences all the
elements of which are atoms between start_val and end_val included.

HTH
CChris