如何编写大量的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);
            }
        }
    }   
}

这段代码的主要功能是告诉我不同的、和组合，能够加起来等于上面的总和（在这个例子中是100）。这个功能运行得很好，但我现在想把它应用到一个更大的数据集上，我不太确定该怎么做，因为我不想手动编写循环，也不知道我会有多少个变量（可能从10个到6000个都有）。我基本上有一个SQL查询，可以从一个数组中加载这些数据。

有没有办法在Java或者Python中（我正在学习这两种语言）自动创建嵌套的循环和条件判断？

非常感谢！

Answer 1

在Java中，一些简单的通用实现至少需要两个类：

一个委托类，用于传递给递归算法，这样你就可以在执行的任何地方接收更新。可以像这样：

public interface IDelegate {
   public void found(List<CombinationFinder.FoundElement> nstack);
}

循环的实现，类似于：

public class CombinationFinder {
   private CombinationFinder next;
   private int multiplier;

   public CombinationFinder(int multiplier) {
      this(multiplier, null);
   }
   public CombinationFinder(int multiplier, CombinationFinder next) {
      this.multiplier = multiplier;
      this.next = next;
   }

   public void setNext(CombinationFinder next) {
      this.next = next;
   }

   public CombinationFinder getNext() {
      return next;
   }

   public void search(int max, IDelegate d) {
      Stack<FoundElement> stack = new Stack<FoundElement>();
      this.search(0, max, stack, d);
   }

   private void search(int start, int max, Stack<FoundElement> s, IDelegate d) {
      for (int i=0, val; (val = start + (i*multiplier)) <= max; i++) {
         s.push(i);
         if (null != next) {
            next.search(val, max, s, d);
         } else if (val == max) {
            d.found(s);
         } 
         s.pop();
      }
   } 

   static public class FoundElement {
      private int value;
      private int multiplier;
      public FoundElement(int value, int multiplier) {
         this.value = value;
         this.multiplier = multiplier;
      }
      public int getValue() {
         return value;
      }
      public int getMultiplier() {
         return multiplier;
      }
      public String toString() {
         return value+"*"+multiplier;
      }
   }
}

最后，设置和运行（测试）：

CombinationFinder a1 = new CombinationFinder(20);
CombinationFinder a2 = new CombinationFinder(5);
CombinationFinder a3 = new CombinationFinder(10);

a1.setNext(a2);
a2.setNext(a3);

a1.search(100, new IDelegate() {
   int count = 1;
   @Override
   public void found(List<CombinationFinder.FoundElement> nstack) {
      System.out.print("#" + (count++) + " Found : ");
      for (int i=0; i<nstack.size(); i++) {
         if (i>0) System.out.print(" + ");
            System.out.print(nstack.get(i));
         }
         System.out.println();
      }
   }
});

这将输出36个解决方案。

通过这个概念，你可以有任意数量的内部循环，甚至可以通过继承来定制每一个循环。如果你想重用对象（比如：a1.setNext(a1);），也没有任何问题。

** 更新 **

因为我喜欢monty的解决方案，所以我忍不住去测试了一下，结果稍微调整了一下。

免责声明 所有的功劳都归monty，感谢他的算法。

public class PolynomialSolver {

   private SolverResult delegate;
   private int min = 0;
   private int max = Integer.MAX_VALUE;

   public PolynomialSolver(SolverResult delegate) {
      this.delegate = delegate;
   }

   public SolverResult getDelegate() {
      return delegate;
   }

   public int getMax() {
      return max;
   }

   public int getMin() {
      return min;
   }

   public void setRange(int min, int max) {
      this.min = min;
      this.max = max;
   }

   public void solve(int[] constants, int total) {
      solveImpl(constants, new int[constants.length], total, 0, 0);
   }

   private void solveImpl(int[] c, int[] v, int t, int n, int r) {
      if (n == c.length) { //your end condition for the recursion
         if (r == t) {
            delegate.solution(c, v, t);
         }
      } else if (r <= t){ //keep going
         for (int i=min, j; (i<=max) && ((j=r+c[n]*i)<=t); i++) {
            v[n] = i;
            solveImpl(c, v, t, n+1, j);
         }
      }
   }

   static public interface SolverResult {
      public void solution(int[] constants, int[] variables, int total);
   }

   static public void main(String...args) {

      PolynomialSolver solver = new PolynomialSolver(new SolverResult() {
         int count = 1;
         @Override
         public void solution(int[] constants, int[] variables, int total) {
            System.out.print("#"+(count++)+" Found : ");
            for (int i=0, len=constants.length; i<len; i++) {
               if (i>0) System.out.print(" + ");
               System.out.print(constants[i]+"*"+variables[i]);
            }
            System.out.println(" = " + total);
         }
      });

      // test some constants = total
      solver.setRange(-10, 20);
      solver.solve(new int[] {20, 5, 10}, 100); // will output 162 solutions

   }
}

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的值。这些代码都没有这样做。不过，可以对后面两个代码进行修改来实现这一点，但会失去一些通用性。

Answer 3

递归。

你想要解决的问题大概是这样的：

你当前的例子是：20x₁ + 5x₂ + 10x₃ = 100

所以一般来说，你是在做：A₁x₁ + A₂x₂ + ... + A_nx_n = 总和

你需要传入一个常数数组 {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)