«

Hello,

I am trying to find out an alternate way to brute-force a variable
length vector with different variable length contents.


int chromossome[MAX_VECTOR_LENGTH]

int max_value_for_each_chromossome[MAX_VALUES]


The only way I am aware of is to build 'n' for(; statements, one
inside the other, but I would then need 1.000 (MAX_VECTOR_LENGTH)
for(; inside for(;.

One key issue is that each chromossome member has different max-
elements, for example:

chromossome[0] may have max_value_for_each_chromossome[0] = 5
(chromossome[0] int will range from 0 to 4)

chromossome[1] may have max_value_for_each_chromossome[1] = 2
(chromossome[1] int will range from 0 to 1)
....

Is there a simpler way to achive this rather than the for(; inside
for(; scheme?

Thank you

Paulo

On May 17, 3:40*pm, estan...@gmail.com wrote:
> Hello,
>
> I am trying to find out an alternate way to brute-force a variable
> length vector with different variable length contents.
>
> int chromossome[MAX_VECTOR_LENGTH]
>
> int max_value_for_each_chromossome[MAX_VALUES]

So which of these is variable length? Or do you have a set of
MAX_VECTOR_LENGTH arrays each of which has length set in
max_value_each_chromossome[]?

> The only way I am aware of is to build 'n' for(; statements, one
> inside the other, but I would then need 1.000 (MAX_VECTOR_LENGTH)
> for(; inside for(;.

What's n? I would think it unlikely you will ever need for-loops
nested 1000-deep.

>
> One key issue is that each chromossome member has different max-
> elements, for example:
>
> chromossome[0] may have max_value_for_each_chromossome[0] = 5
> (chromossome[0] int will range from 0 to 4)
>
> chromossome[1] may have max_value_for_each_chromossome[1] = 2
> (chromossome[1] int will range from 0 to 1)

So [0] ranges from 0..4. [1] ranges from 0..1. There doesn't seem to
be a problem.

What is it you are trying to achieve?

Perhaps give a more fully worked out example using small values then
we can see the pattern.

--
Bartc

writes:

> int chromossome[MAX_VECTOR_LENGTH]
>
> int max_value_for_each_chromossome[MAX_VALUES]
>
>
> The only way I am aware of is to build 'n' for(; statements, one
> inside the other, but I would then need 1.000 (MAX_VECTOR_LENGTH)
> for(; inside for(;.

I think you're trying to iterate through all possible value
assignments. I'd do something like this (which is untested):

for (i = 0; i < MAX_VECTOR_LENGTH; i++)
chromossome[i] = 0;
while (next_assignment(chromossome)) {
..do something..
}

/* Increments the values in chromossome to the next logical
value. Returns true if successful, false if all possible
assignments have been exhausted. */
static int
next_assignment(int chromossome[MAX_VECTOR_LENGTH])
{
int i;
for (i = 0; i < MAX_VECTOR_LENGTH; i++) {
if (++chromossome[i] < max_value_for_each_chromossome[i])
return true;
chromossome[i] = 0;
}
return false;
}

Also, you misspelled "chromosome".
--
char a[]="\n .CJacehknorstu";int putchar(int);int main(void){unsigned long b[]
={0x67dffdff,0x9aa9aa6a,0xa77ffda9,0x7da6aa6a,0xa6 7f6aaa,0xaa9aa9f6,0x11f6},*p
=b,i=24;for(;p+=!*p;*p/=4)switch(0[p]&3)case 0:{return 0;for(p--;i--;i--)case+
2:{i++;if(i)break;else default:continue;if(0)case 1utchar(a[i&15]);break;}}}

wrote:

> Hello,
>
> I am trying to find out an alternate way to brute-force a variable
> length vector with different variable length contents.
>
>
> int chromossome[MAX_VECTOR_LENGTH]
>
> int max_value_for_each_chromossome[MAX_VALUES]
>
>
> The only way I am aware of is to build 'n' for(; statements, one
> inside the other, but I would then need 1.000 (MAX_VECTOR_LENGTH)
> for(; inside for(;.
>
> One key issue is that each chromossome member has different max-
> elements, for example:
>
> chromossome[0] may have max_value_for_each_chromossome[0] = 5
> (chromossome[0] int will range from 0 to 4)

Okay. chromossome[n] is an int which can hold all values from INT_MIN to
INT_MAX. So unless a max_value_for_each_chromossome[n] is likely to be
beyond these bounds then you can safely use chromossome[n].

> chromossome[1] may have max_value_for_each_chromossome[1] = 2
> (chromossome[1] int will range from 0 to 1)
> ...
>
> Is there a simpler way to achive this rather than the for(; inside
> for(; scheme?

It's not entirely clear what you want to do. Can you elaborate?

On 17 May 2008 at 14:40, wrote:
> I am trying to find out an alternate way to brute-force a variable
> length vector with different variable length contents.
>
> int chromossome[MAX_VECTOR_LENGTH]
> int max_value_for_each_chromossome[MAX_VALUES]
>
> The only way I am aware of is to build 'n' for(; statements, one
> inside the other, but I would then need 1.000 (MAX_VECTOR_LENGTH)
> for(; inside for(;.

If 1000 really is what you're looking at, then even if each
"chromossome" only takes values 0 or 1, your brute-forcing will still
be so far from finishing when oblivion takes the earth that you may as
well not bother.

> One key issue is that each chromossome member has different max-
> elements, for example:

That makes things awkward. If the max-elements is fixed, let's say you
have vectors with n components each taking values 0,...,k-1, then you can
use a single loop counter i from 0 to k^n-1. At each iteration of the
loop, regard i as an integer base k; treat the jth base-k-digit of i as
the value to assign to the jth component on that iteration.

With variable max-elements, I can't off-hand think of a better way than
doing this with k=max(max-elements) and putting tests into the loop to
ignore invalid assignments.

In article <e2a9c8ca-b18c-4484-a48e->
>The only way I am aware of is to build 'n' for(; statements, one
>inside the other ... One key issue is that each chromossome member
>has different max-elements ...
>
>chromossome[0] may have max_value_for_each_chromossome[0] = 5
>(chromossome[0] int will range from 0 to 4)
>
>chromossome[1] may have max_value_for_each_chromossome[1] = 2
>(chromossome[1] int will range from 0 to 1)
>...

As others have said, it is not entirely clear what you are really
trying to achieve here.

My best guess at what you actually want is what I like to call an
"odometer algorithm".

In an odometer, there are a series of wheels that count up from 0
to 9, and when one wheel clicks from 9 to 0, the "next-one-over"
wheel counts up. We can do this trivially for a fixed number of
digits (say, 3) that count 0-to-9 with:

for (a[0] = 0; a[0] < 10; a[0]++) {
for (a[1] = 0; a[1] < 10; a[1]++) {
for (a[2] = 0; a[2] < 10; a[2]++) {
... now the three digits are in a[0] a[1] a[2] ...
}
}
}

So far, everything is pretty obvious, but what if we want our
"odometer" to read, e.g.:

000, 001, 002,
010, 011, 012,
020, 021, 022,
030, 031, 032,
040, 041, 042,
100, 101, 102,
110, 111, 112,
...
940, 941, 942

That is, the last digit only counts 0..2 and the middle digit only
counts 0..5? Well, again, this is pretty obvious:

for (a[0] = 0; a[0] < 10; a[0]++) {
for (a[1] = 0; a[1] < 5; a[1]++) {
for (a[2] = 0; a[2] < 3; a[2]++) {
... now the three digits are in a[0] a[1] a[2] ...
}
}
}

What if the odometer does not have exactly *three* digits, but
rather some variable number of digits? (Let us call this n and
assume it is no more than MAX_N.)

Here is where we take advantage of the fact that the outermost loop
runs over a[0], the next loop runs over a[1], the next over a[2],
and so on. Then we simply start by zeroing-out the entire odometer
(let me write this as a general-purpose function):

/* we will see what these are for in a moment */
#define NO_OVERFLOW 0
#define OVERFLOW 1

void odo_init(int *odo, int n_digits) {
int i;
for (i = 0; i < n_digits; i++)
odo[i] = 0;
}

and then run a loop that repeats until our odometer "overflows"
(back to all-zeros if it is a traditional car-odometer):

int a[MAX_N];
... find n ...
assert(n <= MAX_N);
odo_init(a);
do {
... work with odometer in a ...
} while (odo_increment(a, n) == NO_OVERFLOW);

Now we need only write the "increment" function. If the odometer
were a traditional car odometer, with all the digits running from
0 to 9 inclusive, this would look like:

/*
* Increment an odometer by "clicking the digits". Return
* OVERFLOW if the odometer overflows, or NO_OVERFLOW if not.
*/
int odo_increment(int *odo, int n_digits) {
int i;

/*
* Click the right-most (least-significant) digit first,
* and stop (and return NO_OVERFLOW) as soon as we can
* increment a digit without having to reset it to 0.
* If we have to reset the digit to 0, do that and continue
* the loop to increment the next-more-significant digit.
*/
for (i = n_digits - 1; i >= 0; i--) {
if (odo[i] < 9) {
odo[i]++;
return NO_OVERFLOW;
}
odo[i] = 0;
}

/* If we got here, we cranked everything all the way to 0 again. */
return OVERFLOW;
}

It should be pretty obvious how to modify odo_increment() to take
a second array of "range for each odometer digit" -- which can of
course vary per "digit" -- instead of just assuming [0..9].

It should be equally obvious how to rearrange the "odometer digits"
if "rightmost-counts-fastest" is not what is desired. The key work
all happens in the odo_increment() function.

(Note that there are other ways to solve this problem. For the
most trivial cases -- an odometer that reads 000 to 999 for instance
-- we can just do:

for (i = 0; i < 1000; i++) {
a[0] = i / 100;
a[1] = (i / 10) % 10;
a[2] = (i / 100) % 10;
... a[] holds the three digits ...
}

and we can usually eliminate the array "a" entirely. But calling
it an "odometer" makes things much clearer, I think.)
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
email: gmail (figure it out) http://web.torek.net/torek/index.html

> It's not entirely clear what you want to do. Can you elaborate?- Hide quoted text -

Hi,

Thanks all for the replies. I think the best way is to show a numeric
example:

for a given max_chromosome = 3 (I will not need to go upto
MAX_VECTOR_LENGHT, which is 1000):

max_value_for_each_chromossome[0] = 2 (0, 1)
max_value_for_each_chromossome[1] = 1 (0)
max_value_for_each_chromossome[2] = 3 (0, 1 and 2)

I need to get the following sequence of valid cobinations:

0, 0, 0
0, 0, 1
0, 0, 2
1, 0, 0
1, 0, 1
1, 0, 2

In a 3-number combination is easy to build a 3-level for(;
statement, but this value can be upto a thousand (variable).

Thank you all for the help, I appreciate it.

Paulo

On May 18, 2:58*am, estan...@gmail.com wrote:
> > It's not entirely clear what you want to do. Can you elaborate?- Hide quoted text -
>
> Hi,
>
> Thanks all for the replies. I think the best way is to show a numeric
> example:
>
> for a given max_chromosome = 3 (I will not need to go upto
> MAX_VECTOR_LENGHT, which is 1000):
>
> max_value_for_each_chromossome[0] = 2 (0, 1)
> max_value_for_each_chromossome[1] = 1 (0)
> max_value_for_each_chromossome[2] = 3 (0, 1 and 2)
>
> I need to get the following sequence of valid cobinations:
>
> 0, 0, 0
> 0, 0, 1
> 0, 0, 2
> 1, 0, 0
> 1, 0, 1
> 1, 0, 2
>
> In a 3-number combination is easy to build a 3-level for(;
> statement, but this value can be upto a thousand (variable).

I used this code:

#include <stdio.h>
#include <stdlib.h>

#define n 3

int main(void) {

int a[n] = {2,1,3};
int b[n] = {0,0,0};
int i,j,k;

while(1) {

for (i=0; i<n; ++i) printf(" %d",b[i]); puts("");

j=n-1;

while(1) {
++b[j];
if (b[j]==a[j]) {
b[j]=0;
if (j==0) exit(0);
--j;
}
else
break;
};
};

}

Array a corresponds to your max_value vector. Array b is an auxilliary
counting vector.

Probably other replies have suggested similar.

Note that for bigger values of n, and larger values in your max_value
vector (a above) the task may take a long time to finish. As has also
been noted.

--
Bartc

On May 17, 6:59 pm, Chris Torek <nos...@torek.net> wrote:
> What if the odometer does not have exactly *three* digits, but
> rather some variable number of digits? (Let us call this n and
> assume it is no more than MAX_N.)

This is the case.

> It should be pretty obvious how to modify odo_increment() to take
> a second array of "range for each odometer digit" -- which can of
> course vary per "digit" -- instead of just assuming [0..9].

Not for me ...

> -- we can just do:
>
> for (i = 0; i < 1000; i++) {
> a[0] = i / 100;
> a[1] = (i / 10) % 10;
> a[2] = (i / 100) % 10;
> ... a[] holds the three digits ...
> }

If I understood you correclty, I will only one nested for(;. I still
have to think and read your explanation a few more times to see if I
can adapt your idea to my code.

Thank you

Paulo