Author |
Topic: Urgent Excel (Read 4270 times) |
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
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.
|
|
 IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
fatball
Senior Riddler
Can anyone help me think outside the box please?
Gender:
Posts: 315
|
 |
Re: Urgent Excel
« Reply #26 on: May 10th, 2017, 12:53pm » |
 Quote  Modify
|
towr, your generalized model is very neat. Can you elaborate on the rationale behind the formula inside the body of the table please?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Urgent Excel
« Reply #27 on: May 10th, 2017, 10:35pm » |
Quote Modify
|
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.
|
| « Last Edit: May 10th, 2017, 10:35pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
fatball
Senior Riddler
Can anyone help me think outside the box please?
Gender:
Posts: 315
|
|
Re: Urgent Excel
« Reply #28 on: May 11th, 2017, 6:54am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Urgent Excel
« Reply #29 on: May 11th, 2017, 1:02pm » |
Quote Modify
|
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.
|
| « Last Edit: May 11th, 2017, 1:03pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
fatball
Senior Riddler
Can anyone help me think outside the box please?
Gender:
Posts: 315
|
|
Re: Urgent Excel
« Reply #30 on: May 11th, 2017, 3:57pm » |
Quote Modify
|
Thanks towr, so then why would this approach end up having the effect of a binary algorithm? How do you reconcile the two concepts?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Urgent Excel
« Reply #31 on: May 11th, 2017, 11:40pm » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
fatball
Senior Riddler
Can anyone help me think outside the box please?
Gender:
Posts: 315
|
|
Re: Urgent Excel
« Reply #32 on: May 14th, 2017, 9:08am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Urgent Excel
« Reply #33 on: May 14th, 2017, 1:10pm » |
Quote Modify
|
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.)
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
dudiobugtron
Uberpuzzler
Posts: 735
|
|
Re: Urgent Excel
« Reply #34 on: May 14th, 2017, 1:33pm » |
Quote Modify
|
Afaict that only goes up to 512. That's according to this page, anyway.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Urgent Excel
« Reply #35 on: May 14th, 2017, 10:18pm » |
Quote Modify
|
Huh, you're right. What a weird limitation. Who ever heard of ten bit numbers.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
fatball
Senior Riddler
Can anyone help me think outside the box please?
Gender:
Posts: 315
|
|
Re: Urgent Excel
« Reply #36 on: May 16th, 2017, 10:23am » |
Quote Modify
|
Thank you all for help!
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
combos_2.zip