computes the number of possible orderings of n objects under the relations < and =

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 =开发者_如何学JAVA 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?

The code

Let f(n,k) be the number of possible orderings with exactly k inequality relations (and (n - 1 - k) quality relations).

Easy to see, that f(n,0) = 1, f(n,n-1) = n! for any n.

Now we want to compute f(n,k) for any k. Imagine, you moved away one number (any), so there are now (n-1) numbers. There are two possabilities:

1) There are (k-1) inequalities in those (n-1) numbers, and there are (k+1)(f(n-1,k-1)) ways to add n'th number so that new inequality added.

2) There are k inequlaities in those (n-1) numbers, and there are (k+1)(f(n-1,k)) ways to add n'th number with no additional inequality.

So, f(n,k) = (k+1)(f(n-1,k-1) + f(n-1,k)).

The final answer F(n) = f(n,0) + f(n,1) + ... + f(n,n-1).

If you just have <, then a set of size N can be ordered N! different ways.

If you add back in =, then you can count partitions of the set into different number of equivalence classes -- and multiply by the number of ways of ordering them.

For example, let's do a set of size 3 (like your example). We can have 1, 2 or 3 equivalence classes. There's only 1 way to have 1 equivalence class, 3 ways to have 2 equivalence classes and 1 way to have 3 equivalence classes (see later for how to compute these). This gives 1 * 1! + 3 * 2! + 1 * 3! = 13 total orderings.

This breaks the original problem into a simpler one: counting ways to partition a set into k parts. If you write a function S(N, k) to do this, you can get the answer to the original problem by computing:

sum(k! * S(N, k) for k in 1, 2, ..., N).

You can use these recurrence relations to count partitions (see http://en.wikipedia.org/wiki/Stirling_number_of_the_second_kind):

S(N, k) = S(N - 1, k - 1) + k * S(N - 1, k)
S(N, 1) = 1
S(N, N) = 1

And you can use dynamic programming to compute this function.

you can have recursive function for this:

F(1) = 1;
F(2) = 3;


F(n) = F(n-1) * n + F(n-2) * n*(n-1)/2 + F(n-3) * n*(n-1)(n-2)/3!+.... + F(1) * n + 1;

for example

F(2) = 1 * 2 +1 = 3;
F(3) = F(2) * 3 + F(1) * 3 + 1 = 9 + 3 + 1 = 13;

Why?

think you know F(n-1) now you want insert An in your sequences, An can be in the 0,1,2,...nth place in the sequence, no matter, counting the number of sequences:

[A0,...An-1] < An this can be as  [A0,...An] < An-1,... 

so there are n * f(n-1) sequences end with <

how many sequences end with one `=` sign? f(n-2) * n * (n-1)/ 2 why? ... (think yourself it's easy)

how many sequences end with "K" "=" sing? f(n-k+1) * n * ...*(n-k+1)/ k!

and there is one sequence full =

this can be calculated polynomially simply.