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
> ver
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 (rath
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
A quick fix: change your last two functions to:
def generateNotMatching(A,n,P):
for g in gen(A,n,P,[]):
for x in g:
yield x
def gen(A,n,P,acc):
if any(imap((lambda p: allStar(p) and notNullOrZero(p,n)), P)):
yield []
else:
if n==0:
Michael,
Yes! That is precisely what I had in mind!
Thanks,
Walter Kehowski
--
http://mail.python.org/mailman/listinfo/python-list
[EMAIL PROTECTED] wrote:
> The python code below is adapted from a Haskell program written by
> Tomasz
> Wielonka on the comp.lang.functional group. It's more verbose than his
> since I wanted to make sure I got it right.
>
> http://groups.google.com/group/comp.lang.functional/browse_frm/thread...
The python code below is adapted from a Haskell program written by
Tomasz
Wielonka on the comp.lang.functional group. It's more verbose than his
since I wanted to make sure I got it right.
http://groups.google.com/group/comp.lang.functional/browse_frm/thread...
Does anyone know how to turn it int
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
--
http://mail.python.org/mailman
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
[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 impo
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
[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 woul
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
> >> > e
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.
>> Exponentia
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
--
http://mail.python.org
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 th
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
>
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, mini
[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 th
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
> s
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
[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. The
"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?
--
http://mai
[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. No
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
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 neede
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 curre
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
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 l
<[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, f
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 ca
[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
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.
-
[ 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
[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
> 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 alw
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 enci
"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 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
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
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,
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
[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 missi
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
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.
--
[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 way
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 w
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
When I run this I get through ghc I get
C:\Documents and Settings\User\My Documents\wildcard>ghc
"./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'
C:/Languages/ghc/ghc-6.4.1/libHSrts.a(Main.o)
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 modi
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
"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
[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
[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.
--
http://mail.python.org/mailman/listi
"[EMAIL PROTECTED]" <[EMAIL PROTECTED]> writes:
> What I have in mind is the efficient, 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
Wade Humeniuk wrote:
> [EMAIL PROTECTED] wrote:
> > What I have in mind is the efficient, 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
> >
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
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
[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 mo
[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
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
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.
--
http://mail.python.org/mailman/listinfo/python-
[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 generati
Dan Piponi wrote:
> 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
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:
-- 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
.
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 initializ
[EMAIL PROTECTED] wrote:
> What I have in mind is the efficient, 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 i
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
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 adjacen
"[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
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 = cardina
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.
--
ng challenge: wildcard exclusion in cartesian
products
>Date: 16 Mar 2006 03:14:23 -0800
(defun show-me (x) (format t "~A~%" x))
(defun set^n (fn set n &optional acc)
"call `fn' on each permutation of `set' raised to the `n' power"
(if (<= n
What I have in mind is the efficient, 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 without explic
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))
[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/
-
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). You
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 problem
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 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)
[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.
>
> CHALLEN
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,
83 matches
Mail list logo
