5

前几天有人通过电子邮件问我一个关于整数分区的问题（因为我发布了一个 Perl 模块，Integer::Partition，来生成它们），我无法回答。

背景：这里是7的所有整数分区（每行之和等于7）。

7
6 1
5 2
5 1 1
4 3
4 2 1
4 1 1 1
3 3 1
3 2 2
3 2 1 1
3 1 1 1 1
2 2 2 1
2 2 1 1 1
2 1 1 1 1 1
1 1 1 1 1 1 1

现在，如果我们查看每个分区的长度并计算每个长度有多少：

1 1
2 3
3 4
4 3
5 2
6 1
7 1

...我们看到一个分区的长度为 1 (7)，一个分区的长度为 7 (1 1 1 1 1 1 1)。有 4 个长度为 3 的分区：(5 1 1)、(4 2 1)、(3 3 1)、(3 2 2)。

对于较大数量的 N，如果您绘制分区长度的分布图，则会出现一条不对称曲线，向原点倾斜。如果您好奇，请绘制以下 N=40 的分区长度计数。

1兆

如果您对生成这些分布计数感兴趣，这是我使用的代码：

#! /usr/local/bin/perl

use strict;
use warnings;

use Integer::Partition;

my $n = shift || 1;

while (1) {
    my $start = time;
    my $i = Integer::Partition->new($n);
    my %size;
    while (my $p = $i->next) {
        $size{scalar @$p}++;
    }

    open my $out, '>>', "bucket-count.out";
    for my $s (sort {$a <=> $b} keys %size) {
        print $out "$n\t$s\t$size{$s}\n";
    }
    close $out;
    my $delta = time - $start;
    print "$n\t$delta secs\n";
    ++$n;
}

（注意：在我的电脑上，生成 N=90 大约需要 10 分钟）。

所以我的问题是：什么方程可以用来匹配观察到的分布曲线？它是高斯分布（高斯分布可以是不对称的吗？）还是泊松分布，还是别的什么？

我如何解决它的N？如果我记得我高中的数学，我可以通过求解导数与 0 相交的时间来确定峰值。如何产生导数？我在网上搜索过，但我得到的只是深奥的数学论文。我只需要一些代码:)

4

1 回答 1

2

我认为泊松分布是一个合理的估计。鉴于假设您的问题现在转向寻找最大频率 k 之一，给定 N。我认为您有两种方法：

  1. 从数学的角度弄清楚（我会从组合数学开始，但这可能不是一个特别好的指导）
  2. 假设它是泊松，并测量任何给定 N 的峰值，如上所述。

一旦你有了峰值 (k)，估计 lambda 应该很简单（尝试一些）并且你有你的曲线。

另一种方法是在 python 中完成整个工作并在 numpy 或 scipy 板上询问:-)

高温高压

于 2008-10-25T11:12:40.820 回答