Compilers - sampling algoritm based on indexed constrains

Author

sampling algoritm based on indexed constrains

Albretch

2004-12-02, 3:57 am

I know this might not exactly be a question to this newsgroup, but,
again, I don't know how to solve this type of problems. I need to
understand it well, because I see myself using this a lot

I have been thinking about an implementation of a sampling algorithm
that would conditionally constrain selections preferably in Java (ANSI
C/C++ are fine, too).

Say, you have a number of items you may conditionally select. Cases
would be:

1._ you may select any and any number of them,
2._ you may select any, but only a given number of them, say 1, 2 or 3
3._ you either select the first or second and any other one,
4._ you may select any as long as the total of certain weight remains
in a range
5._ you -must- select all
. .

As you can see it is not only about the items themselves but there
are also aggregations involved.

It would pretty much be like an indexing of possible WHERE clauses in
SQL. I could imagine other people have stumbled on these kinds of
problems before.

I have been thinking about implementing a solution to the problem based
on the "language (or grammar how is it called?) pattern" using the
knapsack algorithm to try keep things tidy.

I did search and could not find anything similar to what I was looking for.
Maybe you know of something like this or can avail me of some leads in
the right direction.

John Lawson

2004-12-11, 3:59 pm

Albretch wrote:

> I have been thinking about an implementation of a sampling algorithm
> that would conditionally constrain selections preferably in Java (ANSI
> C/C++ are fine, too).
>
> Say, you have a number of items you may conditionally select. Cases
> would be:
>
> 1._ you may select any and any number of them,
> 2._ you may select any, but only a given number of them, say 1, 2 or
3
> 3._ you either select the first or second and any other one,
> 4._ you may select any as long as the total of certain weight remains
> in a range
> 5._ you -must- select all
> . .

> I did search and could not find anything similar to what I was
> looking for. Maybe you know of something like this or can avail me
> of some leads in the right direction.

Yes, you *could* write a simple scanner and parser to determine the
validity of sampling criteria. What you do with valid criteria after
that is up to you!

I would type "Scanners", "parsers" and "simple examples" into Google
and try and find a tutorial on how to write them. You will also need
to define the grammar.

Flex would be a good tool to use to see how parsers and scanners work,
although for your problem it might be a little overcomplex :)

A Java binary is available here and there are also some useful papers
and tutorials:
http://www.flex-compiler.lcs.mit.edu/Harpoon/

John

Sponsored Links