469,612 Members | 1,639 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 469,612 developers. It's quick & easy.

Number of combinations of the arrangement of caps

1
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.
2 Weeks Ago #1
0 4921

Post your reply

Sign in to post your reply or Sign up for a free account.

Similar topics

1 post views Thread by Jim Hubbard | last post: by
19 posts views Thread by Thomas Cameron | last post: by
3 posts views Thread by Ryan | last post: by
reply views Thread by Louis Aslett | last post: by
5 posts views Thread by placid | last post: by
5 posts views Thread by Bails | last post: by
reply views Thread by devrayhaan | last post: by
reply views Thread by gheharukoh7 | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.