Chris F Clark wrote:
Yes, there is literature on the generating side of the regular
expression/FSM model. In fact, the matching problem and the
generating problems are exactly equivalent. A slight variation of the
definition of how a matcher works, turns it into a generator and vice
versa.
Going in a slightly different direction ...
There has been lots of published work on how to create efficient FSMs
from regexps. Generally these FSMs are used for pattern matching (i.e.
does string 's' match regexp 'e'?).
Is there any corresponding literature on the topic addressed by the
OP's
Yes, there is literature on the generating side of the regular
expression/FSM model. In fact, the matching problem and the
generating problems are exactly equivalent. A slight variation of the
definition of how a matcher works, turns it into a generator and vice
versa. To directly generate
Dinko Tenev [EMAIL PROTECTED] wrote:
Dirk Thierbach wrote:
[A lot of stuff]
Now clearer?
Let's leave it there, and take a break.
Maybe it would help to just take a concrete example, and work through
it. Then you'll see exactly what happens.
- Dirk
--
Dirk Thierbach wrote:
Dinko Tenev [EMAIL PROTECTED] wrote:
I don't see immediately how exactly this is going to work. Unless I'm
very much mistaken, a FSA in the classical sense will accept or reject
only after the whole sequence has been consumed, and this spells
exponential times.
[EMAIL PROTECTED] wrote:
Call a wc 'free' if it satisfies the propery that every letter 'a' in
it appears only in the form '*a*', and 'anchored' otherwise. What if
all wc's are free? How does this affect the DFA? Does it minimize
nontrivially? Keep in mind I'm new to DFA theory.
There would
Dinko Tenev [EMAIL PROTECTED] wrote:
Dirk Thierbach wrote:
[One cannot escape exponential behaviour]
But you cannot get rid of this. Consider S = {a, b}, W = {a}.
Then there are |S|^n result elements for n 1, and you have to enumerate
all of them.
Yes, but then, they are in the target
[EMAIL PROTECTED] [EMAIL PROTECTED] wrote:
Call a wc 'free' if it satisfies the propery that every letter 'a' in
it appears only in the form '*a*', and 'anchored' otherwise.
Would '*ab*' be free or anchored?
What if all wc's are free? How does this affect the DFA?
I don't know. The
Dirk Thierbach wrote:
[A lot of stuff]
Now clearer?
- Dirk
Actually, it's getting all the messier, and we seem to be running
around in circles. I've already lost track of the point you're trying
to make, and it seems that you're missing most of my points.
Let's leave it there, and take a
Hello,
The solution that would have the most utility would be one where the
elements are generated one-by-one, loop-like, so that they can be used
in the body of a loop, and to avoid the fact that even with exclusion
the cardinality of the target set EX^n could be in the millions even
with a full
Dirk Thierbach wrote:
If more time during preprocessing is allowed, another idea is to
treat the wildcard expressions as regular expressions, convert
each into a finite state machine, construct the intersection of
all these state machines, minimize it and then swap final and non-final
states.
[EMAIL PROTECTED] schreef:
The solution that would have the most utility would be one where the
elements are generated one-by-one, loop-like, so that they can be used
in the body of a loop, and to avoid the fact that even with exclusion
the cardinality of the target set EX^n could be in the
Dinko Tenev [EMAIL PROTECTED] wrote:
Dirk Thierbach wrote:
If more time during preprocessing is allowed, another idea is to
treat the wildcard expressions as regular expressions, convert
each into a finite state machine, construct the intersection of
all these state machines, minimize it and
Dirk Thierbach wrote:
Dinko Tenev [EMAIL PROTECTED] wrote:
Dirk Thierbach wrote:
If more time during preprocessing is allowed, another idea is to
treat the wildcard expressions as regular expressions, convert
each into a finite state machine, construct the intersection of
all these
On 2006-03-23, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote:
The solution that would have the most utility would be one where the
elements are generated one-by-one, loop-like, so that they can be used
in the body of a loop, and to avoid the fact that even with exclusion
the cardinality of the
Call a wc 'free' if it satisfies the propery that every letter 'a' in
it appears only in the form '*a*', and 'anchored' otherwise. What if
all wc's are free? How does this affect the DFA? Does it minimize
nontrivially? Keep in mind I'm new to DFA theory.
Walter Kehowski
--
Dinko Tenev [EMAIL PROTECTED] wrote:
I don't see immediately how exactly this is going to work. Unless I'm
very much mistaken, a FSA in the classical sense will accept or reject
only after the whole sequence has been consumed, and this spells
exponential times.
Exponential in respect to
funkyj wrote:
How about the other iterator characteristics?
when there is a huge solution space can I ask the prolog version to
give me the first 1000 solutions?
Geoffrey's post above offers one way to do this from within a REPL.
Within a program, as soon as you accept a solution, you're
OK, here's a case that will make your program run in exponential time:
S = { a, b }, W = { *a*b, *b*a } -- on my machine, it starts getting
ugly as soon as n is 15 or so. Note that S^n - W = { a^n, b^n }.
In general, whenever all the patterns in the set match against the last
position, your
Mark Carter wrote:
At the risk of being labelled a troll
One thing I just discovered, and by which I mean *really* discovered ...
is that Lisp is an interactive environment. I am working on trying to
verify the contents of disks. I noticed that the input formats are
slightly wrong, and
Mark Carter [EMAIL PROTECTED] writes:
A programmers mindset is usually geared towards writing applications. What
I'm currently doing in Lisp is building up functions as I need them. Using
emacs, I can just C-x C-e to make my functions live, and when it's time to
stop for the day, save my
[Had to drop alt.comp.lang.haskell, otherwise my newsserver doesn't accept it]
Dinko Tenev [EMAIL PROTECTED] wrote:
OK, here's a case that will make your program run in exponential time:
S = { a, b }, W = { *a*b, *b*a } -- on my machine, it starts getting
ugly as soon as n is 15 or so. Note
And it doesn't really matter what language you use to implement this
algorithm, it's the idea that counts. Notation aside, all
implementations will be quite similar.
I'll guess I'll get out my Turing tape. ;)
What are some good references for finite state machines? Minimization?
--
[EMAIL PROTECTED] [EMAIL PROTECTED] wrote:
What are some good references for finite state machines? Minimization?
A classic is Introduction to automata theory, languages and computation
by Hopcroft and Ullman. But any other book about finite state machines
should cover these topics, too. There
[EMAIL PROTECTED] wrote:
After the basic fact of generating the exclusion - a considerable
achievement - the program should be interactive. What if the target set
has thousands or millions of elements? There should be a loop-like way
('do' in Haskell, for example) to peel off the elements
Dinko Tenev wrote:
Speculation: the time for
building-up a smart structure to speed-up enumeration, together with
the time for enumerating the set using that structure, should sum up to
roughly Theta( n*|S^n| ), even with a really smart algorithm.
OK, maybe not.
This might be the worst case,
[EMAIL PROTECTED] wrote in message
news:[EMAIL PROTECTED]
After the basic fact of generating the exclusion - a considerable
achievement - the program should be interactive. What if the target set
has thousands or millions of elements? There should be a loop-like way
('do' in Haskell, for
Dinko Tenev wrote:
Doug Quale wrote:
Hmmm...storage is not an issue in the Prolog version. It generates a
candidate solution, then checks membership in the wildcard set, then
backtracks (backtracking is caused by fail in the test goal.) On
backtracking, it effectively forgets the last
Doug Quale wrote:
funkyj [EMAIL PROTECTED] writes:
One advantage of a generator over filtering the full product is that I,
as the user of the generator, am not obligated to iterate over the
entire solution space.
Are there other _practical_ advantages of generators over mapping
[EMAIL PROTECTED] wrote:
It would seem that your program is just filtering the full cartesian
product, right? The solution I'm looking for generates the elements
one-by-one so that it could be used in a loop.
OK, having read some of the comments so far, I have the feeling that I
may be missing
Hi,
You wrote into the Qilang News group with your problem.
This is a solution in 17 lines of Qi for any n-product = 2.
It falls short of your complete requirement since it uses
generate and then test, rather than interleaving the
two.
(define challenge
Patterns N X - (filter (/. Y (member Y
I'd like to propose a coding challenge of my own. The challenge is to
reproduce the TEA (Tiny Encryption Algorith):
http://www.simonshepherd.supanet.com/tea.htm
in your language of choice.
Here's the code, just two simple functions:
void encipher(unsigned long *const v,unsigned long *const w,
Interesting. But you probably need to post this as a new
message, since it is a distinctly different
problem from the one driving this thread.
Mark
--
http://mail.python.org/mailman/listinfo/python-list
Mark Tarver wrote:
Interesting.
At the risk of being labelled a troll, one thought that is occuring to
me is that in Lisp it seems that sometimes it is difficult to achieve a
simple thing in a simple way. To clarify ... recently, I had been
trying to obtain md5 hashes of the files we had on
Dinko Tenev [EMAIL PROTECTED] wrote in message
news:[EMAIL PROTECTED]
[EMAIL PROTECTED] wrote:
It would seem that your program is just filtering the full cartesian
product, right? The solution I'm looking for generates the elements
one-by-one so that it could be used in a loop.
Mark Carter [EMAIL PROTECTED] writes:
I'd like to propose a coding challenge of my own. The challenge is to
reproduce the TEA (Tiny Encryption Algorith):
http://www.simonshepherd.supanet.com/tea.htm
in your language of choice.
Here's the code, just two simple functions:
void
I had a crack at it in Lisp. My version doesn't work - but of greater
concern to me is that it doesn't appear nearly as compact as the C
version. Anyway, here's my Lisp code (no prizes for guessing that I'm a
noob to Lisp):
Lot's of things you can write more compact.
But compact is not always
[EMAIL PROTECTED] writes:
(defun (val num-bytes)
Right-shift positive integer val by num-bytes
(floor (/ val (expt 2 num-bytes
or just (floor val (expt 2 num-bytes))
'as
--
http://mail.python.org/mailman/listinfo/python-list
[ note followups ]
Mark Carter [EMAIL PROTECTED] writes:
I'd like to propose a coding challenge of my own. The challenge is to
reproduce the TEA (Tiny Encryption Algorith):
http://www.simonshepherd.supanet.com/tea.htm
in your language of choice.
Here's mine, in Common Lisp.
(defmacro
After the basic fact of generating the exclusion - a considerable
achievement - the program should be interactive. What if the target set
has thousands or millions of elements? There should be a loop-like way
('do' in Haskell, for example) to peel off the elements one-by-one and
then terminate.
Yes, the program is quite a jumble: but it works. And I didn't post to
python newsgroup since I was limited to just 5 newsgroups and didn't
feel like doing multiple postings to multiple newsgroups.
--
http://mail.python.org/mailman/listinfo/python-list
Here is an nice intro to K:
http://www.kuro5hin.org/?op=displaystory;sid=2002/11/14/22741/791
This is where K starts to set itself from apart from most of the
common programming languages in use today. You rarely write loops in K
(KDB is 100% loop-free), instead you use adverbs. An adverb
When I run this I get through ghc I get
C:\Documents and Settings\User\My Documents\wildcardghc
./wc-zielonka.hs
compilation IS NOT required
C:/Languages/ghc/ghc-6.4.1/libHSrts.a(Main.o)(.text+0x1d):Main.c:
undefined refe
rence to `__stginit_ZCMain'
The cardinality of excluding '*a*b*' from S^n should be
(m-1)^(n-1)*(m+n-1), where m=|S|. For m=5 this becomes 4^(n-1)*(n+4),
and your table fits this formula. As far as generating and testing, an
'ideal' solution would be to 'start from the ground up', as in
excluding length 2 wc, and then length
Nice! How to put it in a loop? I'm totally a newbie to Lisp myself,
just gettng into Graham and Touretzky. Let's create a problem. Suppose
after excluding I want to know if the digits sum to 12, say, like maybe
they're part of a partition. S={0,..6}, S^5, excluding *1*5* and
1*2*3*, say. How
[EMAIL PROTECTED] schrieb:
This is where K starts to set itself from apart from most of the
common programming languages in use today. You rarely write loops in K
(KDB is 100% loop-free), instead you use adverbs. An adverb modifies a
function, returning another function, changing the ways it
OK, a bad case of RTFM. I saved your file as WildCartesian.hs and then
1) command line: ghci WildCartesian.hs
2) Get some loading messages
3) command line: test
and it works! But how do I compile it to get a program with command
line arguments? I'm looking through Daume's tutorial right now.
--
Heh, here's a Prolog version:
==
gen( _, 0, [] ) :- !.
gen( S, N, [H | T] ) :- member( H, S ), M is N - 1, gen( S, M, T ).
==
Yep, that's it :)))
Here's how to test it:
[EMAIL PROTECTED] wrote:
-- The states are lists of regular expressions
-- where [a,b,..] means match a or b or...
I haven't run or studied your program yet myself but what I had in mind
was that the list of wc's are *all* to be excluded, so the list
[wc1..wcn] is to correspond generating
You may be interested in, or already know about
http://www.lambdassociates.org/
http://www.lambdassociates.org/aboutqi.htm
http://www.lambdassociates.org/webbook/contents.htm
http://www.lambdassociates.org/prolog.htm
Let me know what you think.
--
It would seem that your program is just filtering the full cartesian
product, right? The solution I'm looking for generates the elements
one-by-one so that it could be used in a loop.
--
http://mail.python.org/mailman/listinfo/python-list
[EMAIL PROTECTED] said:
I haven't run or studied your program yet myself but what I had in mind
was that the list of wc's are *all* to be excluded
I think it already does what you want. You might want to change
run n alphabet pat =
generate terminal null transition [pat] n alphabet to
[EMAIL PROTECTED] wrote:
It would seem that your program is just filtering the full cartesian
product, right? The solution I'm looking for generates the elements
one-by-one so that it could be used in a loop.
Oops...missed that part.
It took me a while to study the exchange on this topic more
sa wrote:
in k:
cp:{[c;n;p]+(n#c)_vs(!_ c^n)_dvl,/{2_sv+(,/,/:\:)/(),/:@[x;x=-1;:[;!c]]}'p}
That one goes a long way as a proof of eg evolution theory, you know,
monkeys reproducing shakespeare with a typewriter k-board and all that :)
examples:
cp[2;3;,0 -1 1]
(0 0 0
0 1 0
1 0
Tomasz Zielonka said:
I've implemented the same concept yesterday evening...
It's uncanny reading such similar code coming from another person!
--
http://mail.python.org/mailman/listinfo/python-list
Wade Humeniuk wrote:
[EMAIL PROTECTED] wrote:
What I have in mind is the efficient, enumerated generation of the
complement S^n/WC(S^n). A good program should initialize, generate, and
terminate.
T=cartprodex(S,n,WC); //initialize
for all i in T do
what you want with i
test
[EMAIL PROTECTED] [EMAIL PROTECTED] writes:
What I have in mind is the efficient, enumerated generation of the
complement S^n/WC(S^n). A good program should initialize, generate, and
terminate.
T=cartprodex(S,n,WC); //initialize
for all i in T do
what you want with i
test to see if
[EMAIL PROTECTED] wrote:
The wildcard exclusion problem is interesting enough to have many
distinct, elegant solutions in as many languages.
In that case, you should have crossposted to comp.lang.python also.
Your program looks like a dog's breakfast.
--
[EMAIL PROTECTED] wrote:
It would seem that your program is just filtering the full cartesian
product, right? The solution I'm looking for generates the elements
one-by-one so that it could be used in a loop.
One advantage of a generator over filtering the full product is that I,
as the user
funkyj [EMAIL PROTECTED] writes:
One advantage of a generator over filtering the full product is that I,
as the user of the generator, am not obligated to iterate over the
entire solution space.
Are there other _practical_ advantages of generators over mapping
filtering complete sets?
The python code below generates a cartesian product subject to any
logical combination of wildcard exclusions. For example, suppose I want
to generate a cartesian product S^n, n=3, of [a,b,c,d] that excludes
'*a*b*' and '*c*d*a*'. See below for details.
CHALLENGE: generate an equivalent in ruby,
[EMAIL PROTECTED] wrote:
The python code below generates a cartesian product subject to any
logical combination of wildcard exclusions. For example, suppose I want
to generate a cartesian product S^n, n=3, of [a,b,c,d] that excludes
'*a*b*' and '*c*d*a*'. See below for details.
CHALLENGE:
Tomasz Zielonka wrote:
putStrLn (concat (intersperse [generateMatching, show a, show
b, show c]))
Minor correction: it should be generateNotMatching.
Best regards
Tomasz
--
I am searching for programmers who are good at least in
(Haskell || ML) (Linux || FreeBSD || math)
for work
Major correction (missing case):
Tomasz Zielonka wrote:
generateMatching :: (Ord a) = Int - Set a - [Pat a] - [[a]]
generateMatching 0 _[]= [[]]
generateMatching 0 alphabet (All:ps) = generateMatching 0 alphabet ps
generateMatching 0 _(_:_) = []
Best regards
Tomasz
Flame war? Absolutely not. My reason is to learn. There are many sites
dedicated to reasonably objective comparisons between languages. Here
are two examples:
http://www.smallscript.org/Language%20Comparison%20Chart.asp
http://www.jvoegele.com/software/langcomp.html
The wildcard exclusion
The point is to submit elegant code that showcases the features of each
language. And the problem is, just to clarify, given a set WC of
wildcards in any logical combination, and if WC(S^n) is the set all s
in S^n that matches the wildcards, then efficiently generate the
complement S^n\WC(S^n).
[EMAIL PROTECTED] schreef:
There are many sites
dedicated to reasonably objective comparisons between languages. Here
are two examples:
http://www.smallscript.org/Language%20Comparison%20Chart.asp
http://www.jvoegele.com/software/langcomp.html
http://shootout.alioth.debian.org/
--
Without much testing. Common Lisp
Pattern exclusions are made lispy.
(defun all-lists (list length)
(unless (zerop length)
(if (= length 1) (mapcar #'list list)
(loop for elt in list
nconc
(mapcar (lambda (rest)
(cons elt rest))
What I have in mind is the efficient, enumerated generation of the
complement S^n/WC(S^n). A good program should initialize, generate, and
terminate.
T=cartprodex(S,n,WC); //initialize
for all i in T do
what you want with i
test to see if any more
terminate if not
and it should do this
A B)
(B B B)
set = (1 2)
n= 3
patterns = ((1 ANY 2) (2 ANY 1))
---
(1 1 1)
(1 2 1)
(2 1 2)
(2 2 2)
NIL
CL-USER
source:
cartesian products minus wildcard patterns per:
Newsgroups: comp.lang.lisp, etc...
Subject: Programming challenge: wildcard
NOTE: I am a lisp newbie. I'm sure our resident lisp experts can
create much better (both faster, shorter and clearer) solutions than
the one above.
Even I could have created something shorter but I thought it would be
fun to apply the utility function approach in decomposing the
problem.
in k:
cp:{[c;n;p]+(n#c)_vs(!_ c^n)_dvl,/{2_sv+(,/,/:\:)/(),/:@[x;x=-1;:[;!c]]}'p}
examples:
cp[2;3;,0 -1 1]
(0 0 0
0 1 0
1 0 0
1 0 1
1 1 0
1 1 1)
cp[2;3;(0 -1 1;1 -1 0)]
(0 0 0
0 1 0
1 0 1
1 1 1)
cp[2;3;(0 -1 1;1 -1 1)]
(0 0 0
0 1 0
1 0 0
1 1 0)
arguments of cp:
c =
[EMAIL PROTECTED] [EMAIL PROTECTED] writes:
The python code below generates a cartesian product subject to any
logical combination of wildcard exclusions. For example, suppose I want
to generate a cartesian product S^n, n=3, of [a,b,c,d] that excludes
'*a*b*' and '*c*d*a*'. See below for
The asterisk '*' matches any sequence of elements, not just one
element. The wildcard '*1*2*' would then correspond to a tuple with a 1
preceding a 2 in any positions. The wc '1*2' would correspond to a
starting 1 and an ending 2 with anything in between. The wc *12* would
correspond to a 1
Is this Haskell implementation what you want? It does the wildcard
matching through a state machine and it essentially threads the
state machine through the cartesian product, switching to the
ordinary cartesian product when possible as an optimisation.
The execution of the state machine is shared
[EMAIL PROTECTED] wrote:
What I have in mind is the efficient, enumerated generation of the
complement S^n/WC(S^n). A good program should initialize, generate, and
terminate.
T=cartprodex(S,n,WC); //initialize
for all i in T do
what you want with i
test to see if any more
terminate
Oops, problems cutting an pasting, should be,
;; Wade Humeniuk
(defclass odometer ()
((base :initform 0 :accessor base)
(meter :initform nil :accessor meter)
(n-digits :initarg :n-digits :accessor n-digits)
(digit-set :initarg :digit-set :accessor digit-set)))
(defmethod
-- The states are lists of regular expressions
-- where [a,b,..] means match a or b or...
I haven't run or studied your program yet myself but what I had in mind
was that the list of wc's are *all* to be excluded, so the list
[wc1..wcn] is to correspond generating all tuples matching not(wc1 and
78 matches
Mail list logo
