# Qbasicnews.com

Full Version: Combinatorics Algorithm
You're currently viewing a stripped down version of our content. View the full version with proper formatting.
Pages: 1 2
Make an algorithm that, given a bunch of (n) random INTEGERs and two inputted (sp??) LONGs, where the sum of the LONGs equals the sum of the integers,

finds the combination of INTEGERs for each LONG that most closely approximate (or exactly equal) the LONG's individual values.

Example:

INTEGERS: 5 4 2 3 = 14
LONGs: 6 8

Solution:
4 2, 5 3

Most efficient (or, the one that actually works, if there is only one that works..) algorithm wins...
let's say the two longs = 10, 8
and the integers are 7, 2, and 9

both sets sum 18

would you want the program to say "7+2, 9" or "9+2, 7"? Both return answers (9, 9) or (11, 7) that are one away from correct.

*peace*

Meg.

p.s. cool challenge
heh. Good question.

Just any equivalent answer will do.

You could just display all equivalent answers. That would be even cooler.
*swats the flies and gets rid of the giant dust balls*
Quote:*swats the flies and gets rid of the giant dust balls*

Need some help there? I've got a vacuum
Aga, I had such a question on a programming tournament (olympiad) once, and the answer is just like:

Code:
[pseudocode]
do
do
give highest number from the stack
loop all groups
do
give lowest number from the stack
loop all groups
loop all available 'stack-numbers'
[/pseudocode]

I got many points on that question
I don't get it.
First you divide all highest numbers to all groups, then you divide all lowest numbers to each group. That should give a good answer. This is a global algorithm, there could be better answers, but take a look:

LONGs: 8, 6
INTs: 5, 4, 3, 2

My algo: 5 + 2 = 7 and 4 + 3 = 7
One-of-a-time algo: 5 + 3 = 8, 4 + 2 = 6

But take a look: average of my algo is 7, the one of a time algo is 7 as well.
How would it work with this:

100 500
200 100 195 15

?
This is my shot at it. It's probably not optimized, but it seems to work. My strategy is to only try to fit the smaller of the two longs, and I start with the biggest integers first.

If you want to try it with your own numbers, call GroupAddends with the longs in SUM(), the integers in Choices() (starting with Choices(1)), and the number of integers in n. The output is in Groups(), with the number of integers for the jth long in Groups(j, 0), and the integers starting from Groups(j, 1).

Code:
DEFINT A-Z

DECLARE SUB Sort (Array%(), n%)
DECLARE SUB GroupAddends (Sum() AS LONG, Choices%(), n%, Groups%(), Errr%)
DECLARE SUB FindAddends (Chcs%(), n%, BYVAL Total AS LONG, Sum AS LONG, Addends%(), Errr%)

DIM Sum(1) AS LONG, Total AS LONG

n = 14
DIM Choices(n), Groups(1, n)

CLS
RANDOMIZE TIMER

'------------- Generate & Display Numbers -----------------
Adds0 = INT(RND * (n - 1) + 1)

FOR j = 1 TO n
Choices(j) = INT(RND * 1000 + .5)
PRINT Choices(j);
Sum(0) = Sum(0) + Choices(j)
PRINT "+";
ELSE
PRINT "="; Sum(0)
END IF
ELSE
Sum(1) = Sum(1) + Choices(j)
IF j < n THEN
PRINT "+";
ELSE
PRINT "="; Sum(1)
END IF
END IF
NEXT
PRINT
'------------ End of Genrate & Display Numbers ------------

GroupAddends Sum(), Choices(), n, Groups(), Errr

'-------------------  Display Results  --------------------
FOR i = 0 TO 1
Total = 0
FOR j = 1 TO Groups(i, 0) - 1
Total = Total + Groups(i, j)
PRINT Groups(i, j); "+";
NEXT
Total = Total + Groups(i, j)
PRINT Groups(i, j); "="; Total
NEXT
PRINT "Error ="; Errr
'-------------------- End of Display results --------------

SUB FindAddends (Chcs(), n, BYVAL Total AS LONG, Sum AS LONG, Addends(), Errr)
Errr = 10000
j = n
DO
IF Total <= Sum THEN
IF Sum - Total < Errr THEN
Errr = Sum - Total
FOR i = 1 TO j
NEXT
END IF
EXIT SUB
ELSE
Total = Total - Chcs(j)
IF Chcs(j) < Sum THEN
IF Sum - Chcs(j) < NewEr THEN
IF Sum - Chcs(j) < Errr THEN
Errr = Sum - Chcs(j)
END IF
FOR i = 1 TO Adds(0)
NEXT
IF NewEr = 0 THEN EXIT SUB
END IF
ELSE
IF Chcs(j) - Sum < Errr THEN
Errr = Chcs(j) - Sum
END IF
IF Chcs(j) = Sum THEN EXIT SUB
END IF
END IF
j = j - 1
LOOP WHILE j > 0
END SUB

SUB GroupAddends (Sum() AS LONG, Choices(), n, Groups(), Errr)
Sort Choices(), n
Smaller = -(Sum(1) < Sum(0))
Total = Sum(0) + Sum(1)

CIndex = 1
GIndex = 0

Groups(1 - Smaller, 0) = n - Addends(0)

FOR j = 1 TO Addends(0)
GIndex = GIndex + 1
Groups(1 - Smaller, GIndex) = Choices(CIndex)
CIndex = CIndex + 1
WEND
CIndex = CIndex + 1
NEXT

IF CIndex <= n THEN
FOR j = CIndex TO n
GIndex = GIndex + 1
Groups(1 - Smaller, GIndex) = Choices(j)
NEXT
END IF
END SUB

SUB Sort (Array(), n)
DO
Changes = 0
FOR j = 0 TO n - 1
IF Array(j) > Array(j + 1) THEN
SWAP Array(j), Array(j + 1)
Changes = Changes + 1
END IF
NEXT
LOOP WHILE Changes > 0
END SUB
Pages: 1 2