Prev: question about component integration or assembly
Next: Carnegie Mellon Software Architecture courses in NYC
From: Veloz on 18 Jan 2008 09:57
Hi there

Not sure this is the best place for this question.. but it might be.

How would you design a solution for the problem of effectively needing
a number of nested "foreach" statements but you don't know the number
at compile that?

That is let's say your algorithm needs to produce combinations. If you
knew in advance you had two "levels" of things, you would write

foreach(level1 = 0; level1 < somecount; level++) {
foreach(level2 = 0; level2 < somecount2; level2++) {
// do something with level1 and level2
}
}

If you knew in advance that you three such levels you would do this

foreach(level1 = 0; level1 < somecount; level++) {
foreach(level2 = 0; level2 < somecount2; level2++) {
foreach(level3 = 0; level3 < somecount3; level3++) {
// do something using level1, level2, level3
}
}
}

etc.

But what if yo don't know how many levels you were going to have in
advance..instead the number of levels is figured out at runtime. You
obviously can't code your foreach's in advance like I have done above.

So I'm interested in any algorithm, and if it's OO based, so much the
better!

TIA
Michael
From: WALLYWORLD on 18 Jan 2008 12:25

dear veloz,
see the algorithm for the insert sort.

that will check the subgroups and fill them in. a bubble sort is also good.
do a bubble...

"Veloz" <michaelveloz(a)gmail.com> wrote in message
news:a4acc220-ccec-495e-ae70-2c1fbbfee34f(a)d4g2000prg.googlegroups.com...
> Hi there
>
> Not sure this is the best place for this question.. but it might be.
>
> How would you design a solution for the problem of effectively needing
> a number of nested "foreach" statements but you don't know the number
> at compile that?
>
> That is let's say your algorithm needs to produce combinations. If you
> knew in advance you had two "levels" of things, you would write
>
> foreach(level1 = 0; level1 < somecount; level++) {
> foreach(level2 = 0; level2 < somecount2; level2++) {
> // do something with level1 and level2
> }
> }
>
> If you knew in advance that you three such levels you would do this
>
> foreach(level1 = 0; level1 < somecount; level++) {
> foreach(level2 = 0; level2 < somecount2; level2++) {
> foreach(level3 = 0; level3 < somecount3; level3++) {
> // do something using level1, level2, level3
> }
> }
> }
>
> etc.
>
> But what if yo don't know how many levels you were going to have in
> advance..instead the number of levels is figured out at runtime. You
> obviously can't code your foreach's in advance like I have done above.
>
> So I'm interested in any algorithm, and if it's OO based, so much the
> better!
>
> TIA
> Michael


From: Daniel T. on 18 Jan 2008 14:59
On Jan 18, 9:57 am, Veloz <michaelve...(a)gmail.com> wrote:
> Hi there
>
> Not sure this is the best place for this question.. but it might be.
>
> How would you design a solution for the problem of effectively needing
> a number of nested "foreach" statements but you don't know the number
> at compile that?
>
> That is let's say your algorithm needs to produce combinations. If you
> knew in advance you had two "levels"  of things, you would write
>
> foreach(level1 = 0; level1 < somecount; level++) {
>   foreach(level2 = 0; level2 < somecount2; level2++) {
>      // do something with level1 and level2
>   }
>
> }
>
> If you knew in advance that you three such levels you would do this
>
> foreach(level1 = 0; level1 < somecount; level++) {
>   foreach(level2 = 0; level2 < somecount2; level2++) {
>     foreach(level3 = 0; level3 < somecount3; level3++) {
>         // do something using level1, level2, level3
>     }
>   }
>
> }
>
> etc.
>
> But what if yo don't know how many levels you were going to have in
> advance..instead the number of levels is figured out at runtime. You
> obviously can't code your foreach's in advance like I have done above.

It depends on what you are going to be doing in the body of the inner-
most loop. Do you really need each of the variables from each loop? If
so, what do you use them for? When push comes to shove, this question
should probably be in the language group for the language you are
using.
From: Dmitry A. Kazakov on 18 Jan 2008 15:06
On Fri, 18 Jan 2008 06:57:48 -0800 (PST), Veloz wrote:

> But what if yo don't know how many levels you were going to have in
> advance..instead the number of levels is figured out at runtime. You
> obviously can't code your foreach's in advance like I have done above.
>
> So I'm interested in any algorithm, and if it's OO based, so much the
> better!

The algorithm is self-recursive. For each level of indices it call
enumeration anew. A model is as follows:

1. You define an abstract dimension index (component). It has operations
like Next, First, Last, <, > etc. Let it be Index.

2. You define a container type which elements are abstract indices. The
container is order, i.e. the result is a tuple of indices Path = Index_1 x
Index_2 x .... It has operations like First, the value of the first index,
Length, the number of indices, Suffix that returns a path the first index
removed.

3. You iterate between two Paths of same length using, for example, the
visitor pattern:

procedure Forall (Visited : in out Object; From, To : Path) is
begin
for I in First (From)..First (To)) loop
-- For each index value on this level
if Length (From) = 1 then
-- This is the last level, so visit the object
Visit (Visited);
else
-- Iterate between suffixes
Forall (Visitor, Suffix (From), Suffix (To));
end if;
end loop;
end Forall;

Surely you can optimize the above by passing the current depth as an
iteration parameter and getting elements of tuples at the depth without
modifying them:

procedure Forall
(Visited : in out Object; Depth : Natural; From, To : Path) is
begin
for I in From (Depth)..To (Depth) loop
-- For each index value on this level
if Depth = Length (From) then
-- This is the last level, so visit the object
Visit (Visited);
else
-- Iterate deeper
Forall (Visitor, Depth + 1, From, To);
end if;
end loop;
end Forall;

--
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de
From: H. S. Lahman on 21 Jan 2008 18:50
Responding to Veloz...

> How would you design a solution for the problem of effectively needing
> a number of nested "foreach" statements but you don't know the number
> at compile that?
>
> That is let's say your algorithm needs to produce combinations. If you
> knew in advance you had two "levels" of things, you would write
>
> foreach(level1 = 0; level1 < somecount; level++) {
> foreach(level2 = 0; level2 < somecount2; level2++) {
> // do something with level1 and level2
> }
> }
>
> If you knew in advance that you three such levels you would do this
>
> foreach(level1 = 0; level1 < somecount; level++) {
> foreach(level2 = 0; level2 < somecount2; level2++) {
> foreach(level3 = 0; level3 < somecount3; level3++) {
> // do something using level1, level2, level3
> }
> }
> }

First note that the bodies of these two examples are necessarily
different because they are parameterized differently (i.e., the second
example needs level3 but the first does not). So, in effect, you are
solving two different problems.

However, there are problems where data is optional or can be defaulted.
In that case, the number of variables being modified could change. The
answer in those kinds of problems is to separate the computational body
from the iterations. So one might have something like:

[ParameterList]
+ level1
+ level2
+ level3
....
+ setNextIteration()
| 1
| accesses
|
| R2
|
| 1
[Body]
+ doIt()

On each iteration somebody invokes setNextIteration() and then doIt().
The setNextIteration incorporates whatever iteration is necessary and
keeps track of where it is. (It needs some sort of reset() as well.) The
[ParameterList] keeps track of /all/ the possible parameters, some of
which may be defaulted or designated IGNORE. The doIt() behavior
accesses the levelN values and plugs them into its internal computation.

Note that the doIt computation is independent of how many levels of
iteration there are so long as it is viable to use defaults or ignore
values that aren't provided.

Now it is possible to parameterize the iteration. The setNextIteration()
behavior just needs to know which levelN values can be incremented,
which can be handled by a bitmap. It then just "walks" the increment
through the list of levels whose values change. As Daniel T. points out,
that reduces the problem to more of a language manipulation issue.


--
There is nothing wrong with me that could
not be cured by a capful of Drano.

H. S. Lahman
hsl(a)pathfindermda.com
Pathfinder Solutions
http://www.pathfindermda.com
blog: http://pathfinderpeople.blogs.com/hslahman
"Model-Based Translation: The Next Step in Agile Development". Email
info(a)pathfindermda.com for your copy.
Pathfinder is hiring:
http://www.pathfindermda.com/about_us/careers_pos3.php.
(888)OOA-PATH
 |  Next  |  Last
Pages: 1 2
Prev: question about component integration or assembly
Next: Carnegie Mellon Software Architecture courses in NYC