Number of combinations of the arrangement of caps
Is there any fast algorithm for this:
K people sit at a table. Each person holds a number (hi) which means: some of his neighbour has a cap of height (hi). I want to count the number of combinations for setting people up at the table according to their height of their cups.
Example:
in:
6
2 6 4 5 3 5
out:
2
(We have two combinations which are 1 2 6 4 5 3 and 6 2 1 4 5 3)
Explanation:
We know that first person points on the second person and last person points on the penultimate person. The neighbour of the second person on the left is two, so his neighbour with height 4 should be on the right. Next we know that left neighbour of fifth person is 4, so his neighbour with height 3 should be on the right. We have two combinations to place 1, 6 cups (1,6 and 6, 1):
Visualisation:
2 6 4 5 3 5
X 2 X X 5 X
X 2 X 4 5 3
Possibilities: 1 2 6 4 5 3 or 6 2 1 4 5 3
Any suggestions or help would be greatly appreciated.
Comments
I try to help you:
last person points on the penultimate person so last person talk about the penultimate (fixed)
Now if continue to this reasoning
the secondo person is the only person that know the glass of the first person (fixed)
the penultimate person is the only person that kwon the glass of the last person (fixed)
and
the third people can only talk about the glass of the 4 people that you neighbour (not the seconth because the value of the glass of the second people is derived by the first people)
So for me i have 1 possibility
first people talked about the second
second people talked about the first
third people talked about fourth people
fourth people talked about the third
fifth people talk about last people
last people talk about the fifth people
For you is it correct ?