A combinatorial problem.

[Robin GrahamParticipant @robingraham42208]

[Robin GrahamParticipant @robingraham42208]

I have only three gauge blocks – 10, 20 and 25mm. I use them for checking micrometers. Obviously I can check at 10,20,25 with single blocks, 30,35,45 by wringing two together and 55 mm by wringing all three. So 7 combinations.

Naturally I wonder about enumerating the possible combinations if I had N blocks. From the binomial theorem there are 2^N -1 possible combinations. That's easy enough. But how to actually list them systematically? I thought it should be easy to translate my 3 block example into computer code and generalise, but it's proving harder than I thought.

I had a look around and found:

n%){,=}+[[]]@1/{`{1$+}+%}%;,n*

which isn't helpful.

Anyone with a handy algorithm?

 

Robin.

 

Edited By Robin Graham on 26/08/2023 00:02:40

Edited By Robin Graham on 26/08/2023 00:04:32

Edited By Robin Graham on 26/08/2023 00:16:23

[Ady1Participant @ady1]

combinations and permutations

Edited By Ady1 on 26/08/2023 00:33:55

[DC31kParticipant @dc31k]

Your example is incorrect. You have eight possibilities. You can choose zero blocks. The total is the sum of the corresponding line in Pascal's triangle.

I think your problem can be described as the sum of 'N choose R' (or 'R choose N', I forget which way the terms are used).

So you do 3 choose 0 plus 3 choose 1 plus 3 choose 2 plus 3 choose 3 to arrive at your total.

In Python, it is easy as there is an itertools module that does the combinations and permutations maths for you.

You might have to consider uniqueness in your calculations – different combinations of blocks could add up to the same total. Again, in Python, you put your total into a set, which cannot contain duplicate entries.

If you want to display systematically, you store the total and block choices in a standard list. For 30, the list item would be (30, 10, 20); for 35, the list would be (35, 20, 25). Then sort the list by total and print out the list.

When the numbers get big (like an 81 piece imperial gauge block set), the time taken for the calculations is excessive.

Edited By DC31k on 26/08/2023 07:11:32

[John HaineParticipant @johnhaine32865]

You have 3 blocks each of which may be in the stack or not. The sum of the heights is

A*10 + B*20 + C*25

where A B and C can be 1 or 0 depending on whether you use that block or not. ABC forms a binary number, which can go from 0 to 7:

000, 001, 010, 011, 100, 101, 110, 111

For each you can easily compute the total height and enumerate the possibilities. A 2 minute spreadsheet gives:

0 0 0 0
0 0 1 25
0 1 0 20
0 1 1 45
1 0 0 10
1 0 1 35
1 1 0 30
1 1 1 55

[SillyOldDufferModerator @sillyoldduffer]

Python supports permutations with the 'itertools' module. Example is a snip from the program I used to calculate all the ratios available from my lathe's change gears. All combinations of 4 gears from a list of 11 gears.

import itertools # Load the module that does permutations

metric = [ 20, 30, 45, 50, 60, 60, 65, 70, 75, 80, 85 ] # list the gears available by tooth count

# print all combinations by looping through the list of permutations

for a,b,c,d in itertools.permutations( gears, 4 ):
print(a,b,c,d)

Dave

[Robin GrahamParticipant @robingraham42208]

Thanks for replies. In saying that there are 7 combinations of my three blocks I was deliberately ignoring zero blocks – hence (2^n)-1 rather than 2^n.

When looking about before posting here I did see some Python implementations but it's been too long since I wrote any Python so passed over. This old dog can't even remember old tricks, let alone learn new ones!

I've written a recursive C function which does the job – the problem is well suited to recursive solution – but I wanted to find a non-recursive algorithm.

Posted by John Haine on 26/08/2023 07:12:59:

You have 3 blocks each of which may be in the stack or not. The sum of the heights is

A*10 + B*20 + C*25

where A B and C can be 1 or 0 depending on whether you use that block or not. ABC forms a binary number, which can go from 0 to 7:

000, 001, 010, 011, 100, 101, 110, 111

For each you can easily compute the total height and enumerate the possibilities. A 2 minute spreadsheet gives:

0 0 0 0
0 0 1 25
0 1 0 20
0 1 1 45
1 0 0 10
1 0 1 35
1 1 0 30
1 1 1 55

Thanks John. That's a penny-drop moment for me. A very neat way of thinking about it and easily implemented in C. Problem solved I think.

Robin.

[SillyOldDufferModerator @sillyoldduffer]

Posted by Robin Graham on 26/08/2023 22:42:44:

…

When looking about before posting here I did see some Python implementations but it's been too long since I wrote any Python so passed over. This old dog can't even remember old tricks, let alone learn new ones!

I've written a recursive C function which does the job – the problem is well suited to recursive solution – but I wanted to find a non-recursive algorithm.

Posted by John Haine on 26/08/2023 07:12:59:…

…

Robin.

This is the problem with becoming an old dog! If you know Python, this, and similar problems are trivial. Much harder to implement in 'C' starting from scratch with a recursive algorithm. Unless of course, you already know C and understand recursion! It saves having to learn Python.

C/C++ and Python are my all time favourite languages. They complement each other delightfully. In this particular case Python easily wins on rapid development grounds. Unless high performance is essential, or the code has to be low-level for a system reason, Python gets the code written faster and performance is usually more than acceptable.

I strongly recommend Python to anyone looking for a general purpose computing language. (Not so useful on microcontrollers: MicroPython is sawn-off compared with big brother. Not bad on a powerful microcontoller like the Pi Pico though. )

Dave

[Robin GrahamParticipant @robingraham42208]

Posted by SillyOldDuffer on 27/08/2023 10:43:09:

[…]

C/C++ and Python are my all time favourite languages. They complement each other delightfully. In this particular case Python easily wins on rapid development grounds.

[…]

Dave

Not being a Pythonite it would have taken me longer to refresh my memory and look around to see what libraries have been developed over the last 20+ years than to code in C. Using John Haine's method it took maybe 45 minutes to code in C – but that includes error checking to avoid the unhelpful 'Segmentation fault (core dumped)' message. Python does a lot of work 'under the hood' I suppose.

Anyhow, I got it working.

The whole thing started because I wanted to check my micrometers (0-150mm) for an upcoming project and when Zoro emailed saying they were upset and hoped a 15% discount might lure me back, I thought to buy some gauge blocks. But what sizes should I get?

This is a bit niche I know, but I found that using John's method it took about 7ms to calculate the 65535 non-zero combinations of 16 blocks, about 22 seconds(!) to order them by bubble sorting and another 7ms to weed out unique values. For the 7 blocks I now have it took 23 microseconds to calculate the 127 combinations, 1 millisecond to sort and 300 microseconds to weed out unique values. That's on an ancient Intel Duo 2 machine.

I now know how to make make 82 unique combinations from seven blocks covering the range I need with no more than a 2mm gap between sizes.

Thanks again for contributions, Robin.

[DC31kParticipant @dc31k]

Posted by Robin Graham on 30/08/2023 00:22:58:

The whole thing started because I wanted to check my micrometers (0-150mm)

It might be worth sniffing aroung the NPL's literature on metrology. If you are to check a micrometer over, say, a 1" range, there are a number of preferred measurements at which to make those checks.

I do not recall the exact details, but in principle, the 'best' way is _not_ using regular intervals.

Please see here just as an example of a commercial one:

https://mqs.co.uk/mm1-8-micrometer-check-set-with-stand-8-pieces-inch.html

Micrometers have been around a long time and standardised methods have been developed for their calibration. It would be wise to be aware of them as that gives you a rationale for any deviations you make from that method.

[SillyOldDufferModerator @sillyoldduffer]

Posted by Robin Graham on 30/08/2023 00:22:58:

Posted by SillyOldDuffer on 27/08/2023 10:43:09:

[…]

C/C++ and Python are my all time favourite languages. They complement each other delightfully. In this particular case Python easily wins on rapid development grounds.

[…]

Dave

Not being a Pythonite it would have taken me longer to refresh my memory and look around to see what libraries have been developed over the last 20+ years than to code in C. Using John Haine's method it took maybe 45 minutes to code in C – but that includes error checking to avoid the unhelpful 'Segmentation fault (core dumped)' message. Python does a lot of work 'under the hood' I suppose.

Anyhow, I got it working.

…

Getting it working is the main thing, installing and learning Python for a one-off requirement is daft if you already know another language.

If 'C' were a road vehicle, I'd say it was the most powerful motorbike on the planet. Wonderful, but has to be ridden with great care and skill or the rider crashes. 'Segmentation fault (core dumped)' is only one of many exciting possibilities the programmer has to manage. Python is more like a posh pick-up truck – much easier to drive with reasonable performance, comfortable, safe and very capable.

The 'under the hood' comment is correct. Apart from protecting the programmer from hard crashes, Python claims to be 'batteries included'. Comes close – it's achieved by having a huge library of modules. Almost guaranteed that someone has written a Python module that supports what you need, which avoids much grunt work and debugging. If necessary you can write your own module. Many are written in C for high performance and efficiency.

Dave

[Rod RenshawParticipant @rodrenshaw28584]

Interesting thread, far beyond my IT knowledge.

Can anything similar be done for sets of angle blocks where each block ( in a stack of blocks ) can be used one way around to add to the total angle or the other way around to reduce the total angle?

Rod

[DC31kParticipant @dc31k]

Posted by Rod Renshaw on 30/08/2023 14:50:55:

Can anything similar be done for sets of angle blocks

Yes.

Write down the list of blocks of whose possibilities you would like to see.

For a 15 degree block, you would list it twice as +15 and -15. The possibility of selecting it twice would take care of itself as it would lead to a zero result.

You would have to write a little logic into the program at the results printing stage so that it did not try to tell you that it could make -45 degrees from -30 and -15 as well as +45 degrees from the same blocks.

[Robin GrahamParticipant @robingraham42208]

Posted by DC31k on 30/08/2023 08:10:00:

Posted by Robin Graham on 30/08/2023 00:22:58:

The whole thing started because I wanted to check my micrometers (0-150mm)

It might be worth sniffing aroung the NPL's literature on metrology. If you are to check a micrometer over, say, a 1" range, there are a number of preferred measurements at which to make those checks.

I do not recall the exact details, but in principle, the 'best' way is _not_ using regular intervals.

Please see here just as an example of a commercial one:

https://mqs.co.uk/mm1-8-micrometer-check-set-with-stand-8-pieces-inch.html

Micrometers have been around a long time and standardised methods have been developed for their calibration. It would be wise to be aware of them as that gives you a rationale for any deviations you make from that method.

Thanks for this – I'll have a sniff around, but more out of interest than for any practical purpose. I imagine NPL are concerned with very high accuracy. I think I'd be fooling myself if I believed that I could measure anything to micron accuracy under normal workshop conditions.

At £395 + VAT I doubt that I'll be buying the MQS set of standards, but thanks for the link!

Robin.

[Robin GrahamParticipant @robingraham42208]

Posted by Rod Renshaw on 30/08/2023 14:50:55:

Interesting thread, far beyond my IT knowledge.

Can anything similar be done for sets of angle blocks where each block ( in a stack of blocks ) can be used one way around to add to the total angle or the other way around to reduce the total angle?

Rod

As DC31k says it's entirely possible. The code I've written could be adapted fairly easily. However, it's Linux terminal based so perhaps not friendly to everyone. PM me if you're interested though.

Robin

[Martin ConnellyParticipant @martinconnelly55370]

There is another way to do this type of there/not there calculation, that is to use a spreadsheet in the "sledgehammer to crack a nut" way.

List all the blocks across the top row

In the columns below, in the first column going down put 0 1 0 1 0 1 …..

In the second column put 0 0 1 1 0 0 1 1…..

In the third column put 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 …

Do this pattern for all the blocks increasing the repetition of 1s and 0s in powers of 2 for each column until you get down to a row that is all 1s

Finally add a calculation in the cells of another column that uses absolute positions for the sizes and relative positions for the 1s and 0s to add together the values of the there (1s) blocks for a total thickness.

If you add a column numbered 0 to whatever the bottom row is (eg 7, 15, 31…) you can sort the table into total size and unsort it back to original order as required.

It is probably easier to do than to explain but is easier for a non-programmer to understand and expand to their own needs. If we had the option I would create an example, it would only take a few minutes, and post it in the forum.

Martin C

[John HaineParticipant @johnhaine32865]

Indeed, see 4th post down.

[Martin ConnellyParticipant @martinconnelly55370]

Sorry, missed the bit where it mentioned a spreadsheet. I have had family visiting this week and was just skimming through posts to catch up. However having done a quick spreadsheet for10 blocks it is clear that you could add a column that counts how many blocks are used for each combination. 10 blocks results in 1024 combinations and there are likely to be a few that give the required result. A column that also shows the number of blocks used will help pick the one(s) that require the smallest number of blocks. Sorting on the resulting total for the blocks and then the number of blocks allows you to quickly identify a combination that best suits needs.

Martin C

[Rod RenshawParticipant @rodrenshaw28584]

Thanks to those who responded to my question about angle blocks.

I was just curious really. I do have a few angle blocks but I don't have enough blocks or use them often enough to need to have a spreadsheet or other aid to get any particular angle.

Rod

[Author]

Posts