如何编写大量的for循环

Question

我是编程的新手,所以如果我没有正确地提出这个问题,我很抱歉.

我有以下代码:

int sum = 100;
int a1 = 20;
int a2 = 5;
int a3 = 10;
for (int i = 0; i * a1 <= sum; i++) {
    for (int j = 0; i * a1 + j * a2 <= sum; j++) {
        for (int k = 0; i * a1 + j * a2 + k * a3 <= sum; k++) {
            if (i * a1 + j * a2 + k * a3 == sum) {
                System.out.println(i + "," + j + "," + k);
            }
        }
    }   
}

基本上它的作用是告诉我的不同组合a1,a2和a3那等于上述款项(在这种情况下,100).这工作正常,但我现在正试图将它应用于更大的数据集,我不知道如何在没有手动编程for循环或高级知道我将拥有多少变量的情况下(可以在10到6000之间) ).我基本上有一个SQL查询从数组加载该数据.

在Java或python(我正在学习两者)中有没有办法自动创建嵌套for和if循环？

非常感谢提前.

Answer 1

递归.

这就是你想要解决的问题:

您当前的示例:20x ₁ + 5x ₂ + 10x ₃ = 100

所以一般来说你做的是:₁ x ₁ + A ₂ x ₂ + ... + A _n x _n = SUM

所以你传入一个常量数组{A ₁,A ₂,...,A _n },你想解决{x ₁,x ₂,...,x _n }

    public void findVariables(int[] constants, int sum, 
                              int[] variables, int n, int result) {
        if (n == constants.length) { //your end condition for the recursion
            if (result == sum) {
                printArrayAsList(variables);
            }
        } else if (result <= sum){ //keep going
            for (int i = 0; result + constants[n]*i <= sum; i++) {
                variables[n] = i;
                findVariables(constants, sum, variables, n+1, result+constants[n]*i);
            }
        }
    }

并呼吁你使用你的例子:

    findVariables(new int[] {20, 5, 20}, 100, new int[] {0,0,0}, 0, 0)

Answer 2

虽然它可能无法扩展,但这里是一个非常简单的暴力python解决方案,不需要递归:

import itertools
target_sum = 100
a = 20
b = 5
c = 10
a_range = range(0, target_sum + 1, a)
b_range = range(0, target_sum + 1, b)
c_range = range(0, target_sum + 1, c)
for i, j, k in itertools.product(a_range, b_range, c_range):
    if i + j + k == 100:
        print i, ',', j, ',', k

此外,还有一些方法可以计算任意列表列表的笛卡尔积,而无需递归.(lol=清单清单)

def product_gen(*lol):
    indices = [0] * len(lol)
    index_limits = [len(l) - 1 for l in lol]
    while indices < index_limits:
        yield [l[i] for l, i in zip(lol, indices)]
        for n, index in enumerate(indices):
            index += 1
            if index > index_limits[n]:
                indices[n] = 0
            else:
                indices[n] = index
                break
    yield [l[i] for l, i in zip(lol, indices)]

如果您只是学习python,那么您可能不熟悉yield语句或zip函数; 在这种情况下,下面的代码将更清楚.

def product(*lol):
    indices = [0] * len(lol)
    index_limits = [len(l) - 1 for l in lol]
    index_accumulator = []
    while indices < index_limits:
        index_accumulator.append([lol[i][indices[i]] for i in range(len(lol))])
        for n, index in enumerate(indices):
            index += 1
            if index > index_limits[n]:
                indices[n] = 0
            else:
                indices[n] = index
                break
    index_accumulator.append([lol[i][indices[i]] for i in range(len(lol))])
    return index_accumulator

通过跳过i + j + k大于的值,您在代码中做了一件聪明的事情sum.这些都没有.但是有可能修改后两个来做到这一点,但失去了一般性.