Calculation

[Dinosaur]

Hi all,

I need help in doing a rather unusual calculation.
We have a total of 16 integers
I need to calculate all possible combinations of these 16 numbers.
But no more then 6 are added at any time.
Currently doing it long hand in asm, but need to find a new way
so that I can convert it to asm after testing in basic.
Current Algorithm, the numbers represent the 16 integers.
1+2
1+2+3
1+2+3+4
1+2+3+4+5
1+2+3+4+5+6 no more then 6 numbers
easy so far, then drop nbr 6
1+2+3+4+5+7
1+2+3+4+5+8
etc until 16, then
1+2+3+4+
It gets that complicated, that I have forgotten how it continues.

Any math gurus that shed light on doing that in an indexing loop ?

Regards

[Meg]

This will find all combinations of length Markers in a list Numbers numbers long. If you wanted all combinations of length 1, 2, 3, 4, 5, OR 6, then you could run this whole piece of code 6 times, changing the value of Markers each time.

Let me know if this helps.

*peace*

Meg.

[syntax="qbasic"]'THIS PROGRAM PRINTS OUT ALL COMBINATIONS OF AMOUNT markers FROM A LIST OF
'NUMBERS numbers LONG.
' - Written 12/15/2004 by mb

CLS

'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
'Numbers is the amount of numbers in the list. Markers is the maximum amount
'of them to sum up for a combination. In your problem, Markers = 6 and
'Numbers = 16
'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
CONST Numbers = 16
CONST Markers = 6

'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
'make a list of numbers from data statement
'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
DIM n(1 TO Numbers) AS INTEGER
FOR i% = 1 TO Numbers
READ n(i%)
NEXT i%

'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
'set initial markers flush left
'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
DIM m(1 TO Markers) AS INTEGER
FOR i% = 1 TO Markers
m(i%) = Markers + 1 - i%
NEXT i%

DO
'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
'locate the right-most marker (Free%) with room to move
'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
Free% = 0
FOR i% = 1 TO Markers
IF m(i%) < Numbers + 1 - i% THEN
Free% = i%
EXIT FOR
END IF
NEXT i%

IF Free% = 0 THEN
'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
'the markers are now flush right. all combinations have been found
'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
EXIT DO
ELSE
'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
'advance the free marker
'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
m(Free%) = m(Free%) + 1

'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
'flush all markers to the right of free back to the left
'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
FOR i% = Free% - 1 TO 1 STEP -1
m(i%) = m(Free%) + Free% - i%
NEXT i%

'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
'print the new combination
'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
FOR i% = Markers TO 1 STEP -1
PRINT m(i%); " ";
NEXT i%
PRINT

'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
'wait for keypress
'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
DO: LOOP UNTIL INKEY$ <> ""
END IF
LOOP

SYSTEM

'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
'our list of numbers
'@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
DATA 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16
[/syntax]

[Antoni Gual]

A recursive version :evil:

Code:

DECLARE SUB PRINTSUM (S%, I%, N%)
DEFINT A-Z
CONST AMOUNT = 16
DIM SHARED A(1 TO AMOUNT)
FOR I = 1 TO AMOUNT
  READ A(I)
NEXT
DATA 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16
CLS
'change only the lat parameter, (the number of terms)
PRINTSUM 0, 1, 6
END

SUB PRINTSUM (S, I, N)
  IF N = 0 THEN PRINT S, : EXIT SUB

  FOR J = I TO AMOUNT
    PRINTSUM S + A(J), J + 1, N - 1
  NEXT
END SUB

[Dinosaur]

Thanks for both of those methods.
Will test and see and update you guys.

Regards

[Meg]

Antoni: AWESOME. I tried for like two hours to figure out how to do this via recursion, but kept stumbling over myself. I'm glad a recursive solution was posted.

[Diroga]

cant you do calculate it with combination/permuation?

[Dinosaur]

Diroga

I am away bush for a few days so on borrowed dial up.
Can you give me an example of what you mean, say with a couple
of numbers.

I am still evaluating the responses I have had.

Regards

[Dinosaur]

Hi all

Just an update for those whom have contributed to my request.
No problem understanding Meg's way of handling it.
No chance of understanding the recursive routine of Antoni.
I have never ventured into recursive routines.
But having said that, if my wording was placed into the variables
then I would work it out.
Even though I have opted for a different method
(how can i say that if I dont understand one of them ??) I would
still love to hear an explanation for Antoni's..

The solution contributed by an asm forum suited, as the 16 numbers
are not all available at the same time, and works something like:

1. Place first value in location 1 of memory
2. Add second value to first value and place result in loc 2
3. Place second value alone in the 3rd location.
4. Add third value to each of the previous entries and place in
next free location, once again placing third value alone in next
free location.
do this for 16 values as they become available.
But whilst doing the adding I can check for valid combinations
and send them back to basic.

Uses huge amount of memory, but as I am using this in Dos with
"Unreal" Flat memory, I can address up to 10GigaByte of Ram.

I have timed it by running the 16 values 100 times, and takes
about 3msec.

Once again many thanks to the contributor's

Regards
Dinosaur