wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Urgent Excel
        
(Message started by: fatball on May 8th, 2017, 10:44am)
Title: Urgent Excel
Post by fatball on May 8th, 2017, 10:44am
Assume I have a set of 10 different numbers and I want to obtain a sum for each combination of 2 to 9 numbers.  How can I do it quickly with Excel please?
Title: Re: Urgent Excel
Post by dudiobugtron on May 8th, 2017, 12:22pm
The set of all the different combinations is called the 'powerset' - you basically need to generate the powerset and then work out the sum of each element of it. There are over 1000 possible combinations you will need to add, so doing it manually would probably be too hard.  (The powerset has 1024 elements but you only need 1012 of them.)

Excel doesn't have a powerset function, but if you know how to use Visual Basic for Applications in Excel, then people have written some code to do that:

http://www.tushar-mehta.com/excel/tips/powerset.html

And here is some info about using VBA in Excel:
http://www.excel-easy.com/vba.html

Sorry I couldn't be more help than that!  I haven't actually done this myself, so I can't give you specific tips for your situation.  You might be able to just write your own code to generate the powerset in a format that is easy to copy and paste into excel.
Title: Re: Urgent Excel
Post by fatball on May 8th, 2017, 12:29pm
No, your advice is very helpful, I can write VBA codes.  Let me give it a try and see if it works.  Thanks.
Title: Re: Urgent Excel
Post by towr on May 8th, 2017, 12:49pm
You can also do it with copy-pasting ten times

start with two empty rows
put the 10th number in the 10th column of the first row
copy all rows, paste them under existing rows.
put the 9th number in the 9th column of the pasted rows.
copy all rows, paste them under existing rows.
put the 8th number in the 8th column of the pasted rows.
etc

make the 11th column the sum of the previous 10.
eliminate the rows with exactly 1 or ten numbers.



You can probably also make all the numbers variables instead so you can fill in any set of 10 numbers.
Title: Re: Urgent Excel
Post by fatball on May 8th, 2017, 1:40pm
towr,  I started with this simple approach as well, but there was no way I could address all the possible combinations?
Title: Re: Urgent Excel
Post by rmsgrey on May 8th, 2017, 3:49pm
Or you can set up a binary array:

A1:J1 = 0
A2 = 1 - A1
B2 = if (A1==1 and A2 == 0); 1-B1; B1
Copy A2 into A2:A1024
Copy B2 into B2:J1024

Give or take my not remembering Excel syntax properly, that will give you every binary number from 0 to 1023. You can then get all 1024 sums by copying a suitable formula down another column. Eliminating the 12 sums you don't want and then making use of the remaining 1012 sums is up to you :)
Title: Re: Urgent Excel
Post by towr on May 8th, 2017, 10:12pm

on 05/08/17 at 13:40:07, fatball wrote:
towr,  I started with this simple approach as well, but there was no way I could address all the possible combinations?
What do you mean by "address"?
Title: Re: Urgent Excel
Post by fatball on May 9th, 2017, 8:32am

on 05/08/17 at 22:12:14, towr wrote:
What do you mean by "address"?

I need the sum of each and every combination.
Title: Re: Urgent Excel
Post by fatball on May 9th, 2017, 8:37am
rmsgery, I will give it a try and let you know.  Thanks.
Title: Re: Urgent Excel
Post by towr on May 9th, 2017, 8:49am

on 05/09/17 at 08:32:20, fatball wrote:
I need the sum of each and every combination.

I don't see how that's a problem; you just paste "sum of previous ten columns" in the 11th, and then the 11th column has all the sums.
Title: Re: Urgent Excel
Post by fatball on May 9th, 2017, 9:19am
uhmmm, but all I will be getting is 11 results bot 1000?
Title: Re: Urgent Excel
Post by towr on May 9th, 2017, 10:09am
see attachment

You can fill in whatever ten numbers you want in the first row, and it'll fill out the rest of the sheet. Sums of combos are in the L column.
Title: Re: Urgent Excel
Post by fatball on May 9th, 2017, 10:21am

on 05/09/17 at 10:09:13, towr wrote:
see attachment

You can fill in whatever ten numbers you want in the first row, and it'll fill out the rest of the sheet. Sums of combos are in the L column.

How do you populate Cols A to J starting row 3?
Title: Re: Urgent Excel
Post by towr on May 9th, 2017, 10:47am
The cells in the rows from 3 down have an absolute reference to cells in the top row, i.e. the cells contain =$A$1 up to =$J$1 (or nothing if the number is left out of that combo)
So if you change the values in the top row, the rest copy that one.

By using absolute references, you can just copy the row, and they'll reference the same cells as the original row, instead of other cells that have the same relative position to the new row.
i.e. if you copy a cell with =$A$1 from A3 to A4, it'll still reference A1 i.s.o. A2 as it would if A3 contained =A1.
And I just realized I could have made things slightly easier for myself if I had only made the row-position absolute (i.e. using =A$1), then I could have just copied that to the other columns to refer to the top cell.
Title: Re: Urgent Excel
Post by fatball on May 9th, 2017, 10:52am
I know but you were not copying and pasting the entire row as there were blank cells with no formulae.  How did you set up the criteria for each row?  Using some sort of binary algorithm like what rmsgrey suggested?  
Title: Re: Urgent Excel
Post by towr on May 9th, 2017, 10:56am
I started with a full row, then copied it, then emptied the tenth column from the rows I copied (i.e. the top half).
Then copied all the rows again, and emptied the 9th column of the rows I copied.
and so on.
Then I removed rows with just one value in them. (Which conveniently is always the first row in which each number occurs, tenth in row 1(+2), 9th in row 2(+2), 8th in row 4(+2) etc)


1 2 3 4

=> duplicate rows + clear half of 4th column

1 2 3 _
1 2 3 4

=> duplicate rows + clear half of 3th column

1 2 _ _
1 2 _ 4
1 2 3 _
1 2 3 4

=> duplicate rows + clear half of 2th column

1 _ _ _
1 _ _ 4
1 _ 3 _
1 _ 3 4
1 2 _ _
1 2 _ 4
1 2 3 _
1 2 3 4

=> duplicate rows + clear half of 1th column

_ _ _ _
_ _ _ 4
_ _ 3 _
_ _ 3 4
_ 2 _ _
_ 2 _ 4
_ 2 3 _
_ 2 3 4
1 _ _ _
1 _ _ 4
1 _ 3 _
1 _ 3 4
1 2 _ _
1 2 _ 4
1 2 3 _
1 2 3 4

=> remove rows with 0 or 1 value

_ _ 3 4
_ 2 _ 4
_ 2 3 _
_ 2 3 4
1 _ _ 4
1 _ 3 _
1 _ 3 4
1 2 _ _
1 2 _ 4
1 2 3 _
1 2 3 4


I suppose it doesn't really matter at what end you start, or whether you empty the bottom or top half of the column each step.  
Title: Re: Urgent Excel
Post by fatball on May 9th, 2017, 11:07am
Oh so you were indeed taking a manual approach...is there a way to generalize the model with sth like rmsgrey suggested?  I was attempting it but found it quite tedious.

On a side note, why couldn't I see your illustration in your main message but only under the topic summary when I replied?
Title: Re: Urgent Excel
Post by towr on May 9th, 2017, 11:13am

on 05/09/17 at 11:07:34, fatball wrote:
Oh so you were indeed taking a manual approach...is there a way to generalize the model with sth like rmsgrey suggested?  I was attempting it but found it quite tedious.
Well, it didn't take me more than 7 minutes.

I'm really not an excel-wizard, I didn't even know how to use absolute cell-reference until yesterday. I could probably write something in python that would generate an excel sheet for a given number of values, but you'll have to wait for one of the other puzzler to get an answer how to do it purely in excel (and/or VBA).


Quote:
On a side note, why couldn't I see your illustration in your main message but only under the topic summary when I replied?
Because I was still editing it in :P
Title: Re: Urgent Excel
Post by fatball on May 9th, 2017, 11:19am
In that case, I may as well do it the same way as yours as all I need is a quick solution.  Building a model in excel takes time and writing the VBA codes takes longer... :)  
Title: Re: Urgent Excel
Post by dudiobugtron on May 9th, 2017, 12:41pm
Thanks for the tip about absolute references btw towr!  Very useful, but I didn't even think that they might be a thing until I read your post today.
Title: Re: Urgent Excel
Post by fatball on May 9th, 2017, 1:36pm
It did not really take that long to do it the towr way.  I needed to do it for 18 numbers and it just took me less than 15 min to populate over 260K rows.  Thanks!
Title: Re: Urgent Excel
Post by dudiobugtron on May 9th, 2017, 6:03pm
If I'm understanding it correctly, then a slight speed-up for towr's method would be to paste *after* deleting the column.  That way you can quickly select all the things you want to copy (ctrl+a, ctrl+c) and delete (just click on the column header). The only time you'd need to find the right row would be when pasting.
Title: Re: Urgent Excel
Post by fatball on May 9th, 2017, 8:17pm
but at which point do I have to delete any column? I just create the columns I need to hold my numbers...
Title: Re: Urgent Excel
Post by towr on May 9th, 2017, 11:05pm
You don't delete the column, but the contents.

like

1 2 3 4
1 2 3 4

=> copy (no paste)

1 2 3 4
1 2 3 4

=> delete column-content

1 _ 3 4
1 _ 3 4

=> paste

1 _ 3 4
1 _ 3 4
1 2 3 4
1 2 3 4

So that's a bit faster since you don't need to select half a column.
Title: Re: Urgent Excel
Post by fatball on May 10th, 2017, 6:19am
It sounds like deleting the entire column content is technically better than deleting half-column, but practically there will be no gain in time as, with the revised method, you have to place your cursor precisely for the copy-delete-paste steps; but by pasting first, the cursor will end up sitting at the same spot, i.e., mid-way of the entire data set, thus you can easily select the half column to delete with these buttons [shift] [end] [up arrow]...
Title: Re: Urgent Excel
Post by towr on May 10th, 2017, 11:03am
An alternative, more scalable solution. Using an extra column of integers as bitmask (skipping powers of 2) and a row of powers of two to check whether to include a value or not.
You can now simply extend the whole matrix in one go by copying columns/rows

NB, I had to use OpenOffice. I think excel actually has a BITAND, which would've made it a bit easier.
Title: Re: Urgent Excel
Post by fatball on May 10th, 2017, 12:53pm
towr, your generalized model is very neat.  Can you elaborate on the rationale behind the formula inside the body of the table please?
Title: Re: Urgent Excel
Post by towr on May 10th, 2017, 10:35pm
The basic rationale is, include value for column (top row) if the bit for its corresponding power of two (5th row) is set in the index bit-mask (column A)

For reference, the complete formula (in D7) is =IF(MOD(INT($A7/D$5);2);D$1;0)

$A7 is the index bitmask in column A, row 7, $A makes the column reference absolute, so copying will always refer to the first column when copied. The row will automatically change to the correct one when copied to another row.
D$1 is the value we want to use in the combo (or not), it's always the number in the top row, but column can vary when copied elsewhere.
D$5 is the bit we need to lookup in the bitmask to decide whether to include the value or not, it's always in the fifth row of the column.

Because I can't use BITAND (because openoffice sucks even more than excel), I'm using an alternative to check whether the bit is set or not.
BITAND(x; 2^y) == (x div 2^y) % 2 == MOD( INT(x/2^y); 2)
So, if the bit is set, include the value D$1 in the combo, else leave it out and use 0 instead.
Title: Re: Urgent Excel
Post by fatball on May 11th, 2017, 6:54am
I am fully comfortable with all your Excel work including the absolute and relative referencing but guess I need to study more about the concept of bit and bitmask.
Title: Re: Urgent Excel
Post by towr on May 11th, 2017, 1:02pm
Well, bits and bitmasks is just a useful abstraction for me, it's not necessary, per se.

Basically every number can be written uniquely as a sum of distinct powers of two, e.g. 11 = 1 + 2 + 8. And what I'm doing is checking if a given power of two is part of the sum for a given number. In this case 4 isn't part of the sum (and also anything greater than 8), so we'd leave the third value (and anything after the 4th) out of the combination on the row with index 11.
Title: Re: Urgent Excel
Post by fatball on May 11th, 2017, 3:57pm
Thanks towr, so then why would this approach end up having the effect of a binary algorithm?  How do you reconcile the two concepts?
Title: Re: Urgent Excel
Post by towr on May 11th, 2017, 11:40pm
The sum of powers of two representation is equivalent to the binary representation.
A binary representation 1011 means 1*8 + 0*4 + 1*2 + 1*1 = 8 + 2 + 1 = 11

And you might notice it's very much the same as what we're trying to do, except instead of powers of two we have a "random" set of numbers.
Say we have numbers a, b, c, d that we want to use in a combination. Then we can use the binary representation 1011 to mean 1*a + 0*b + 1*c + 1*d = a + c + d
We just replace the powers of two in the sum by the numbers we want combinations for.
By looping through all binary representations (up to 2^(# of values)), we loop through all combinations of our set of numbers.

Looping through all binary representations is also equivalent to a manual approach where each step you duplicate all the rows, but include the next power of two in the new rows:
0*1
1*1
=>
0*1
1*1
1*2 + 0*1
1*2 + 1*1
=>
0*1
1*1
1*2 + 0*1
1*2 + 1*1
1*4 + 0*1
1*4 + 1*1
1*4 + 1*2 + 0*1
1*4 + 1*2 + 1*1

The main difference with my manual version earlier is that my procedure was in some way reversed: I started with all 1s (in binary), and removed them from a column in each step, instead of starting with all zeroes and adding 1s in a column each step.

Comparison:

0000 vs 1111
=>
0000 - 1110
0001 - 1111
=>
0000 - 1100
0001 - 1101
0010 - 1110
0011 - 1111
=>
0000 - 1000
0001 - 1001
0010 - 1010
0011 - 1011
0100 - 1100
0101 - 1101
0110 - 1110
0111 - 1111
=>
0000 - 0000
0001 - 0001
0010 - 0010
0011 - 0011
0100 - 0100
0101 - 0101
0110 - 0110
0111 - 0111
1000 - 1000
1001 - 1001
1010 - 1010
1011 - 1011
1100 - 1100
1101 - 1101
1110 - 1110
1111 - 1111

You end up with exactly the same thing both ways.

A lot of problems are just figuring out how to map one thing you know (numbers 0 to 2^10) to another thing you want (sums of combination of up to 10 values). And there's multiple equivalent ways to do it.
Title: Re: Urgent Excel
Post by fatball on May 14th, 2017, 9:08am
is it possible to automate the manual copying and pasting with a formula like this one: MOD( INT(x/2^y); 2) in order to list a full result of binary representation e.g. 1100, 1010, etc.
Title: Re: Urgent Excel
Post by towr on May 14th, 2017, 1:10pm
If you want the binary representations, you could just fill in 1 for all values in the last spreadsheet.
Though perhaps a better way is to use excels DEC2BIN function. (Which gives the binary representation as (probably a) string in one column, rather than as 0s and 1s spread over multiple columns.)
Title: Re: Urgent Excel
Post by dudiobugtron on May 14th, 2017, 1:33pm
Afaict that only goes up to 512.  That's according to this page (https://support.office.com/en-us/article/DEC2BIN-function-0f63dd0e-5d1a-42d8-b511-5bf5c6d43838?ui=en-US&rs=en-US&ad=US&fromAR=1), anyway.
Title: Re: Urgent Excel
Post by towr on May 14th, 2017, 10:18pm
Huh, you're right. What a weird limitation. Who ever heard of ten bit numbers.
Title: Re: Urgent Excel
Post by fatball on May 16th, 2017, 10:23am
Thank you all for help!


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board