algorithm for brute force an variable lenght array

**pete** · Jun 27 '08, 07:37 PM

Re: algorithm for brute force an variable lenght array

estantep@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_LENG TH]
>
int max_value_for_e ach_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_LEN GTH)
for(;;) inside for(;;).
>
One key issue is that each chromossome member has different max-
elements, for example:
>
chromossome[0] may have max_value_for_e ach_chromossome[0] = 5
(chromossome[0] int will range from 0 to 4)
>
chromossome[1] may have max_value_for_e ach_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?

I don't understand what you're trying to achieve.

--
pete

**Bart** · Jun 27 '08, 07:37 PM

Re: algorithm for brute force an variable lenght array

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_LENG TH]
>
int max_value_for_e ach_chromossome[MAX_VALUES]

So which of these is variable length? Or do you have a set of
MAX_VECTOR_LENG TH 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_LEN GTH)
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_e ach_chromossome[0] = 5
(chromossome[0] int will range from 0 to 4)
>
chromossome[1] may have max_value_for_e ach_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** · Jun 27 '08, 07:37 PM

Re: algorithm for brute force an variable lenght array

estantep@gmail. com writes:

int chromossome[MAX_VECTOR_LENG TH]
>
int max_value_for_e ach_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_LEN GTH)
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_LENG TH; i++)
chromossome[i] = 0;
while (next_assignmen t(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_LENG TH])
{
int i;
for (i = 0; i < MAX_VECTOR_LENG TH; i++) {
if (++chromossome[i] < max_value_for_e ach_chromossome[i])
return true;
chromossome[i] = 0;
}
return false;
}

Also, you misspelled "chromosome ".
--
char a[]="\n .CJacehknorstu" ;int putchar(int);in t main(void){unsi gned long b[]
={0x67dffdff,0x 9aa9aa6a,0xa77f fda9,0x7da6aa6a ,0xa67f6aaa,0xa a9aa9f6,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)bre ak;else default:continu e;if(0)case 1:putchar(a[i&15]);break;}}}

**santosh** · Jun 27 '08, 07:37 PM

Re: algorithm for brute force an variable lenght array

estantep@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_LENG TH]
>
int max_value_for_e ach_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_LEN GTH)
for(;;) inside for(;;).
>
One key issue is that each chromossome member has different max-
elements, for example:
>
chromossome[0] may have max_value_for_e ach_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_e ach_chromossome[n] is likely to be
beyond these bounds then you can safely use chromossome[n].

chromossome[1] may have max_value_for_e ach_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?

**Malcolm McLean** · Jun 27 '08, 07:37 PM

Re: algorithm for brute force an variable lenght array

<estantep@gmail .comwrote in message

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_LEN GTH)
for(;;) inside for(;;).
>

I somehow doubt you need a N^N algorithm. N^2, or two nested fors, is quite
common.

--
Free games and programming goodies.

http://www.personal.leeds.ac.uk/~bgy1mm

**Antoninus Twink** · Jun 27 '08, 07:37 PM

Re: algorithm for brute force an variable lenght array

On 17 May 2008 at 14:40, estantep@gmail. com 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_LENG TH]
int max_value_for_e ach_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_LEN GTH)
for(;;) inside for(;;).

If 1000 really is what you're looking at, then even if each
"chromossom e" 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** · Jun 27 '08, 07:37 PM

Re: algorithm for brute force an variable lenght array

In article <e2a9c8ca-b18c-4484-a48e-549dc03f0352@w7 g2000hsa.google groups.com>

>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_e ach_chromossome[0] = 5
>(chromossome[0] int will range from 0 to 4)
>
>chromossome[1] may have max_value_for_e ach_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(i nt *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** · Jun 27 '08, 07:37 PM

Re: algorithm for brute force an variable lenght array

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_LENG HT, which is 1000):

max_value_for_e ach_chromossome[0] = 2 (0, 1)
max_value_for_e ach_chromossome[1] = 1 (0)
max_value_for_e ach_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** · Jun 27 '08, 07:37 PM

Re: algorithm for brute force an variable lenght array

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_LENG HT, which is 1000):
>
max_value_for_e ach_chromossome[0] = 2 (0, 1)
max_value_for_e ach_chromossome[1] = 1 (0)
max_value_for_e ach_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** · Jun 27 '08, 07:37 PM

Re: algorithm for brute force an variable lenght array

On May 17, 6:59 pm, Chris Torek <nos...@torek.n etwrote:

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

**Malcolm McLean** · Jun 27 '08, 07:37 PM

Re: algorithm for brute force an variable lenght array

<estantep@gmail .comwrote in message

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

Do you think maybe Chris Torek can read minds?

The odometer is a bit fiddly to code, but if you say

/*
advance odometer 1 step
Params: numvals - number of values in each wheel
Nvals - number of wheels
vals - current wheel positions
Returns: 0 if running, 1 if clocked over
*/
int tick(const int *numvals, int Nvals, int *vals)
{
int i = Nvals - 1;

while(i >= 0)
{
vals[i]++;
if(vals[i] < maxvals[i])
return 0;
vals[i] = 0;
i--;
}
return 1;
}

Remember that a thousand wheels is too many. Assming two values per wheel,
the program will start to run into severe time difficulties at about Nvals =
32.

--
Free games and programming goodies.

http://www.personal.leeds.ac.uk/~bgy1mm

algorithm for brute force an variable lenght array

algorithm for brute force an variable lenght array

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment