Velocity Reviews > algorithm for brute force an variable lenght array

# algorithm for brute force an variable lenght array

estantep@gmail.com
Guest
Posts: n/a

 05-17-2008
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

Bart
Guest
Posts: n/a

 05-17-2008
On May 17, 3:40*pm, (E-Mail Removed) 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

Ben Pfaff
Guest
Posts: n/a

 05-17-2008
http://www.velocityreviews.com/forums/(E-Mail Removed) 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;}}}

santosh
Guest
Posts: n/a

 05-17-2008
(E-Mail Removed) 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?

Antoninus Twink
Guest
Posts: n/a

 05-17-2008
On 17 May 2008 at 14:40, (E-Mail Removed) 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.

Chris Torek
Guest
Posts: n/a

 05-17-2008
In article <(E-Mail Removed)>
>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

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

estantep@gmail.com
Guest
Posts: n/a

 05-18-2008
> 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

Bart
Guest
Posts: n/a

 05-18-2008
On May 18, 2:58*am, (E-Mail Removed) 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

estantep@gmail.com
Guest
Posts: n/a

 05-18-2008
On May 17, 6:59 pm, Chris Torek <(E-Mail Removed)> 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

Thank you

Paulo