生成一个数的所有不同分区

Question

我正在尝试编写一个C代码来生成所有可能的划分（由2个或更多部分组成），这些划分的元素是不同的，给定数字的所有数字的总和应等于给定数字。例如，对于输入"n = 6"，具有2个或更多元素且具有不同元素的所有可能的分区如下：

• 1, 5
• 1, 2, 3
• 2, 4

我认为递归方法应该可以解决问题，但我无法处理不同元素的附加约束。非常感谢提供C / C ++ / Java伪代码或示例代码。

谢谢！

编辑：如果简化问题，则可以忽略至少具有两个元素的分区限制。这将允许将数字本身添加到列表中（例如，数字6本身将是一种微不足道但有效的分区）。

- mayank

---

这可以帮助：http://www.numericana.com/answer/numbers.htm#partitions - David Ranieri

@DavidRF 谢谢，但是这个链接计算的是分区数（而不是实际的分区），而且还允许重复。更准确的描述应该是http://oeis.org/A000009，但它仍然不能帮助我生成这些分区。 - mayank

可能是Project Euler 76 - List All Partitions For a Given Number的重复问题。 - mbeckish

@mbeckish 这个问题与众不同，因为我还要求分区中的每个数字都是不同的。所以像 n 个1这样的情况是不允许的。 - mayank

生成一组元素的划分集（特别是数字）是一个经典的回溯问题。 - Mihai8

以后参考，Patrick87的答案让理解变得非常简单。 - mayank

Answer 1

您根本不需要使用递归。数字列表本质上是一个堆栈，通过按顺序迭代，可以确保没有重复项。

下面是一个示例代码（您标记了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;
}

- JasonD

---

请不要编写像((tot += *ptr++ = cur++) < part)这样难以理解的代码。虽然压缩代码在可读性和可维护性方面是一种虚假的节省，但请注意，基于尝试理解这段代码的一个完整的后续问题已经产生了。 - templatetypedef

@JasonD，你能帮我解决这个问题吗？https://dev59.com/-qrka4cB1Zd3GeqPXw1V - famedoro

Answer 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

- Patrick87

---

@mayank 请查看我的编辑。这应该能解决你的问题，而不会生成无效的答案。基本上，这解决了“找到一个数的所有分区，不包含任何一组元素”的问题。你的问题可以归约为这个问题；调用给定算法时，使用已经看过的 = {}。 - Patrick87

@mayank 的确可能会有这个问题。当然，可以通过仅循环大于或等于上一个数字的数字来克服这个问题。实际上，您可以摆脱整个“alreadySeen”的业务并解决以下问题：找到由严格大于给定数字的数字组成的所有分区。您的问题也可以归结为该问题；将函数称为具有0作为“必须大于此”参数。然后，将for循环更改为从mustBeGreaterThan + 1开始，而不是从1开始。 - Patrick87

是的，在阅读了您之前的伪代码后，我也在考虑类似的方案。感谢您的确认并提供更新的伪代码！这看起来更简单、更美观，而且应该更快。 - mayank

@woodchips 在我的回答中，我提供了几种不同的方法来完成这个任务，效率也有所不同。 - Patrick87

如果我们只需要计算有多少个选项，那么这个能被优化吗？ - tomer.z

Answer 3

你试图做的事情对我来说没有太多意义，但是这是我处理它的方法。

首先，我会创建一个循环，从1到n-1遍历i。在第一次循环中，您可以添加分区1，i。然后，我将使用 i 中的值进行递归，以获取还可以添加到1的所有子分区。

然后继续到2，依此类推。

- Jonathan Wood

---

我相信在第i步，他可以从i+1迭代到remainder-i；所有大于remainder-i的数字都已经被考虑过了，并且会落入重复的分区。 - LSerni

Answer 4

我勾勒了这个解决方案（它可以被美化和优化），不应该生成重复项：

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);
    }
}

- imreal

---

非常感谢！这似乎很好用！我会尝试理解和测试它。 - mayank

Answer 5

这是另一种基于迭代算法的解决方案。它比@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;
}

- Randy Lai