Creating an logical combination brute-forcing routine ?? 
Author Message
 Creating an logical combination brute-forcing routine ??

Problem: How to create an pseudo-brute-forcing routine that tries most of the
combinations required??

I believe this problem comes up a lot among programmers, so that perhaps
someone already has a solution....

The problem is that I need to create an effective way of going throught most
combinations of a given set of numbers.
{example}
- The set of numbers (in an array): 1, 4, 3, 9.
- Target number: 15
- Max amount of elements in solution: 4

The routine needs to be capable of doing the things below:

- Given a certain set of numbers the routine should be able to go throught all
the possible combinations.
- If the routine finds that one combination equals the target number it should
return True, otherwise False.

{example solution}
- True: the combination 1+4+9+1 = 15 (and doesnt use more than 4 elements in
the solution).

If you think you have a solution, even if it is plain english (or pseudocode),
please reply.



Sat, 01 May 2004 04:03:57 GMT  
 Creating an logical combination brute-forcing routine ??

Quote:

>The problem is that I need to create an effective way of going throught most
>combinations of a given set of numbers.
>{example}
>- The set of numbers (in an array): 1, 4, 3, 9.
>- Target number: 15
>- Max amount of elements in solution: 4

>The routine needs to be capable of doing the things below:

>- Given a certain set of numbers the routine should be able to go throught all
>the possible combinations.
>- If the routine finds that one combination equals the target number it should
>return True, otherwise False.

>{example solution}
>- True: the combination 1+4+9+1 = 15 (and doesnt use more than 4 elements in
>the solution).

>If you think you have a solution, even if it is plain english (or pseudocode),
>please reply.

The biggest part of this problem is finding a coding for the probable
solutions. E.g. if your input array contains 5 inputs, you could
represent any solution to the problem as a string of 4 digits, each of
which is 0-5. E.g.

1111

would represent 1+1+1+1

1234

would represent 1+4+3+9

0123

would represent 1+2+3 (interpret 0 as a null value - allowing you to
express solutions with fewer than four values).

Now to brute force your solution, you just have to examine each number
from 0000 to  5555 (base 6). Does that number result in a solution of
15? Then stop. Otherwise, continue.

Of course, a coding like this could be used for other kinds of search
for the solution - a genetic algorithm for example.

Gareth



Sat, 01 May 2004 05:04:37 GMT  
 Creating an logical combination brute-forcing routine ??


12 Nov 2001 20:03:57 :-

Quote:
>Problem: How to create an pseudo-brute-forcing routine that tries most of the
>combinations required??

>I believe this problem comes up a lot among programmers, so that perhaps
>someone already has a solution....

>The problem is that I need to create an effective way of going throught most
>combinations of a given set of numbers.
>{example}
>- The set of numbers (in an array): 1, 4, 3, 9.
>- Target number: 15
>- Max amount of elements in solution: 4

Your problem is a modified subset of <URL: http://www.merlyn.demon.co.uk
/programs/countdwn.pas>, which is a Vorderman emulator.

--

 Web <URL: http://www.merlyn.demon.co.uk/> - FAQqish topics, acronyms & links.
 PAS, EXE in <URL: http://www.merlyn.demon.co.uk/programs/> - see 00index.txt.
 My DOS <URL: http://www.merlyn.demon.co.uk/batfiles.htm> - also batprogs.htm.



Sun, 02 May 2004 02:04:51 GMT  
 Creating an logical combination brute-forcing routine ??
Gareth - That was an accurate and useful solution.

Coding it was ok - but my input array has a top of 30 so I had to use
characters to represent the values. That was not a problem, since Char(x)
returns the number coded and Ord(x) returns the integer value back.

The only problem with arraysize 30 is that there are
30^30 different combinations = 2.05891132094649e+44 (as Windows calculated it).

But after I optimized the code the program produces the correct output in a
less than <1 ms (for the test inputs [that are rather small]).

John Stockton - A useful remark.

Ill check the code out and optimize my code further...

BOTH - Thank you very much!!



Sun, 02 May 2004 06:19:15 GMT  
 Creating an logical combination brute-forcing routine ??

Quote:

>Gareth - That was an accurate and useful solution.

>Coding it was ok - but my input array has a top of 30 so I had to use
>characters to represent the values. That was not a problem, since Char(x)
>returns the number coded and Ord(x) returns the integer value back.

Yes, that's a nice way of doing it. Alternatively you could have used
an array of integers (one array element per "digit" of the coding) to
represent each potential solution.

Quote:
>The only problem with arraysize 30 is that there are
>30^30 different combinations = 2.05891132094649e+44 (as Windows calculated it).

ouch.

Quote:
>But after I optimized the code the program produces the correct output in a
>less than <1 ms (for the test inputs [that are rather small]).

>John Stockton - A useful remark.

>Ill check the code out and optimize my code further...

Bear in mind that if your solution space is very big, optimising might
not help much. For example, if you find that a brute force attack on
yoru solution space would take a thousand years, then even if you
optimised your program so that it ran 100 times faster, you would not
really be happy with the result :-). At this point, you have to look
for a faster algorithm (as opposed to a faster implementation of the
brute force algorithm - which is the slowest way of looking for any
solution).

Quote:
>BOTH - Thank you very much!!

No problem.

Gareth



Sun, 02 May 2004 07:39:18 GMT  
 
 [ 5 post ] 

 Relevant Pages 

1. Must it be "Brute Force"?

2. Creating an AutoInc but forcing it to start from a 10000

3. Creating logical palettes...

4. Creating a logical palette

5. Creating JPEG routines

6. Creating JPEG routines

7. DataSource and Standard ComboBox: Strange Combination.

8. DatBase combination

9. Problems with Apollo 2.11 in combination with Advantage DB Server

10. Keys, Combinations, Diffrences between Dos and Linux.

11. all possible combinations

12. all possible combinations

 

 
Powered by phpBB® Forum Software