[Excel] Combinations again - what macro will find them all?

[rp-usa]

I'd like to have a column of data (integers from 1-88) that is of variable length x (could be 1 to 20 rows)

I would like to create (on a separate sheet, perhaps) a list of all the possible subsets ranging in size from 2 to (x-1), along with the sums for each set.

I know I could probably nest a bunch of loops and exit at some point, but I'm sure there is a MUCH better way to write a macro, maybe a recursive function of something. My problem is that I don't really know VB. So will anyone write that sub for me?

Thanks!

[GBeats]

I'd like to have a column of data (integers from 1-88) that is of variable length x (could be 1 to 20 rows)

I would like to create (on a separate sheet, perhaps) a list of all the possible subsets ranging in size from 2 to (x-1), along with the sums for each set.

you should clarify this a little.
a column with numbers 1 to 88 of variable length?!!
X
(could be)1 to 20 rows ?!! of unknown data?

and you want to sum the values of each cell with each other cell? or row?

[Ecniv]

Hi,

So will anyone write that sub for me?

Some one might... but the main use of this forum is to further your own knowledge by you writing it. When you get stuck you can get advice on how to proceed.


Question sounds like a school project....?



From what I gather... you have 1 column of data that ranges from 1 to 20 rows. This data is values of 1-88.

Not sure what you mean by subsets; do you mean all the possible totals? example minimum of 1 max of 20*88? or are you looking for numbers of re-occurances?

With only (max) 20 rows, a for...next loop is probably the best way to go...

[rp-usa]

It's not a school project, just a personal one. I would love to learn how to do this myself, but I just don't know where to start (other than building up to 20 nested loops, with some kind of exit based on the number of values I'm dealing with; that just seems pretty inefficient).

To clarify:
- there are 1-20 rows (only 1 column) of data
- each row (cell) has a value ranging from 1-88
- I would like to generate every possible subset

For example: if the data were 1 3 88, I would like the output to be:
1 (1)
3 (3)
88 (88)
4 (1+3)
89 (1+88)
91 (3+88)
92 (1+3+88)
(Yes, I'd like both the list of each element of every subset, and the sum of those elements for each subset.

Thanks!

[Joacim Andersson]

I hope you do realize that if you have 20 values, combining them all this way would result in a list of more than a million values (1,048,575 values to be exact).

[rp-usa]

I posted 20 just as a number to use -- I'm mostly interested in learning the method to do this. In practice, it would probably be no more than 15 items, which would be ... 32767, if I did the math right.

[Joacim Andersson]

I haven't used VBA in ages, so I'm going to post some pseudo-code instead but it should give you an idea. Let's say that the number of values (rows) you have is stored in numOfValues.

For i = 0 To numOfValues - 1
  Dim sum As Integer
  sum = 0
  For j = 0 To i
    If (i + 1) And (2^j) = (i + 1)
       sum = sum + CellValueAtRow(j) 'or possibly (j+1) if the Rows are not zero based
    End If
  Next
  InsertValueToTheList sum
Next

[rp-usa]

I haven't used VBA in ages, so I'm going to post some pseudo-code instead but it should give you an idea. Let's say that the number of values (rows) you have is stored in numOfValues.

For i = 0 To numOfValues - 1
  Dim sum As Integer
  sum = 0
  For j = 0 To i
    If (i + 1) And (2^j) = (i + 1)
       sum = sum + CellValueAtRow(j) 'or possibly (j+1) if the Rows are not zero based
    End If
  Next
  InsertValueToTheList sum
Next

I assume CellValueAtRow(j) and InsertValueToTheList are not actual functions, but rather placeholders for me to write -- which I should be able to do.
But what does If (i + 1) And (2^j) = (i + 1) mean? I don't quite understand what you're doing with the AND?

[Joacim Andersson]

Yes, CellValueAtRow and InsertValueToTheList are not actual functions (I told you that this was pseudo-code). CellValueAtRow is simply the value at that row index. InsertValueToTheList should do whatever you want to do with each value.

Before I explain what I'm doing with the AND operator let me do a correction in the code since it have an error.
The line shouldn't read:
If (i + 1) And (2 ^ j) = (i + 1) Then <--- THIS IS WRONG, my fault sorry!

It should read:
If (i + 1) And (2 ^ j) = (2 ^j)

Let's use the values 1, 3, 88 (from your own example) as the data. Since that is a list of 3 values let us look at a binary type with 3 bits: 000.
The least significant bit (the right-most bit represents the first value, or rather the first position in the list of values). The middle bit the second value and the left-most bit the last value.

In my code example I have two nested loops. The first loop (represented by the variable i) will loop from 0 to 2 (3 values - 1). The inner loop (represented by the variable j) will loop from 0 to the current value of the outer loop.

So first i and j will both have the value 0. So let's put that inside my If statement:
If (0 + 1) And (2 ^ 0) = (2 ^ 0) Then ....
Let's calculate these values:
If (1) And (1) = (1) Then ...
Let's replace the values with binary values:
(001) AND (001)

What the AND operator is doing here is a binary AND comparison,

001
AND
001
===
001

0 AND 0 = 0
0 AND 1 = 0
1 AND 0 = 0
1 AND 1 = 1

So OK 1 AND 1 = 1 is true, so let's add the value of the row(i) to the sum variable (which is 0 to start with), the result is 1 (since that is the first data value).

Let's look at the example where i = 2, and j loops from 0 To 2
'j = 0
If (2 + 1) AND (2 ^ 0) = (2 ^ 0) Then ...
If (3) AND (1) = (1) Then...

Let's check the above with binary numbers:
If (011) AND (001) = (001) Then

Well,
011
001
===
001

Yes, it's true: so take the value from row(0) and add it to sum: sum = 1

'j = 1
(011) AND (010) = (010)

011
010
===
010

True: sum = 1 + 3, sum = 4

'i = 2
(011) AND (011) = (011)

True
sum = 4 + 88 = 92

So basically look at it this way: If we have 3 values let's look at all the combination (with the exception of 0) for a binary number with 3 bits:
001
010
011
100
101
110
111

The bits that are set to 1 represents the values we need to add together.
001 <- Only the first value: 1
010 <- Only the second value: 3
011 <- The first and the second value: 1+3 = 4
100 <- Only the third value: 88
101 <- The third and the first value: 88+1 = 89
110 <- The third and the second value: 88+3 = 91
111 <- All three values: 88+3+1 = 92

[rp-usa]

I understand AND, and I think I understand what you're describing. But I am not seeing those results. Using the same example, I only generate this data:

i (0-2)	j (0 to i)	i+1	2^j	binary i+1	binary 2^j	(i + 1)And(2^j)	2^j=AND?	sum
0	0		1	1	001		001			001		y	1
1	0		2	1	010		001			000		n	
1	1		2	2	010		010			010		y	3
2	0		3	1	011		001			001		y	1
2	1		3	2	011		010			010		y	1+3=4
2	2		3	4	011		100			000		n

[Joacim Andersson]

You're right. I messed it up a bit, which happens when you don't test your theory.
The outer loop must of course be the maximum of what you can store in a 3-bit value (if you only have 3 data values) which is 7. So basically the outer loop should be:

For i = 0 To (2 ^ numOfValues) - 1

Of course if you now have more than 15 data values the (2 ^ numOfValues) would be larger than what fits (as a positive number) in a signed 16-bit integer so both the variable i as well as numOfValues should be declared as Long.

[GBeats]

Hi,

sry to reply but wow i never used binary like that before, something new to study

[Ecniv]

I'm going to second the GBeats wow...




For me, after putting the unique values into an array, I'd probably use a recursive loop to get to the results that you wanted. They always cause me headaches though

[rp-usa]

Thanks for the posts -- very interesting! I got very busy at work and had to ignore this for a while. Looking at it again, ... OW, my head hurts! I have to admit I don't quite see how this is working; but I'll look again later. The one downside for me with this approach is that the spreadsheet stops calculating after a pretty limited number (31 rows). Maybe I made an error ...

[Joacim Andersson]

Well, if you have 31 rows then combining every combination of those would lead to a list of 2,147,483,647 values. That is not a small limited list.

[Siddharth Rout]

It's not a school project, just a personal one. I would love to learn how to do this myself, but I just don't know where to start (other than building up to 20 nested loops, with some kind of exit based on the number of values I'm dealing with; that just seems pretty inefficient).

To clarify:
- there are 1-20 rows (only 1 column) of data
- each row (cell) has a value ranging from 1-88
- I would like to generate every possible subset

For example: if the data were 1 3 88, I would like the output to be:
1 (1)
3 (3)
88 (88)
4 (1+3)
89 (1+88)
91 (3+88)
92 (1+3+88)
(Yes, I'd like both the list of each element of every subset, and the sum of those elements for each subset.

Thanks!

I hope you do realize that if you have 20 values, combining them all this way would result in a list of more than a million values (1,048,575 values to be exact).

I posted 20 just as a number to use -- I'm mostly interested in learning the method to do this. In practice, it would probably be no more than 15 items, which would be ... 32767, if I did the math right.

@rp-usa: Well, if I have understood your logic correctly then no, there will not be 1,048,575 values for 20 values nor 32767 for 15 values. There will be only 117 values for 15 values. We would not be using the X^X approach to calculate the total number of results.

Here is a simple visual demonstration of 15 values. I believe what you want is a PROGRESSIVE COMBINATION and not ALL PERMUTATION & COMBINATIONS. Let me know if I am missing anything?

[Joacim Andersson]

Here is a simple visual demonstration of 15 values. I believe what you want is a PROGRESSIVE COMBINATION and not ALL PERMUTATION & COMBINATIONS. Let me know if I am missing anything?

Yes.

For example: if the data were 1 3 88, I would like the output to be:
1 (1)
3 (3)
88 (88)
4 (1+3)
89 (1+88)
91 (3+88)
92 (1+3+88)
(Yes, I'd like both the list of each element of every subset, and the sum of those elements for each subset.

[Siddharth Rout]

Hmm that is another way to look at it. I wish if OP could expand more on this...