找到所有向量均等于向量元素和不大于k的元素而不递归 [英] Find all vectors with sum equal of vector elements and elements not bigger of k without recursion

问题描述

我想找到所有向量，其总和等于向量元素和不大于k但不使用递归的元素。例如，向量元素的数量n为5，sum = 10且k = 3，输出将为：



3 1 2 2 2

3 1 2 1 3

3 1 1 3 2

3 1 1 2 3

3 1 0 3 3

3 0 3 3 1

3 0 3 2 2

3 0 3 1 3

3 0 2 3 2

3 0 2 2 3

3 0 1 3 3

2 3 3 2 0

2 3 3 1 1

2 3 3 0 2

2 3 2 3 0



使用递归的源代码在Java中是：

I want to find all vectors with sum equal of vector elements and elements not bigger of k but without using recursion. For example in number of vector elements n is 5, sum=10 and k=3 than, the output will be:

3 1 2 2 2
3 1 2 1 3
3 1 1 3 2
3 1 1 2 3
3 1 0 3 3
3 0 3 3 1
3 0 3 2 2
3 0 3 1 3
3 0 2 3 2
3 0 2 2 3
3 0 1 3 3
2 3 3 2 0
2 3 3 1 1
2 3 3 0 2
2 3 2 3 0

The source code with using recursion in Java is:

private static void printVectors(int p[], int n) {

       for (int i = 0; i < n; i++) {
           System.out.print(p[i] + " ");
       }
       System.out.println();
   }

   private static void computeVectors(int[] n, int sum, int k, int k1, int i) {


       if (sum == 0) {

           printVectors(n, n.length);
       } else if (i < n.length) {

           for (int j = k; j >= 0; j--) {

               if (j <= k1) {
                   n[i] = j;
                   computeVectors(n, sum - j, sum - j, k1, i + 1);
               }
           }
       }
   }

我的问题是如何在不使用递归的情况下重新设计computeVectors（）函数？

My question is how to redesign computeVectors() function without using recursion?

推荐答案

让我重新解释一下你的问题：我理解你想要枚举所有长度为dim的向量，其中每个元素可以具有[0 ... K]的值，并且所有元素的总和为N.



一个简单的方法是枚举所有长度的向量，其中元素的值为[0 ... K]。这是第N组合的K.然后对于每个这样的向量检查它的元素和是否为N.虽然这可能适用于小N和K，但这是一个相当耗时的方法。



对于大N和K以下方法可能会更快：将总和N想象为我们想要分配到昏暗箱中的球的集合。首先将它们分配到第一个箱子中，总是花费尽可能多的球进入箱子。对于N = 5，K = 3和dim = 4将提供：



3 2 0 0



我们将这种分布称为最左侧分布，因为根据我们的规则，所有球都位于​​最左侧。



现在尝试移动当时单球。我们总是从左侧拿出第一个球，我们可以选择并且只向前移动最小数量的箱子，直到我们可以合法地丢弃它。在我们的例子中，这将产生



2 3 0 0



还有一条规则需要考虑：一旦我们丢球，我们必须将球重新分配到左侧以形成最左侧的配置。因此，我们的下一步将从左边的垃圾箱中取出一个球放入第三个垃圾箱，之后我们重新将剩余的四个球重新分配：



3 1 1 0



我们只是继续这些规则，直到我们再也无法向前移动球。以下代码表示这些规则。我用简单的C风格编写它，所以你可以根据自己喜欢的编程语言进行调整。

Let me rephrase your question: I understand you want to enumerate all vectors of length dim, in which each element can have a value of [0 ... K] and for which the sum of all elements is N.

One easy approach would be to enumerate all vectors of length, in which the elements have a value of [0 ... K]. That''s K to the Nth combinations. Then for every such vector check whether its element sum is N. Although that might work for small N and K, it is a rather time consuming approach.

For large N and K the following approach might be faster: Think of the sum N as collection of balls that we want to distribute into dim bins. Start by distributing them into the first bins, always spending as many balls as fits into the bin. For N = 5, K = 3 and dim = 4 that would deliver:

3 2 0 0

We call this kind of distribution a "left-most" distribution as all balls reside as far left as posible according to our rules.

Now try to move a single ball at the time. We always take the first ball from the left that we can pick and only carry it forward a minimal number of bins until we can drop it legally. In our example that would yield

2 3 0 0

There is one more rule to consider: As soon as we have dropped a ball, we must redistribute the balls to its left to form a left-most configuration. So our next step will take one ball out of the left bin in drop it into the third bin, after which we redistrubte the remaining four balls anew:

3 1 1 0

We simply continue with these rules until we are no longer able move a ball forward. The following code represents these rules. I have written it in simple C-like style, so you can adapt it to whatever programming language you like.

void Distribute (int* vec, int dim, int k, int n)
{
    for (int idx = 0; idx < dim; ++idx)
    {
        vec[idx] = min (n, k);
        n -= vec[idx];
    }
    assert (n == 0);
}

bool MoveUp (int* vec, int dim, int k)
{
    int collected = 0;
    for (int idx = 0; idx < dim; ++idx)
    {
        if (collected == 0)
            collected = vec[idx];
        else
        {
            if (vec[idx] < k)
            {
                vec[idx] += 1;
                Distribute (vec, idx, k, collected-1);
                return true;
            }
            else
            {
                collected += k;
            }
        }
    }
    assert (collected != 0);
    return false;
}

void PrintVec (int* vec, int dim)
{
    for (int idx = 0; idx < dim; ++idx)
        printf ("%d", vec[idx]);
    printf ("\n");
}

int main()
{
    int vec[4];
    memset (vec, 0, sizeof vec);
    Distribute (vec, 4, 3, 5);
    PrintVec (vec, 4);
    while (MoveUp (vec, 4, 3))
        PrintVec (vec, 4);
    return 0;
}

我猜这很好地说明它可以用一种简单的迭代方式完成 - 因为有很多问题。代码并不像递归代码那样优雅，当然。但我猜这不是你的问题。

I guess that demonstrates nicely that it can be done in a simple iterative way - as so many problems. The code is not as elegant as the recursive one, for sure. But that was not your question I guess.

这篇关于找到所有向量均等于向量元素和不大于k的元素而不递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！