0

いいえを分割する必要がある問題を試しています。可能な限り多くのMパーティションにN。

例：

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 130
。
。
。

等々。

私はバックトラックアルゴをコーディングしました。可能なすべての構成を段階的に生成しますが、入力が大きくなるとチョークになります。多くの構成はパーツの順序だけが異なるため、それを減らしたいと思います。より効率的な方法を提供するために誰かが助けてくれますか。

私の方法：

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 :::コンポジションは1つだけです：<0,0,1 >、しかしそれは3回発生します。それは私がすべての可能なユニークな構成について知りたいことです。

別の例：N = 4 M = 4

コンポジション<0004>が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 に答える