Member Avatar for cadam940

There is a famous recursive relation to find Stirling numbers of the first kind, i.e.

C(n,k)=C(n−1,k−1)+(n−1)C(n−1,k)

This is a solution to the following problem:

Given a set of N distinct numbers, how many different permutations of the set exist such that there are exactly K left-to-right maxima?

This was not very hard, but the following little variation:

Given a multiset of N numbers (not necessarily distinct), how many different permutations of the set exist such that there are exactly K left-to-right maxima (see definition below)?

Example:

Let the multiset be S={1,2,2,3} [Note: the two 2s should be considered non-identical while permuting] and K=3. Then, the following permutations:

<1,2,2,3>
<1,2,2,3>
<1,2,3,2>
<1,2,3,2>

satisfy the required condition. Hence, the answer should be 4 (we do not need to find all the permutations but we are interested in the number of such permutations).

Definition: An element should be considered a maximum if and only if all the elements occurring before it are strictly less than it.

For example, in the above example <1,2,2,3>, the second 2 is not maximum but the first 2 is. Hence, this arrangement satisfy K=3 (not K=4).

PS: I have worked a whole day to solve it, but can't do anything good. Any help is really appreciated.

  • 3 Contributors
  • 3 Replies
  • 397 Views
  • 17 Hours Discussion Span
  • Latest Post Latest Post by rubberman

Dani AI

Generated

Short answer and what to code: this multiset variant is a known, solved extension of the “records / left‑to‑right maxima” statistic. Treat equal-valued items as a class, process classes one at a time (largest first) and keep a DP vector dp[r] = number of labelled permutations seen so far with exactly r records. The combinatorial update for inserting a whole class of n items (all smaller than the ones already processed) is compact and leads to an O(N·K) algorithm you can implement directly. See Myers & Wilf for the rigorous generating‑function/recurrence treatment. (ar5iv.org)

Algorithm (implementation sketch you can code from): let counts = multiplicities of each distinct value, sorted by value descending; let dp[0]=1, all other dp[]=0, and m=0 (current total items). For each class with multiplicity n compute
T = (m+1)(m+2)...(m+n-1) (equal to (m+n-1)!/m!, with T=1 when n=1).
Then update dp in descending r order:
add = dp[r] n T (this contributes to dp[r+1])
dp[r] = dp[r] m T (keeps the dp[r] permutations that remain with same record count)
if r+1 <= K: dp[r+1] += add
After finishing all classes, dp[K] is the exact number of labelled permutations with exactly K strict left‑to‑right maxima. The same update rule (and why it works) is used in short contest editorials that implement the Myers–Wilf idea. (discuss.codechef.com)

Compact Python implementation (uses Python big ints; adapt to modular arithmetic or big-integer library in C++ if needed):

def count_records(counts, K):
    counts = sorted(counts, reverse=True)
    dp = [0]*(K+1); dp[0]=1
    m = 0
    for n in counts:
        T = 1
        for j in range(1, n): T *= (m + j)
        for r in range(K, -1, -1):
            if dp[r]==0: continue
            add = dp[r] * n * T if r+1<=K else 0
            dp[r] = dp[r] * m * T
            if r+1 <= K: dp[r+1] += add
        m += n
    return dp[K]

Notes and practical tips: use big integers or compute modulo early if answer must be mod p; sort values descending beforehand; dp is updated descending to avoid overwrite. This iterative DP is the practical form of the recursive idea suggested, and answers ’s request for code; it matches the formal results in Myers & Wilf for the multiset case. (ar5iv.org)

Recommended Answers

All 3 Replies

Member Avatar for Ancient Dragon

Please post the code you have written.

Member Avatar for cadam940

i don't know how to solve this. I am asking for a approach so as to solve this

Member Avatar for rubberman

It looks like a fairly straight forward recursive algorithm. Work it through in words (pseudo code) what you need to solve it.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.