8

我正在尝试编写一个 C 代码来生成具有给定数字的不同元素的所有可能的分区(分成 2 个或更多部分)。给定分区的所有数字的总和应该等于给定的数字。例如,对于 input n = 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 迭代到n- 1 的循环。在第一个循环中,您可以添加分区 1,即。然后我会使用 in 的值进行递归,i以获取所有也可以添加到 1 的子分区。

然后继续2,以此类推。

于 2013-01-04T18:37:19.017 回答
2

你根本不需要递归。数字列表本质上是一个堆栈,并且通过按顺序迭代可以确保没有重复。

这是一个版本,它说明了我的意思(您标记了这个 C,所以我用 C 编写了它。在 C++ 中,您可以使用带有 push 和 pop 的动态容器,并对其进行大量整理)。

#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 回答
0

这是另一种基于迭代算法的解决方案。它比@imreal 的算法快得多,也比@JasonD 的算法快一点。

计算 n = 100 所需的时间

$ time ./randy > /dev/null
./randy > /dev/null  0.39s user 0.00s system 99% cpu 0.393 total
$ time ./jasond > /dev/null
./jasond > /dev/null  0.43s user 0.00s system 99% cpu 0.438 total
$ time ./imreal > /dev/null
./imreal > /dev/null  3.28s user 0.13s system 99% cpu 3.435 total
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int next_partition(int *a, int* kp) {
    int k = *kp;
    int i, t, b;

    if (k == 1) return 0;
    if (a[k - 1] - a[k - 2] > 2) {
        b = a[k - 2] + 1;
        a[k - 2] = b;
        t = a[k - 1] - 1;
        i = k - 1;
        while (t >= 2*b + 3) {
            b += 1;
            a[i] = b;
            t -= b;
            i += 1;
        }
        a[i] = t;
        k = i + 1;
    } else {
        a[k - 2] = a[k - 2] + a[k - 1];
        a[k - 1] = 0;
        k = k - 1;
    }
    *kp = k;
    return 1;
}

int main(int argc, char* argv[])
{
    int n = 100;
    int m = floor(0.5 * (sqrt(8*n + 1) - 1));
    int i, k;
    int *a;
    a = malloc(m * sizeof(int));
    k = m;
    for (i = 0; i < m - 1; i++) {
        a[i] = i + 1;
    }
    a[m - 1] = n - m*(m-1)/2;

    for (i = 0; i < k; i++) printf("%d ", a[i]);
    printf("\n");

    while (next_partition(a, &k)) {
        for (i = 0; i < k; i++) printf("%d ", a[i]);
        printf("\n");
    }
    free(a);
    return 0;
}
于 2019-12-30T01:29:06.927 回答