Number of combinations of the arrangement of caps

1 posts Thu, Nov 18, 2021 at 12:34 AM in Skill Building for Algorithm

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.

View: Threaded  |  Flat
+0

Comments

  • wally66wally66 Re: Number of combinations of the arrangement of caps (response to post by pitrel)
    1 posts Fri, Mar 10, 2023 at 10:24 AM

    I try to help you:

    • first person points on the second person so first person talk about the second (fixed)
    • 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)

    • the fourth people can only talk about the glass of the 3 people that is the neighbour ( not the fith people because the value of the glass of the fifth people is derived by the last 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 ?
    +0
Sign In or Register to comment.