11023 - Multisets and Sequences

[sclo]

I got AC on this one, but my time is quite slow.
It seems that the bottleneck in my code is in the derive and find command.
Is there any way to do these without generating the (sub)multisets of the multiset? i.e. Are there any ways to do it in O(n^2) instead of O(n*2^n)?

[Cho]

Is the following input legal?

Code: Select all

degrade {}
promote () 0
rank {}
derive () 0 0
find {} ()
derive (1,2,3) 0 0
find {} (1,2,3)
end

If so, is this output correct?

Code: Select all

()
{}
0
{}
0
{}
0

Are there any ways to do it in O(n^2) instead of O(n*2^n)?

There is probably no polynomial time solution. My solution heavily relies on the subroutine which counts the number of multisubset (with size m) of a multiset (with size n). It's exponential but could finish in 0.3+ seconds (WA though ).

[little joey]

Is the following input legal?

Yes.

If so, is this output correct?

Yes.

Are there any ways to do it in O(n^2) instead of O(n*2^n)?

I don't think so. There are some pretty fast algos for simple sets. I searched real hard, but couldn't find anything useful on multisets.

[tadeu]

Is there an algorithm that, given a set (1,2,3,4,5,...), gives it's n-th permutation in lexicographical order, without needing to compute all permutations before it? I.e, if I want the 6th permutation, it would give me (1,3,2,4,5) directly, without the need to compute:

(1,2,3,5,4)
(1,2,4,3,5)
(1,2,4,5,3)
(1,2,5,3,4)
(1,2,5,4,3)
(1,3,2,4,5)

If not, is there at least one that runs in less than O(n!) ?

[david]

PostPosted: Thu Apr 13, 2006 9:21 pm Post subject: Algorithm
Is there an algorithm that, given a set (1,2,3,4,5,...), gives it's n-th permutation in lexicographical order, without needing to compute all permutations before it?

There is a trivial linear-time algorithm for that if all elements are distinct. But the general case, which is what this problem asks for, is harder. I used DP to find in O(n

[Stephan.Ritscher]

Hi,
in my opinion there are defect (or not correct specified) test cases for this probem.
I tested with my program (assert ) because I got many WAs and think, that in the input there are commands "find", in which the sequence is NOT completely contained in the multiset.
Can anyone check this?
Thank you!

[Stephan.Ritscher]

Sorry guys, everything is ok.
Had a VERY nasty & hard to find bug.

[Adrian Kuegel]

I got AC on this one, but my time is quite slow.
It seems that the bottleneck in my code is in the derive and find command.
Is there any way to do these without generating the (sub)multisets of the multiset? i.e. Are there any ways to do it in O(n^2) instead of O(n*2^n)?

I found a way to get this number with dynamic programming.
Given a set of n available numbers, and the wanted size s, I can calculate the number of sequences of that size in O(n * s).

It is relatively easy to calculate the number of subsets of size s.
For one subset, there are s! / (c_1! * c_2! * ... * c_k!) different orderings where c_i are the number of same elements. When calculating the number of subsets of size s, I could in between divide by c_i! if I take c_i same numbers in the subset, and then just multiply by s! in the end.
To avoid using doubles we multiply by s! before we start the dynamic programming, so the base case is there are s! ways to get a subset of size 0.
Sorry if that sounds confusing, I must admit I was not totally sure this method works, especially since first I got a lot of WAs because of a stupid bug.

[little joey]

I found a way to get this number with dynamic programming.
Given a set of n available numbers, and the wanted size s, I can calculate the number of sequences of that size in O(n * s).

Yes, that is the way I meant this problem to be solved, although I used recursion+memoization in stead of DP to precalculate these quantities, but that is the same thing, essentially.

What I hoped for when I started out creating this problem, is that there would be a direct way of calculating the counts, like with ordinary sets, without doing the precalculations. My original limits for this problem were much bigger (multisets with hundreds or thousands of elements), but I had to let go of that idea.

Somewhere along the route to ranking or unranking sequences in multisets, you have to calculate quantities like Count(7;4,3,2,1,1), by which I mean: count all sub-sequences of size 7 from a multiset of size 11, where the elements are repeated resp. 4, 3, 2, 1 and 1 times. The only way I can think of is using the recursion:

Count(7;4,3,2,1,1) = Count(6;3,3,2,1,1) + Count(6;4,2,2,1,1) + Count(6;4,3,1,1,1) + 2*Count(6;4,3,2,1).

In the case of ordinary sets, where all the repeat counts are 1, there is a direct formula:

Count(7;1,1,1,1,1,1,1,1,1,1,1) = 11! / (11-7)!

and I was hoping to find something like that for multisets. Looks like there isn't one...

[Adrian Kuegel]

I think we do something different, because the only thing I precalculate are the factorials. Then, each find and derive command takes O(n^4) time, the rank and promote command O(n^2) time. But you are right, it seems there is no way efficient enough to handle hundreds or thousands of elements.

[little joey]

OK. I see. But then you ignore the fact that "find {1,2,3} (-1,0,0,0,1,1,2,2,3,3)" and "find {-987,1023,0} (-987,-987,0,24,24,24,100,100,1023,1023)" are similar problems.

After the precalculation phase, that takes place only once, I solve both queries in O(n^2), while your program takes O(n^4) for them, but doesn't precalculate. But I believe that our methods are essentially the same. Also, judged by the runtimes, it looks like my precalculations don't pay off for such a small input set (about 1000 cases). And for these small values of n, your O(n^4) maybe as fast as my O(n^2). (precalculation takes .45 seconds, solving the queries takes 0.11 sec, comparable with your runtime).

EDIT: I think I'm wrong. My precalculation meight be worse than O(n^4), in fact probably exponential. I am not smart enough to do the actual analysis...