computes the number of possible orderings of n objects under the relations < and =
Posted
by
hilal
on Stack Overflow
See other posts from Stack Overflow
or by hilal
Published on 2011-01-16T07:45:13Z
Indexed on
2011/01/16
7:53 UTC
Read the original article
Hit count: 222
Filed under:
algorithm
|dynamic-programming
Here is the problem :
Give a algorithm that takes a positive integer n as input, and computes the number of possible orderings of n objects under the relations < and =. For example, if n = 3 the 13 possible orderings are as follows:
a = b = c,
a = b < c,
a < b = c,
a < b < c,
a < c < b,
a = c < b,
b < a = c,
b < a < c,
b < c < a,
b = c < a,
c < a = b,
c < a < b,
c < b < a.
Your algorithm should run in time polynomial in n.
I'm null to this problem. Can you find any solution to this dynamic-programming problem?
© Stack Overflow or respective owner
