1. Project Programmer Wanter
I am seeking a voluntary Euphoria programmer/s wishing to complete a project for
general license (public Euphoria Library) involving permutation processing.
Please respond ASAP.
2. Re: Project Programmer Wanter
Ret Law wrote:
> I am seeking a voluntary Euphoria programmer/s wishing to complete a project
> for general license (public Euphoria Library) involving permutation
> processing.
>
> Please respond ASAP.
Sorry, I don't want to volunteer, but I can contribute a cool function:
global function next_permutation (sequence s)
-- Return the next permutation of s (in lexicographic order);
-- the function also works, if not all elements in s are distinguishable
-- (meaning s is a multiset). For example, there are only
-- 10 permutations of {1,1,2,2,2}, instead of 120.
-- ** In order to get all possible permutations, initially sort s in
-- ascending order. **
-- [after
-- Donald E. Knuth: TAOCP, Vol. 4, Fascicle 2 (2005), pp. 39 f.,
-- "Algorithm 7.2.1.2 L"]
-- Demo
-- ----
-- object x
-- x = {"green", "blue", "red"}
-- x = sort(x)
-- while sequence(x) do
-- ...
-- x = next_permutation(x)
-- end while
object t
integer n, i, j
n = length(s)
-- Step 1: Find the largest i such that s[i] can be increased.
i = n - 1
while i > 0 and compare(s[i],s[i+1]) != -1 do
i -= 1
end while
if i = 0 then
return -1 -- end
end if
-- Step 2: Increase s[i] by the smallest feasible amount.
j = n
while compare(s[j],s[i]) != 1 do
j -= 1
end while
t=s[i] s[i]=s[j] s[j]=t -- swap s[i], s[j]
-- Step 3: Reverse s[i+1..n] (Find the lexicographically least
-- way to extend the new s[1..i] to a complete pattern.)
i += 1
j = n
while i < j do
t=s[i] s[i]=s[j] s[j]=t -- swap s[i], s[j]
i += 1
j -= 1
end while
return s
end function
Maybe this is useful for your project.
Regards,
Juergen
--
http://luethje.eu/prog/
3. Re: Project Programmer Wanter
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?
4. Re: Project Programmer Wanter
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
5. Re: Project Programmer Wanter
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
<snip>
> DCD
> DDA
> DDB
> DDC
> DDD
>
> How would that function be implemented to achieve that?
Well, creating different permutations just means re-ordering of the items.
In order to achieve what you want here, we have to build variations with
repetition. The following code does do so:
global function next_variation_r (sequence s, integer mini, integer maxi)
-- return the next variation with repetition on s
-- (in lexicographic order);
-- ** In order to get all possible variations, s must initially only
-- contain 'mini' values. **
s[$] += 1
for i = length(s) to 2 by -1 do
if s[i] <= maxi then
exit
end if
s[i] = mini
s[i-1] += 1
end for
if s[1] <= maxi then
return s
else
return -1 -- end
end if
end function
-- Demo
object x
integer mini, maxi, k
-- a) your example:
mini = 'A'
maxi = 'D'
k = 3
x = repeat(mini, k)
while sequence(x) do
puts(1, x & "\n")
x = next_variation_r(x, mini, maxi)
end while
puts(1, "-------\n")
-- b) get all possible combinations of two 6-sided dice:
mini = 1
maxi = 6
k = 2
x = repeat(mini, k)
while sequence(x) do
? x
x = next_variation_r(x, mini, maxi)
end while
Regards,
Juergen
--
http://luethje.eu/prog/
6. Re: Project Programmer Wanter
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
>
[snipped]
> DDB
> DDC
> DDD
>
> How would that function be implemented to achieve that?
Here is another implementation:
function VariationsRep(integer n, sequence s)
integer len
atom lin,lines,rep
object si
sequence p
len = length(s)
lines = power(len,n)
p = repeat(repeat(0,n),lines)
rep = 1
for col = n to 1 by -1 do
lin = 1
while lin <= lines do
for i = 1 to len do
si = s[i]
for k = 1 to rep do
p[lin][col] = si
lin += 1
end for
end for
end while
rep *= len
end for
return p
end function
sequence v
-- a) your example:
v = VariationsRep(3,"ABCD")
for i = 1 to length(v) do
printf(1,"%3d = %s\n", {i,v[i]})
end for
-- b) get all possible combinations of two 6-sided dice:
v = VariationsRep(2,{1,2,3,4,5,6})
for i = 1 to length(v) do
printf(1,"%3d = %d,%d\n", {i,v[i][1],v[i][2]})
end for
-- c) show all 8 bits binary numbers:
v = VariationsRep(8,{'0','1'})
for i = 1 to length(v) do
printf(1,"%3d = %s\n", {i-1,v[i]})
end for
Regards,
Fernando
7. Re: Project Programmer Wanter
- Posted by c.k.lester <euphoric at ckleste?.c?m>
Feb 08, 2008
-
Last edited Feb 09, 2008
Fernando Bauer wrote:
>
> Here is another implementation:
> function VariationsRep(integer n, sequence s)
Nice, Fernando! Can you do one that does combinations? 8)
8. Re: Project Programmer Wanter
c.k.lester wrote:
>
> Fernando Bauer wrote:
> >
> > Here is another implementation:
> > function VariationsRep(integer n, sequence s)
>
> Nice, Fernando! Can you do one that does combinations? 8)
Hi CK!
Sorry, I won't have access to a computer this weekend, so I hope that I can do
that next week.
Regards,
Fernando
9. Re: Project Programmer Wanter
- Posted by Juergen Luethje <jur at nurf?erspa?.de>
Feb 09, 2008
-
Last edited Feb 10, 2008
The following function for building variations with repetition is
a little clearer and faster than the one which I posted yesterday:
global function next_variation_r (sequence s, integer mini, integer maxi)
-- Return the next variation with repetition on s
-- (in lexicographic order);
-- ** In order to get all possible variations, s must initially only
-- contain 'mini' values. **
integer i
i = length(s)
-- carry if necessary
while s[i] >= maxi do
s[i] = mini
i -= 1
if i = 0 then
return -1 -- end
end if
end while
s[i] += 1
return s
end function
-- Demo
object x
integer mini, maxi, k
-- a) Ret's example:
mini = 'A'
maxi = 'D'
k = 3
x = repeat(mini, k)
while sequence(x) do
puts(1, x & "\n")
x = next_variation_r(x, mini, maxi)
end while
puts(1, "-------\n")
-- b) Get all possible combinations of two 6-sided dice:
mini = 1
maxi = 6
k = 2
x = repeat(mini, k)
while sequence(x) do
? x
x = next_variation_r(x, mini, maxi)
end while
Regards,
Juergen
--
http://luethje.eu/prog/
10. Re: Project Programmer Wanter
- Posted by Ret Law <retlaw144 at y?h?o.com>
Feb 09, 2008
-
Last edited Feb 10, 2008
So CChris and Juergen,
The functions and procedures you gave will output a text file with the full
enumeration of the succession of A,B,C,D permuations across x digits in the order
of A,B,C,D from right to left?
Please, I am a complete beginner to Euphoria and really only wanted this
specific task so your help will save me a considerable amount of time. I am not
sure how to piece this information together to actually write an executable
Euphoria program.
It aPpears to be a simple program to compute judging by the speed of response.
Would it be possible to provide me with a complete executable (with source code)
file that will process and output the desired enumeration with variable input.
e.g.#1:
INPUT:
Items: A,B,C,D
Digits: 3
Order: A,B,C,D
OUTPUT:
AAA
AAB
AAC
AAD
...
<snip>
...
DDA
DDB
DDC
DDD
e.g.#2:
Items: A,H,I.Y
Digits: 5
Order: H,I,Y,A
OUTPUT:
HHHHH
HHHHI
HHHHY
HHHHA
.....
<snip>
.....
AAAAH
AAAAI
AAAAY
AAAAA
e.g.#3:
Items: A,E,L,P,R,Y
Digits: 3
Order: P,L,A,Y,E,R
OUTPUT:
PPP
PPL
PPA
PPY
PPE
PPR
...
<snip>
...
RRP
RRL
RRA
RRY
RRE
RRR
11. Re: Project Programmer Wanter
To all those participating (Juergen, Fernando, CChris, etc)
OK we have a good group of people with a range of approaches to the program.
I think we want to make both a library file and a EXE file for the program so
that it can be implemented into any other Euphoria task and be implemented as a
unique program.
Inasmuch, we ought make it as functionally robust as possible.
I have a specific use for the program and could give very specific parameters
for base and expanded implementation; yet in being a voluntary project I feel it
wise to make it a common library file and unique program for broad and extended
use.
Basically, we want a library file and a unique executable permutational
enumeration program that receives the input of a) the number of digits, and b)
the sequence of characters; that enumerates the permutations of the character set
according to the given order as an outputted text file.
Where:
n = the number of digits
s = the order and sequence of single characters as a single character string
The order of successive permutations ought be according to the pattern of the
provided output of the following example.
e.g.:
Input:
n=5
s = tobe1
Output:
ttttt
tttto
ttttb
tttte
tttt1
tttot
tttoo
tttob
tttoe
ttto1
tttbt
tttbo
tttbb
tttbe
tttb1
tttet
ttteo
ttteb
tttee
ttte1
ttt1t
ttt1o
ttt1b
ttt1e
ttt11
ttott
ttoto
ttotb
ttote
ttot1
ttoot
ttooo
ttoob
ttooe
ttoo1
ttobt
ttobo
ttobb
ttobe
ttob1
ttoet
ttoeo
ttoeb
ttoee
ttoe1
tto1t
tto1o
tto1b
tto1e
tto11
ttbtt
ttbto
ttbtb
ttbte
ttbt1
ttbot
ttboo
ttbob
ttboe
ttbo1
ttbbt
ttbbo
ttbbb
ttbbe
ttbb1
ttbet
ttbeo
ttbeb
ttbee
ttbe1
ttb1t
ttb1o
ttb1b
ttb1e
ttb11
ttett
tteto
ttetb
ttete
ttet1
tteot
tteoo
tteob
tteoe
tteo1
ttebt
ttebo
ttebb
ttebe
tteb1
tteet
tteeo
tteeb
tteee
ttee1
tte1t
tte1o
tte1b
tte1e
tte11
tt1tt
tt1to
tt1tb
tt1te
tt1t1
tt1ot
tt1oo
tt1ob
tt1oe
tt1o1
tt1bt
tt1bo
tt1bb
tt1be
tt1b1
tt1et
tt1eo
tt1eb
tt1ee
tt1e1
tt11t
tt11o
tt11b
tt11e
tt111
.....
<snip>
.....
11111
We may later expand it to include alternate sorting methods or include the
enumeration of the combination of all enumerations of a given permutation.
12. Re: Project Programmer Wanter
To All Concerned
In nmanually processing an array of such permutation enumerations, I figured
that the actual enumeration process could be processed quicker and more simply by
a multi-linear approach.
i.e. for n (the number of digits), s (the ordered character string) thus x (the
total number of characters in the ordered character string as "s1..sx") and f
(output file name):
1. c=1 (current column), p=n-1 (current power), open the output file
2. Goto column c, row 1 and print s1..sx vertically down the column x^p times
each and repeat onward down the column until reaching row x^n
3. c=c+1 and p=p-1
4. If c>n and p<0 then save the output file and stop
5. Repeat items 2-4
The executable program version should display a request for user input of x, s
and f before processing the enumeration.
The library function version should expect the variables with the function call
to process the enumeration.
13. Re: Project Programmer Wanter
CChris wrote:
>
> 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?
>
Here is a modified implementation that doesn't keep the whole data in memory,
writes both item and symmetric item. It assumes the objects whose arrangements
are to be written are byte sized:
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
global procedure enumerate(
sequence succession, -- list of objects to appear in order
integer n, -- number of digits
sequence outfile) -- output file name
-- WARNING: no check is made for available space on the medium you write to.
-- Writing a file that's too big may result in data loss or physical damage
-- to medium.
-- AUTHOR WILL DECLINE ANY CLAIM FOR LIABILITY.
sequence counter,rev_item,item
integer ls,fh
ls=length(succession)
counter=update_counter("",1,ls,n)
item=repeat(0,n)
rev_item=repeat(0,n)
fh=open(outfile,"wb")
if fh=-1 then
puts(2,"Could not open output file - bailing out")
return
end if
-- The first byte in the output file is the length of each item.
-- Remove the next statement if it will always be 4, for instance
puts(fh,n)
while compare(counter,{})=1 do
for i=counter[$] to n do
item[i]=succession[counter[i]]
rev_item[i]=succession[$+1-counter[i]]
end for
puts(fh,item)
puts(fh,rev_item)
counter=update_counter(counter,1,ls,n)
end while
close(fh)
end procedure
global procedure display_output(sequence infile)
-- reads what enumerate() has written
integer fh,n
sequence item,rev_item
fh=open(infile,"rb")
if fh=-1 then
puts(2,"Couldn't locate input file - bailing out.")
return
end if
-- replace next statement with a fixed assignment like n=4 if you removed
-- the puts(fh,n) statement in enumerate().
n=getc(fh) -- record length
while 1 do
item=get_bytes(fh,n)
if not length(item) then-- normal termination
exit
elsif length(item)<n then
puts(2,"Input file doesn't hold properly matched strings - halting.")
exit
end if
rev_item=get_bytes(fh,n)
if length(rev_item)<n then
puts(2,"Input file doesn't hold properly matched strings - halting.")
exit
end if
-- change this statement in order to meet your display requirements
printf(1,"%s %s\n",{item,rev_item})
end while
close(fh)
end procedure
CChris
