如何均匀随机地产生一个单调不降序列

学术版

LionBlaze @ 2024-11-28 18:09:35

rt。

问题：

给定 N,M，如何真正均匀随机（指每种可能的序列的概率相同）出一个长度为 N 的单调不降序列（所以可以有相同的），每个元素是在 [1,M] 中的整数。

显然生成所有数字再排序不是正确的，当 N=2 时就有：

  • 如果两个数字 x,y 相同，则概率为 \dfrac{1}{M^2}。
  • 如果两个数字 x,y（这是经过排序的生成的序列，满足 x < y） 不同，概率为 \dfrac{2}{M^2}。

容易验证概率和为 M \times \dfrac{1}{M^2} + M(M-1) \times \dfrac{1}{M^2} = 1。

更进一步地，如果我们有一个能够均匀随机地产生某种类型（比如一个类）的随机对象产生器，同时有这种类型的小于号重载（可以比较两个对象，并且性质良好），还有这种类型的等于号重载，给定 N，如何产生一个长度为 N 的，对于每个 1 \le i < j \le N 都有 a_i \le a_j（这里的 \le 表示重载后的 a<b || a==b）的序列 a_{1 \cdots N}。

解答必关。

by LionBlaze @ 2024-11-28 19:07:30

普通版的加强版：随机的区间可以不是 [1,M] 而是 [M_{min},M_{max}]，满足 M_{min} \le M_{max}，且 N,M_{max} 尽量大（能多大就多大），M_{min} 尽量小。（忽然发现第一个条件好像就是加强版的弱化版）

加强版的加强版：N 尽量大。（结合上面的“第一个条件就是加强版的弱化版”，如果 N 能做到和普通版的加强版一样大，则可以完全取代其它的三个）

by djfuck @ 2024-11-28 19:07:42

#include <bits/stdc++.h>
int N = 5, M = 5;
int64_t factorial(int n) {
    int64_t res = 1;
    for (int i = 1; i <= n; ++i) {
        res *= i;
    }
    return res;
}
int64_t binom(int n, int m) { return factorial(n) / factorial(m) / factorial(n - m); }
int64_t f(int n, int m) { return binom(n + m - 1, n); }
int64_t g(int start, int len) { return f(len, M - start + 1); }
void generate(int x) {
    std::vector<int> v(1, 1);
    for (int i = 1; i <= N; ++i) {
        int tmp = 0;
        for (int d = v.back(); d <= M; ++d) {
            tmp += g(d, N - i);
            if (tmp >= x) {
                tmp -= g(d, N - i);
                x -= tmp;
                v.push_back(d);
                break;
            }
        }
    }
    for (int i = 1; i <= N; ++i) {
        std::cout << v[i] << " ";
    }
    std::cout << std::endl;
}
int main() {
    int S = f(N, M);
    for (int x = 1; x <= S; ++x) {
        generate(x);
    }
    return 0;
}

好像是这个. 我再看一下

by LionBlaze @ 2024-11-28 19:11:08

这么强 /bx/bx

by LionBlaze @ 2024-11-28 19:11:26

/bx/sto/orz/%%%

by LionBlaze @ 2024-11-28 19:15:37

by djfuck @ 2024-11-28 19:17:52

这个方法本身就有很大的缺陷啊，

一旦 f(n, m) 比较大直接溢出。 大概只能做 n, m 在 10 左右

by LionBlaze @ 2024-11-28 19:21:42

emmm 确实。

by djfuck @ 2024-11-28 19:24:26

#include <bits/stdc++.h>
int N = 7, M = 7;
int64_t factorial(int n) {
    int64_t res = 1;
    for (int i = 1; i <= n; ++i) {
        res *= i;
    }
    return res;
}

int64_t f(int n, int m) {
    int64_t res = 1;
    for (int i = n + 1; i <= n + m - 1; ++i) {
        res *= i;
    }
    for (int i = 1; i <= m - 1; ++i) {
        res /= i;
    }
    return res;
}

void generate(int x) {
    std::vector<int> v(1, 1);
    for (int i = 1; i <= N; ++i) {
        for (int d = v.back();; ++d) {
            x -= f(N - i, M - d + 1);
            if (x <= 0) {
                x += f(N - i, M - d + 1);
                v.push_back(d);
                break;
            }
        }
    }
    for (int i = 1; i <= N; ++i) {
        std::cout << v[i] << " ";
    }
    std::cout << std::endl;
}
int main() {
    int S = f(N, M);
    std::random_device rd;
    std::uniform_int_distribution<int> dist(1, S);
    int x = dist(rd);
    generate(x);
    return 0;
}

by not_clever_syl @ 2024-11-28 19:27:44

考虑把序列映射成 (n-1,m-1) 的格路，然后每个 n-1 个向右和 m-1 个向上的不同排列和一个单调不降序列是双射，于是 shuffle n-1 个 0 和 m-1 个 1 的序列即可，分别代表每步向上走或向右走。

by djfuck @ 2024-11-28 19:31:20

但是这种做法是否只能使 a_N = M?@not_clever_syl

上一页 | 下一页