0

我正在尝试一个我必须分区的问题。尽可能多的将 N 分成 M 个分区。

例子：

N=1 M=3 , 将 1 分成 3 部分

0 0 1
0 1 0
1 0 0

N=3 M=2 ，将 3 分成 2 部分

2 1
1 2
3 0
0 3

N=4 M=4 ，将 4 分成 4 部分

0 0 0 4
0 0 4 0
0 4 0 0
4 0 0 0
0 0 1 3
0 1 0 3
0 1 3 0
。
.
.

等等。

我确实编写了一个回溯算法。它逐步产生所有可能的组合物，但它会因一些更大的输入而窒息。因为许多组合物是相同的，只是部件的顺序不同。我想减少它。任何人都可以帮助提供更有效的方法。

我的方法：

void backt(int* part,int pos,int n) //break N into M parts
{
    if(pos==M-1)
    {
        part[pos]=n;
        ppart(part);   //print part array
        return;
    }

    if(n==0)
    {
        part[pos]=0;
        backt(part,pos+1,0);
        return;
    }

    for(int i=0;i<=n;i++)
    {
        part[pos]=i;

        backt(part,pos+1,n-i);
    }
}

在我的算法中。n 是 N，它为 N 的每个可能的分区填充数组 part[]。

我想知道的是，一旦生成了一个组合，我想计算该组合将以不同的顺序出现多少次。例如：对于 N=1 ，M=3 ::: 组合只有一个：<0,0,1 > ，但它出现了 3 次。这就是我想知道的每一种可能的独特组合。

再举一个例子：N=4 M=4

组合 <0 0 0 4> 被重复 4 次。同样，对于每一个独特的组合，我都想知道它会出现多少次。

看起来我也通过在这里解释得到它。思考。

谢谢。

4

2 回答 2

0

您可以将 int 转换为分区，如下所示：

vector<int> part(int i, int n, int m)
{
    int r = n; // r is num items remaining to be allocated

    vector<int> result(m, 0); // m entries inited to 0

    for (int j = 0; j < m-1; j++)
    {
        if (r == 0) // if none left stop
            break;

        int k = i % r; // mod out next bucket
        i /= r; // divide out bucket
        result[j] = k; // assign bucket
        r -= k; // remove assigned items from remaining
    }

    result[m-1] = r; // put remainder in last bucket

    return result;
}

因此，您可以按如下方式使用它：

for (int i = 0; true; i++)
{
    vector<int> p = part(i, 3, 4);

    if (i != 0 && p.back() == 3) // last part
       break;

    ... // use p

};

从这里也应该清楚如何制作零件的增量版本。

于 2012-06-04T11:19:10.323 回答
0

一种更简单的数学方法：

这个问题等价于在表达式 f(x) = (1+x+x^2+x^3+....+x^N)^M 中求 x^N 的系数

f(x) = ((x^(N-1) - 1)/(x-1))^M 将其微分 M 次(d^Nf(x)/dx^N) 并且系数将为 ( 1/n!)*(d^Nf(x)/dx^N) 在 x = 0；

可以使用任何数值微分技术进行微分。所以算法的复杂度是 O(N*complexity_of_differentiation)..

于 2013-12-11T10:53:49.230 回答