NUMBER OF COMBINATIONS OF THE ARRANGEMENT OF CAPS

[Member_15434824]

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.

[Greg Utas]

You need to specify the problem more clearly. Does everyone at the table have two neighbors, or do the two people at each end only have one neighbour? This may or may not affect the answer.

Robust Services Core | Software Techniques for Lemmings | Articles
The fox knows many things, but the hedgehog knows one big thing.