Qbasicnews.com
November 19, 2019, 01:17:43 PM *
Welcome, Guest. Please login or register.

Login with username, password and session length
News: Back to Qbasicnews.com | QB Online Help | FAQ | Chat | All Basic Code | QB Knowledge Base
 
   Home   Help Search Login Register  
Pages: [1]
  Print  
Author Topic: Combinatorics Algorithm  (Read 5832 times)
Agamemnus
x/ \z
*****
Posts: 3491



« on: December 21, 2003, 01:00:30 PM »

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

Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war."

Visit www.neobasic.net to see rubbish in all its finest.
Meg
Ancient QBer
****
Posts: 483


« Reply #1 on: December 21, 2003, 07:28:20 PM »

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 Wink
Logged
Agamemnus
x/ \z
*****
Posts: 3491



« Reply #2 on: December 21, 2003, 10:21:27 PM »

heh. Good question.

Just any equivalent answer will do.

You could just display all equivalent answers. That would be even cooler.
Logged

Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war."

Visit www.neobasic.net to see rubbish in all its finest.
Agamemnus
x/ \z
*****
Posts: 3491



« Reply #3 on: December 28, 2003, 08:25:37 PM »

*swats the flies and gets rid of the giant dust balls*
Logged

Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war."

Visit www.neobasic.net to see rubbish in all its finest.
Rhiannon
Been there, done that
*****
Posts: 1031



WWW
« Reply #4 on: December 28, 2003, 08:48:24 PM »

Quote from: "Agamemnus"
*swats the flies and gets rid of the giant dust balls*


Need some help there? I've got a vacuum Wink
Logged

igitalblackie.com - Done! Smiley Ask about our hosting Wink

-Goddess of the of the No More Religion Threads movement Smiley
Neo
Na_th_an
*****
Posts: 2150



« Reply #5 on: December 29, 2003, 09:42:54 AM »

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 Wink
Logged
Agamemnus
x/ \z
*****
Posts: 3491



« Reply #6 on: December 30, 2003, 05:07:29 PM »

I don't get it.
Logged

Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war."

Visit www.neobasic.net to see rubbish in all its finest.
Neo
Na_th_an
*****
Posts: 2150



« Reply #7 on: December 31, 2003, 10:42:33 AM »

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. Smiley
Logged
Agamemnus
x/ \z
*****
Posts: 3491



« Reply #8 on: December 31, 2003, 03:09:16 PM »

How would it work with this:

100 500
200 100 195 15

?
Logged

Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war."

Visit www.neobasic.net to see rubbish in all its finest.
SCM
Wandering Guru
***
Posts: 311



« Reply #9 on: January 01, 2004, 10:54:02 PM »

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);
  IF j <= Adds0 THEN
    Sum(0) = Sum(0) + Choices(j)
    IF j < Adds0 THEN
      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)
  DIM Adds(n)
  Errr = 10000
  j = n
  DO
    IF Total <= Sum THEN
      IF Sum - Total < Errr THEN
        Errr = Sum - Total
        Addends(0) = j
        FOR i = 1 TO j
          Addends(i) = Chcs(i)
        NEXT
      END IF
      EXIT SUB
    ELSE
      Total = Total - Chcs(j)
      IF Chcs(j) < Sum THEN
        FindAddends Chcs(), j - 1, Total, Sum - Chcs(j), Adds(), NewEr
        IF Sum - Chcs(j) < NewEr THEN
          IF Sum - Chcs(j) < Errr THEN
            Addends(0) = 1
            Addends(1) = Chcs(j)
            Errr = Sum - Chcs(j)
          END IF
        ELSEIF NewEr < Errr THEN
          Errr = NewEr
          Addends(0) = Adds(0) + 1
          FOR i = 1 TO Adds(0)
            Addends(i) = Adds(i)
          NEXT
          Addends(Addends(0)) = Chcs(j)
          IF NewEr = 0 THEN EXIT SUB
        END IF
      ELSE
        IF Chcs(j) - Sum < Errr THEN
          Errr = Chcs(j) - Sum
          Addends(0) = 1
          Addends(1) = Chcs(j)
        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)
  DIM Addends(n), Total AS LONG
  Sort Choices(), n
  Smaller = -(Sum(1) < Sum(0))
  Total = Sum(0) + Sum(1)
  FindAddends Choices(), n, Total, Sum(Smaller), Addends(), Errr

  CIndex = 1
  GIndex = 0

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

  FOR j = 1 TO Addends(0)
    WHILE Addends(j) > Choices(CIndex)
      GIndex = GIndex + 1
      Groups(1 - Smaller, GIndex) = Choices(CIndex)
      CIndex = CIndex + 1
    WEND
    Groups(Smaller, j) = Addends(j)
    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
Logged

hrist Jesus came into the world to save sinners, of whom I am first.(I Timothy 1:15)

For God so loved the world, that He gave His only begotten Son,
that whoever believes in Him should not perish, but have eternal life.(John 3:16)
Agamemnus
x/ \z
*****
Posts: 3491



« Reply #10 on: January 02, 2004, 11:29:51 AM »

I see. I tested it. Good work.

BTW,
The reason I came up with this challenge is because I was trying to split up 1300 megabytes or so to make them fit on two CDs.. took me a bit of time to come up with the right files for each CD..

PS:
"byval" in a QB sub prolly works in 7.1, but I'm not sure if it works in 4.5. I got rid of the BYVALs (because I couldn't start the program with 'em) and put in each sub call the Total variable in parentheses, which accomplishes the same thing.
Logged

Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war."

Visit www.neobasic.net to see rubbish in all its finest.
qbiscool
Member
*
Posts: 56


« Reply #11 on: March 09, 2004, 12:39:28 AM »

Quote
PS:
"byval" in a QB sub prolly works in 7.1, but I'm not sure if it works in 4.5. I got rid of the BYVALs (because I couldn't start the program with 'em) and put in each sub call the Total variable in parentheses, which accomplishes the same thing.


Just wondering, what does byval do anyways.
Logged

pen your other eyes.........
na_th_an
*/-\*
*****
Posts: 8244



WWW
« Reply #12 on: March 09, 2004, 06:39:35 AM »

Quote from: "qbiscool"
Just wondering, what does byval do anyways.


Explained in QB help.

Code:
BYVAL Clause
 
Syntax
  BYVAL variable [AS type]
 
The BYVAL attribute in the parameter list of a DECLARE statement causes
the value of the specified variable to be passed to the procedure, rather
than the variable's address. BYVAL can only be used in DECLARE statements
for non-BASIC procedures, and cannot be applied to string parameters.
Logged

SCUMM (the band) on Myspace!
ComputerEmuzone Games Studio
underBASIC, homegrown musicians
[img]http://www.ojodepez-fanzine.net/almacen/yoghourtslover.png[/i
SCM
Wandering Guru
***
Posts: 311



« Reply #13 on: March 26, 2004, 12:05:51 AM »

I realize that this is old, but I have been busy for a while.

In 7.1 BYVAL can be used by BASIC as well as non-BASIC procedures.  It has two advantages:

1) Since it only passes the value, The variable in the calling procedure isn't changed.


2) Variables in the calling and called procedure don't have to be the same type.  This saves having to rewrite procedures for different variable types.
Logged

hrist Jesus came into the world to save sinners, of whom I am first.(I Timothy 1:15)

For God so loved the world, that He gave His only begotten Son,
that whoever believes in Him should not perish, but have eternal life.(John 3:16)
Agamemnus
x/ \z
*****
Posts: 3491



« Reply #14 on: March 27, 2004, 04:23:00 PM »

Oh great...

Another reason to use qb7.1...  :evil: [/i]
Logged

Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war."

Visit www.neobasic.net to see rubbish in all its finest.
Pages: [1]
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.21 | SMF © 2015, Simple Machines Valid XHTML 1.0! Valid CSS!