8

特定の番号の個別の要素を持つすべての可能なパーティション (2 つ以上の部分) を生成する C コードを作成しようとしています。特定のパーティションのすべての数の合計は、特定の数と等しくなければなりません。たとえば、 inputn = 6の場合、異なる要素を持つ 2 つ以上の要素を持つすべての可能なパーティションは次のとおりです。

  • 1、5
  • 1、2、3
  • 2、4

再帰的なアプローチが機能するはずですが、個別の要素の追加された制約を処理できません。C/C++/Java の疑似コードまたはサンプル コードを提供していただければ幸いです。

ありがとう！

編集:作業が簡単になる場合は、少なくとも 2 つの要素を持つパーティションの制限を無視できます。これにより、番号自体をリストに追加できます (たとえば、6 自体は些細ですが有効なパーティションになります)。

4

5 に答える 5

2

まず、繰り返しを含むパーティションを含むすべてのパーティションを返す再帰アルゴリズムを作成します。

次に、重複要素を含むパーティションを排除するアルゴリズムを作成します。

編集：

既に表示されている番号を再帰的に呼び出すことを避けることで、結果の重複を避けることができます。擬似コード:

Partitions(n, alreadySeen)
 1. if n = 0 then return {[]}
 2. else then
 3.    results = {}
 4.    for i = 1 to n do
 5.       if i in alreadySeen then continue
 6.       else then
 7.          subresults = Partitions(n - i, alreadySeen UNION {i})
 8.          for subresult in subresults do
 9.             results = results UNION {[i] APPEND subresult}
10.    return results

編集：

同じ結果が複数回生成されるのを回避することもできます。これを行うには、ループの範囲を変更して、単調に増加する方法で新しい要素のみを追加するようにします。

Partitions(n, mustBeGreaterThan)
1. if n = 0 then return {[]}
2. else then
3.    results = {}
4.    for i = (mustBeGreaterThan + 1) to n do
5.       subresults = Partitions(n - i, i)
6.       for subresult in subresults do
7.          results = results UNION {[i] APPEND subresult}
8.    return results
于 2013-01-04T18:36:03.047 に答える
2

あなたがやろうとしていることは私にはあまり意味がありませんが、ここに私がそれにアプローチする方法があります.

iまず、 1 から- 1 まで繰り返すループを作成しますn。最初のループでは、パーティション 1 を追加できます。次に、値を使用して再帰的に進みi、1 に追加できるすべてのサブパーティションを取得します。

その後、2 に進みます。

于 2013-01-04T18:37:19.017 に答える
2

再帰はまったく必要ありません。数値のリストは基本的にスタックであり、順番に反復することで重複を防ぎます。

これが私の言いたいことを示すバージョンです (あなたはこの C にタグを付けたので、私は C で書きました。C++ では、プッシュとポップで動的コンテナーを使用でき、これをかなり整理できます)。

#include <stdio.h>
#include <stdlib.h>

void partition(int part)
{
int *parts;
int *ptr;
int i;
int idx = 0;
int tot = 0;
int cur = 1;
int max = 1;

    while((max * (max + 1)) / 2 <= part) max++;

    ptr = parts = malloc(sizeof(int) * max);

    for(;;) {
        if((tot += *ptr++ = cur++) < part) continue;

        if(tot == part) {
            for(i = 0 ; i < ptr-parts ; i++) {printf("%d ",parts[i]);}
            printf("\n");
        }

        do {
            if(ptr == parts) {free(parts); return;}
            tot -= cur = *--ptr;
        } while(++cur + tot > part);
    }
}

int main(int argc, char* argv[])
{
    partition(6);
    return 0;
}
于 2013-01-04T20:53:51.313 に答える
1

重複を生成しないこのソリューションをスケッチしました（美化および最適化できます）。

void partitions(int target, int curr, int* array, int idx)
{
    if (curr + array[idx] == target)
    {
        for (int i=0; i <= idx; i++)
            cout << array[i] << " ";
        cout << endl;       
        return;
    }
    else if (curr + array[idx] > target)
    {
        return;
    }
    else
    {
        for(int i = array[idx]+1; i < target; i++)
        {
            array[idx+1] = i;
            partitions(target, curr + array[idx], array, idx+1);
        }
    }
}

int main(){
    int array[100];
    int N = 6;
    for(int i = 1; i < N; i++)
    {
        array[0] = i;
        partitions(N, 0, array, 0);
    }
}
于 2013-01-04T19:00:09.277 に答える