algorithm for brute force an variable lenght array

Discussion in 'C Programming' started by estantep@gmail.com, May 17, 2008.

  1. Guest

    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
     
    , May 17, 2008
    #1
    1. Advertising

  2. Bart Guest

    On May 17, 3:40 pm, 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
     
    Bart, May 17, 2008
    #2
    1. Advertising

  3. Ben Pfaff Guest

    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 = 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".
    --
    char a[]="\n .CJacehknorstu";int putchar(int);int main(void){unsigned long b[]
    ={0x67dffdff,0x9aa9aa6a,0xa77ffda9,0x7da6aa6a,0xa67f6aaa,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 1:putchar(a[i&15]);break;}}}
     
    Ben Pfaff, May 17, 2008
    #3
  4. santosh Guest

    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?
     
    santosh, May 17, 2008
    #4
  5. 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.
     
    Antoninus Twink, May 17, 2008
    #5
  6. Chris Torek Guest

    In article <>
    >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.)
    --
    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
     
    Chris Torek, May 17, 2008
    #6
  7. Guest

    > 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
     
    , May 18, 2008
    #7
  8. Bart Guest

    On May 18, 2:58 am, 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); 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
     
    Bart, May 18, 2008
    #8
  9. Guest

    On May 17, 6:59 pm, Chris Torek <> 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
     
    , May 18, 2008
    #9
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. John Apps
    Replies:
    3
    Views:
    7,838
    Alvin Bruney [MVP - ASP.NET]
    May 26, 2005
  2. David List

    Re: brute force

    David List, Aug 22, 2003, in forum: C++
    Replies:
    4
    Views:
    609
    Karl Heinz Buchegger
    Aug 22, 2003
  3. Stuart Golodetz

    Re: brute force

    Stuart Golodetz, Aug 22, 2003, in forum: C++
    Replies:
    2
    Views:
    492
    Stuart Golodetz
    Aug 23, 2003
  4. Bas

    Brute force sudoku cracker

    Bas, Sep 16, 2005, in forum: Python
    Replies:
    21
    Views:
    3,223
    Dennis Lee Bieber
    Sep 23, 2005
  5. Susanne

    Brute-Force-like array

    Susanne, Jul 29, 2004, in forum: Perl Misc
    Replies:
    6
    Views:
    162
    Anno Siegel
    Jul 30, 2004
Loading...

Share This Page