algorithm for brute force an variable lenght array

E

estantep

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
 
B

Bart

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.
 
B

Ben Pfaff

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 = 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 < max_value_for_each_chromossome)
return true;
chromossome = 0;
}
return false;
}

Also, you misspelled "chromosome".
 
S

santosh

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?
 
A

Antoninus Twink

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.
 
C

Chris Torek

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 = 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 < 9) {
odo++;
return NO_OVERFLOW;
}
odo = 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.)
 
E

estantep

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
 
B

Bart

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); 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.
 
E

estantep

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
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,780
Messages
2,569,608
Members
45,250
Latest member
Charlesreero

Latest Threads

Top