Simple Combo/Permute calculation

In summary, the conversation discusses a Steam game called Shapez where the goal is to produce and deliver shapes to a hub using conveyor belts. The game involves using four primary shape resources (square, disc, star, and windmill) in various colors and up to four layers. The number of possible symmetrical products is 112, while the number of asymmetrical products is much larger. The conversation also delves into the complexities of rotational symmetry and layer dependencies when trying to determine the total number of possible configurations in the game.
  • #1
DaveC426913
Gold Member
22,559
6,212
TL;DR Summary
How many possible shapes can there be, given these parameters?
I'm playing a Steam game called Shapez wherein the goal is to produce and deliver given shapes to the Hub by conveyor belt.

1683569142675.png

In the screencap you can see resources of discs and squares and well as green and red, which are to be extracted, chopped up and recombined to form the "product" specified in the Hub.

Here's a sample of three different final "products" with multiple quadrants, layers, colours and shapes (all four shapes are at least partially represented here: a disc, star and windmill; a full square is only partially represented):
1683569683156.png

I was lying awake last night, trying to figure out how many possible products there can be, and I kept getting intuitively wrong numbers.I'll start with the easy one. I'll enumerate only products that are fully rotationally symmetrical. i.e. all four quadrants of the deliverable product are identical. Thus:
1683571145408.png

This is a blue windmill, on top of a white disc, on top of a blue disc.Parameters:

  • There are four primary shape resources: square, disc, star and windmill.
  • Each shape can have one of seven colours: R,G,B,C,M,Y and white.
  • And there can be up to four layers. (There is always a bottom later; if there is a second layer, it is on top of that; if there is a third later, it is on top of that, etc. There are no "empty" layers.)
  • (Size is not a parameter; rotational orientation is not a parameter.)

So, the number of (symmetrical) products should be 4x7x4 = 112. Is this right? Is this too low?Now we go to asymmetrical products:

Each quadrant of an asymmetrical product can have one quarter of any of the above, so:

1124, or about 157 million, right?I'm just not sure I've enumerated it correctly. I suspect I've done the layers wrong in the symmetrical step. It's not just x4, is it? Is it to the power of 4?
 
Mathematics news on Phys.org
  • #2
I’m assuming adjacent layers must be of a different color?

Also, can you put a square on top of a fan? It seems ordering matters too.
 
  • #3
erobz said:
I’m assuming adjacent layers must be of a different color?
No.

I mean, it might be true, but that can be treated as an exception. There are likely many exceptions - combinations that have specious rules.
 
  • #4
DaveC426913 said:
No.
No to both?
 
  • #5
erobz said:
Also, can you put a square on top of a fan? It seems ordering matters too.
You can. There are products where the points of stars are all you can see behind a disc.

Higher layers are rendered smaller for this purpose, as seen in the examples, but that has no effect on combinations.

1683573708549.png
 

Attachments

  • 1683573686212.png
    1683573686212.png
    5.7 KB · Views: 58
  • Like
Likes erobz
  • #6
e.g. a blue circle , on a blue circle , on a blue circle, etc... is a valid configuration?
 
  • #7
erobz said:
e.g. a blue circle , on a blue circle , on a blue circle, etc... is a valid configuration?
Yes. It may not actually be called for, but that doesn't mean it isn't part of the set of all possible products. It is not categorically ruled out.

Note that - whether or not it's called for - I can still produce it if I choose. Pretty easily, in fact.
 
  • #8
So 1, 2, 3, 4 layers are all good too? If so:

1 layer configurations ##4\cdot 7##

2 layer configurations ##\left( 4 \cdot 7\right)^2 ##

3 layer configurations ##\left( 4 \cdot 7\right)^3 ##

4 layer configurations ##\left( 4 \cdot 7\right)^4 ##

Total symmetrical configurations:

##28+28^2+28^3+28^4 = 637,420##
 
Last edited:
  • #9
If you are going to try to find the number of configurations in general (each quadrant), its going to be a much worse combinatorics problem than that because of removing rotationally symmetric configurations...well over my head.

For single layer - single shape, is blue circle quad 1 distinct from blue circle quad 4?
 
Last edited:
  • #10
erobz said:
If you are going to try to find the number of configurations in general (each quadrant), its going to be a much worse combinatorics problem than that because of removing rotationally symmetric configurations...well over my head.
Good point.
erobz said:
For single layer - single shape, is blue circle quad 1 distinct from blue circle quad 4?
No. That's what I meant by 'orientation is not a parameter'.
But I see why it can't be ignored, because ignoring it would let duplicates slip in.
 
  • Like
Likes erobz
  • #11
erobz said:
Total symmetrical configurations: ##28+28^2+28^3+28^4 = 637,420##

So with ## n = (28^4 + 28^3 + 28^2 + 28)^4 = 637,420 ## quadrant types there are ## n ^ 4 = 165,083,148,768,756,940,960,000 ## possible permutations: if we divide this by 4 to get 41,270,787,192,189,235,240,000 we will eliminate rotations but we will have eliminated too many (for instance the unique permutation {type1, type1, type1, type1} will have been incorrectly "eliminated" 3 times) so the answer is a little over that. I make it 41,270,830,356,497,512,121,750: can you get this result or have I made a mistake?
 
  • #12
pbuk said:
So with ## n = (28^4 + 28^3 + 28^2 + 28)^4 = 637,420 ## quadrant types there are ## n ^ 4 = 165,083,148,768,756,940,960,000 ## possible permutations: if we divide this by 4 to get 41,270,787,192,189,235,240,000 we will eliminate rotations but we will have eliminated too many (for instance the unique permutation {type1, type1, type1, type1} will have been incorrectly "eliminated" 3 times) so the answer is a little over that. I make it 41,270,830,356,497,512,121,750: can you get this result or have I made a mistake?
Removing rotational symmetry:

For a 1 layer 1 quadrant selection, there is only one configuration.

1683638455380.png


There are then ##4\cdot7 = 28## ways to select a shape and a color.

For a 1 layer 2 quadrant selection, there are two configurations. Sides touching, corners touching.

1683638562248.png


Thats ##2 \cdot \left( 4\cdot7 \right)^2 = 1,568##

For a 1 layer 3 quadrant selection, there is one configuration.

1683638585604.png


Thats ##\left( 4\cdot7 \right)^3 = 21,952##

For a 1 layer 4 quadrant selection, there is one configuration.

1683638664481.png


Thats ##\left( 4\cdot7 \right)^4 = 614,656##

Total 1st layer configurations - removing rotational symmetry ##638,204##, which is not ## \frac{\left( 4 \cdot 7\right)^4}{4} = 153,664##. So for the general case, I don't think that's working.

Also, I feel like there is a layer dependency issue to consider as well.

I think the possible configurations of the second layer, hinge on what configuration has been selected on the first layer? i.e. putting the blue layer on top of the green layer below would not be allowed?

1683640686148.png


But this would be valid.

1683641946671.png


Maybe I'm misinterpreting that part.
 
Last edited:
  • #13
erobz said:
I feel like there is a layer dependency issue to consider as well.
I think the clarifications in #5 and #7 implied that the layers are entirely independent.

erobz said:
putting the blue layer on top of the green layer below would not be allowed?

View attachment 326240
Why not?
 
  • #14
pbuk said:
I think the clarifications in #5 and #7 implied that the layers are entirely independent.Why not?
I've probably misinterpreted this:
Parameters:

  • And there can be up to four layers. (There is always a bottom later; if there is a second layer, it is on top of that; if there is a third later, it is on top of that, etc. There are no "empty" layers.
But I can't see any example in #5 that clarifies that?

I guess that first one on the left does clarify that as a misinterpretation(I think).
 
Last edited:
  • #15
Assuming there no interlayer dependency:

Then I think the total is the sum of all possible layer shapes and configurations:

##638,204+ 638,204^2 +638,204^3+ 638,204^4##

?

Its still not clear in my mind whether or not we need to remove a bunch of rotational symmetries in that. These problem quickly get me spinning in circles. My gut says the answer to that is certainly.
 
Last edited:
  • #16
erobz said:
Assuming there no interlayer dependency:

Then I think the total is the sum of all possible layer shapes and configurations:

##638,204+ 638,204^2 +638,204^3+ 638,204^4##
No, you seem to be confused. The shapes are not composed of 1, 2, 3 or 4 layers each with 4 quadrants, they are composed of 4 quadrants each with 1, 2, 3 or 4 layers. You calculated the correct number of quadrant types in #8: see my extension of that calculation in #11.
 
  • #17
pbuk said:
No, you seem to be confused. The shapes are not composed of 1, 2, 3 or 4 layers each with 4 quadrants, they are composed of 4 quadrants each with 1, 2, 3 or 4 layers. You calculated the correct number of quadrant types in #8: see my extension of that calculation in #11.
In the green shape in post #5 there is no first layer shape in the right side quadrants. The first layer in that shape is

1683673214400.png


The next layer is:

1683673390367.png


The third and final layer is:

1683673467127.png


Which makes:

1683673502931.png
 
  • #18
erobz said:
In the green shape in post #5 there is no first layer shape in the right side quadrants. The first layer in that shape is

View attachment 326265
I see what you mean. That example shape seems to contradict the stated rules:
DaveC426913 said:
...There is always a bottom latyer ... There are no "empty" layers
@DaveC426913 where did you get the examples from? Edit: and where did you get the rules from?
 
Last edited:
  • Like
Likes erobz
  • #19
OK, I have now played the (demo version of the) game: the examples are right, my interpretation of @DaveC426913's rules was wrong.

A shape consists of 1, 2, 3 or 4 layers.
No layer can be completely empty: at least one quadrant must have a part.
Rotational orientation DOES matter so we don't have to worry about eliminations.
So each quadrant of a layer can have any one of 4 shapes in any one of 7 colours, or no shape at all, except that the configuration with no shapes in any quadrant is not allowed.
Edit: That gives ## c = ((4)(7)+1)^4 - 1 = 707,280 ## configurations for a layer.
And with 1, 2, 3 or 4 layers with no interdependencies there are c + c^2 + c^3 + c^4 = 250,245,412,237,998,716,617,680 \approx 2.5 \times 10^{23} shapes in all.
That gives ## c = ((4)(8)+1)^4 - 1 = 1,185,920 ## configurations for a layer.
And with 1, 2, 3 or 4 layers with no interdependencies there are ## c + c^2 + c^3 + c^4 = 1,977,980,197,799,639,651,080,320 \approx 2.0 \times 10^{24} ## shapes in all.
 
Last edited:
  • Like
Likes erobz
  • #20
erobz said:
In the green shape in post #5 there is no first layer shape in the right side quadrants.
Sunuvagun. You're right.
All the more foolish of me since I had just finished building that one.

pbuk said:
@DaveC426913 where did you get the examples from? Edit: and where did you get the rules from?
The examples are levels I've finished. The rules I am deducing. So yeah, I made a mistake there.
 
Last edited:
  • #21
pbuk said:
Rotational orientation DOES matter so we don't have to worry about eliminations.
Not sure why you say this. As far as I am concerned, a final product that's rotated 90 or 180 degrees is the same product.

pbuk said:
in any one of 7 colours,
And I just discovered that no-colour (or grey) is a valid colour, so that makes 8.
 
  • #22
DaveC426913 said:
Not sure why you say this. As far as I am concerned, a final product that's rotated 90 or 180 degrees is the same product.

But not as far as the game is concerned:
1683706706366.png


Have you seen the shape generator? This shows that https://viewer.shapez.io?----CuCu is not the same as https://viewer.shapez.io?CuCu----.

DaveC426913 said:
And I just discovered that no-colour (or grey) is a valid colour, so that makes 8.
Of course: at the start of the (demo) game you only have grey. I have edited my calculation in #19.
 
  • #23
Hm.
I must have the rules wrong because, with my understanding, this product should be impossible:

1683759767886.png


This is how it says it is constructed (I have labeled the layers a and b for clarity):

1683760301010.png


Layer a must be the top layer. (smaller shape = higher layer.)

If I simply drop a on b, it will not form two layers; I know the rules are that, if it can combine two shapes into the same layer without overlap, it will do so.

So this should form a single layer and will look like this:
1683760158331.png


Tricky...
 

Attachments

  • 1683759688831.png
    1683759688831.png
    7.7 KB · Views: 69
  • #24
I threw in my hat on this one. I went looking for hints on how to solve this type ans stumbled across the exact solution. Here it is in a compact, 2 cell-high format. I'd need to duplicate this about 50 times to get it to deliver in less than a few hours.

1683769642671.png
 
  • #25
DaveC426913 said:
Hm.
I must have the rules wrong because, with my understanding, this product should be impossible:

View attachment 326326

This is how it says it is constructed (I have labeled the layers a and b for clarity):

View attachment 326328

Layer a must be the top layer. (smaller shape = higher layer.)

If I simply drop a on b, it will not form two layers; I know the rules are that, if it can combine two shapes into the same layer without overlap, it will do so.

So this should form a single layer and will look like this:
View attachment 326327

Tricky...
So you are finding that what I said in the bottom of post #12 to be the correct interpretation?
 
  • #26
erobz said:
So you are finding that what I said in the bottom of post #12 to be the correct interpretation?
No, that's incorrect.
The samples at the bottom of post 12 are both legal.

I guess the rules need to be relaxed to merely "no layer can be placed on top of an empty layer."In fact, this one is quite simple:
1683817802573.png

It's just:
1683818263127.png

Even this is legal:

1683818481111.png

It's just:
1683818516023.png


But this one is tricky:
1683818652357.png

If you simply stacked blue on top of green, you would actually get this:
1683818745477.png

because it will "melt" together if it can.
 
Last edited:
  • #27
DaveC426913 said:
No, that's incorrect.
The samples at the bottom of post 12 are both legal.

I guess the rules need to be relaxed to merely "no layer can be placed on top of an empty layer."
White squares represent "empty" spots in a layer in my diagrams. By what you stated in #23 I would expect:

1683818775242.png


?
 
  • #28
erobz said:
White squares represent "empty" spots in a layer in my diagrams. By what you stated in #23 I would expect:
Unfortunately, white is a valid colour so you can't use white as null. And I recently found out that even the default grey is a valid colour. So, the way to represent null has to be to literally "not there at all".

Your shape is represented thus:
1683818481111-png.png

That is the case with the actual product I most recently built:
1683759767886-png.png

(The grey circle is actually just the background "placeholder".)
 
  • #29
DaveC426913 said:
Unfortunately, white is a valid colour so you can't use white as null. And I recently found out that even the default grey is a valid colour.

So, the way to represent null has to be to literally "not there at all".
I get that, but the diagrams that I'm creating to get on the same page as you for valid configs. "a white square is empty quadrant in a layer". Thus I am correct that the figure on the left would automatically convert to the figure on the right.

It has significant "structural" implications for how we would count. How may "colors" or "shapes" there actually are to chose from is trivial to the counting process.
 
  • #30
erobz said:
I get that, but the diagrams that I'm creating to get on the same page as you for valid configs. "a white square is empty quadrant in a layer". Thus I am correct that the figure on the left would automatically convert to the figure on the right.
You are technically correct, but your choice of rendering is going to lead to misunderstandings, tears and heartbreak. Remember, we're not the only ones reading this thread. :wink:
 
  • #31
DaveC426913 said:
You are technically correct, but your choice of rendering is going to lead to misunderstandings, tears and heartbreak. Remember, we're not the only ones reading this thread. :wink:
We've already changed it multiple times! The objective is to get to the base level abstraction of how to count configurations for this game.

EDIT:
Even now I'm still not sure we are in agreement based on the edits made in #26! It seems like this:

1683818481111-png.png

is just:

1683818516023-png.png


( Are there 3 white filled quadrants in this figure not shown?)

Disagrees with my assertion that:

1683821476729.png
 
Last edited:
  • #32
erobz said:
We've already changed it multiple times!
I know; I was originally using a shorthand, thinking I only represented what was needed, but it turns out that was wrong and that ambiguity has caused confusion.

Abstraction is one thing, but misrepresentation is not good for communication.

This is the minimal graphic required to represent valid permutations. It needs grey, it needs white and it needs null.
erobz said:
Even now I'm still not sure we are in agreement based on the edits made in #26!
Here is your product:
1683821952929.png


It is legal, and difficult to build.
But how it is built does not factor into the permutations.I'm also seeing a text version that looks like this:
RgRg|--Rg
----|Rb--

Which means:

Layer 1: squaRe-green, squaRe-green | empty, squaRe-green
Layer 2: empty, empty | squaRe-blue, empty
Personally, while that's good codification, I find it less than visually intuitive.
 
Last edited:
  • #33
DaveC426913 said:
I know; I was originally using a shorthand, thinking I only represented what was needed, but it turns out that was wrong and that ambiguity has caused confusion.

Abstraction is one thing, but misrepresentation is not good for communication.

This is the minimal graphic required to represent valid permutations. It needs grey, it needs white and it needs null.

Here is your product:
View attachment 326394

It is legal, and difficult to build.
But how it is built does not factor into the permutations.
Ok, so you are saying the little blue square placed on an empty layer (grey placeholder) will not resize, and move to the base layer like shown in #23?
 
  • #34
erobz said:
Ok, so you are saying the little blue square placed on an empty layer (grey placeholder) will not resize, and move to the base layer like shown in #23?
Right. Mostly.
It can be done, but it's a process that involves cutting and re-combining and disposing of objects in a complex way. I could go into it if you want; it's all laid out in the game guide, but that's behind a passwall, so I'd have to copy and paste the section of the article.

And I just realized that vastly complicates the calculations of the total permutations. Not I'm no longer sure that there are simply static rules, so much as there are procedures (algorithms).
 
  • #35
DaveC426913 said:
Right. Mostly.
It can be done, but it's a process that involves cutting and re-combining and disposing of objects in a complex way. I could go into it if you want; it's all laid out in the game guide, but that's behind a passwall, so I'd have to copy and paste the section of the article.
Not necessary. I thought you were saying it was not a valid config in 23. Forget I ever said anything.
 

Similar threads

  • Sci-Fi Writing and World Building
Replies
21
Views
1K
  • STEM Academic Advising
Replies
13
Views
2K
  • Special and General Relativity
Replies
1
Views
2K
  • Math Proof Training and Practice
2
Replies
67
Views
10K
  • STEM Academic Advising
Replies
6
Views
2K
  • Sci-Fi Writing and World Building
Replies
15
Views
3K
  • Other Physics Topics
2
Replies
48
Views
8K
  • MATLAB, Maple, Mathematica, LaTeX
Replies
5
Views
2K
  • MATLAB, Maple, Mathematica, LaTeX
Replies
5
Views
3K
  • MATLAB, Maple, Mathematica, LaTeX
Replies
20
Views
4K
Back
Top