java - 生成 x 个整数分区

Question

我有一个递归算法，它生成作为参数给定的数字的所有组合。它还可以根据“k”进行分区，“k”也可以作为参数给出。只要我们输入的数字较小，它就可以正常工作。但是随着'n'的增加，计算结果需要更多的时间和空间。

是否可以给定“x”作为输入，这样算法只返回数字的 x 个分区，而不是全部。这是我正在寻找的示例:

输入:

n = 10,
k = 4, partition n into 'k'parts
x = 2, number of partitions required
m = 4, maximum number in the partition

输出:

1. 4,2,2,2

2. 4,3,2,1

这是我使用的算法:

int h=0;        //iterator
public ArrayList<int[]> generate_partitions(int n,int k,int max,boolean norep)
{
    int korig;
    korig = k;
    int[] A = new int[korig+1];
    ArrayList<int[]> partitions = new ArrayList<int[]>();
    GenP(A, n, k, korig, 1,partitions,max);
    if(norep)
    {
        for(int i=0; i<partitions.size(); i++)
        {
            if(check_repetition(partitions.get(i),max))
                partitions.remove(i);
        }
    }
    return partitions;
}
boolean check_repetition(int[] a,int max)
{
    boolean[] hash = new boolean[max+1];
    for(int i=0; i<max+1; i++)
        hash[i]= false;
    for(int i=0; i<a.length; i++)
    {
        if(hash[a[i]]==false)
            hash[a[i]]=true;
        else
            return true;
    }
    return false;
}
void GenP(int[] A, int n, int k, int korig, int l, ArrayList<int[]> partitions,int max)
{
    //n = number to partition
    //korig = original k
    //l = least number integer required in partition
    if (k==1)   // k = number of partitions
    {
        A[k]=n;
        int [] temp = new int[korig];
        // System.out.println("size = "+korig);
        boolean max_check = false;
        for (int j=1; j<=korig; j++)
        {
            // System.out.print(A[j]+" ");
            temp[j-1]=A[j];
            if(A[j]>max)
                max_check = true;
        }
        if(!max_check) {
            partitions.add(temp);
        }
        //System.out.println();
    }
    else
    {
        if (k==0)
        {
            h=0;
        }
        else
        {
            h=n/k;
            for (int i=l; i<=h; i++)
            {
                A[k]=i;
                GenP(A, n-A[k], k-1, korig, A[k], partitions,max);
            }
        }
    }
}

Answer 1

引入一个全局计数器(与h相同的地方)，将其初始化为零。每次对答案添加分区时，计数器加 1。递归调用 GenP 后，检查计数器是否已经达到 x，如果达到，则立即从递归函数返回。

您的 norep 版本不会那么容易打补丁。您的算法实际上会发出重复项吗？ (您发布的不是完整且可运行的 Java 代码，所以我没有运行它。)如果是这样，当然可以修补算法本身以仅发出唯一分区。然而，确切的限制是什么并没有明确说明(或者至少我无法一目了然)。一旦您指定了问题的确切公式，一个不会生成重复项的简洁高效的算法可能是一个单独问题的主题。