java - 有没有办法加快许多循环的递归？

Question

我基本上是在尝试使用递归并创建了一个小程序，它可以从 10 个项目中找到 0-10 的所有组合({1 个苹果，0 个葡萄}，{2 个苹果，0 个葡萄}，{0 个苹果， 1 颗葡萄}，等等。)。

import java.util.Arrays;
import java.util.List;

public class main {

    public static void main(String[] args) {
        System.out.println("Starting..");
        long startTime = System.currentTimeMillis();
        List<Integer> list_to_start = Arrays.asList(new Integer[] {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}); 
        String[] name_of_list_to_start = new String[] {"Grapes", "Strawberries", "Raspberries", "Blackberries", "Pineapples", "Oranges", "Prunes", "Pears", "cherries", "Peaches", "Apples"};       
        System.out.println(list_to_start.size());
        counter(list_to_start.size(), list_to_start, name_of_list_to_start);
        long endTime = System.currentTimeMillis(); 
        System.out.println("Total execution time: " + (endTime-startTime));
    }

    private static void counter(int length, List<Integer> list_to_start, String[] name_of_list_to_start) {
        // If we've gone through everything then return the results
        if (length == 0) {
            for (int i = 0; i<list_to_start.size(); i++) {
                //System.out.println(name_of_list_to_start[i] + " = " + list_to_start.get(i));
            }
            //System.out.println("****");
            return;
        }   
        //This part basically increments list_to_start and then the above part displays it.
        for (int i = 0; i<=10; i++) {
            if (length != 0 ) {
                list_to_start.set((length-1), i);
                counter((length-1), list_to_start, name_of_list_to_start);
                list_to_start.set((length-1), 0);
            }
        }
    }
}

现在它有 10,000,000,000 次循环 (10^10)，所以我明白为什么它需要很长时间，但我想知道是否有任何 Java 或算法技巧可以用来减少循环次数以加快速度？

我考虑过使用线程/多处理，但仍然需要进行相同数量的循环，这仍然需要很长时间。我不确定这里是否可以使用任何数据结构、排序算法或缓存算法。或者我可以将结果并行添加到数组中，然后将它们放在一起以获得最终结果吗？我不熟悉任何其他现有方法，因此非常欢迎任何有关特定语言技巧或算法解决方案的建议。

更新:为了阐明我在做什么以及性能，我将发布一些示例。要增加处理时间，只需向 list_to_start 添加/删除零(以下结果以毫秒为单位):

1 zero = 0 
2 zero = 1
3 zero = 1
4 zero = 29
5 zero = 37
6 zero = 115
7 zero = 345
8 zero = 1517
9 zero = 23738 (23 seconds)
10 zero = over 30 min. I gave up.

输出(我禁用它以使其运行得更快)是针对 2 个变量(上面的代码运行 10):

Grapes = 0
Strawberries = 0
****
Grapes = 1
Strawberries = 0
****
Grapes = 2
Strawberries = 0
****
Grapes = 3
Strawberries = 0
****
Grapes = 4
Strawberries = 0
****
Grapes = 5
Strawberries = 0
****
Grapes = 6
Strawberries = 0
****
Grapes = 7
Strawberries = 0
****
Grapes = 8
Strawberries = 0
****
Grapes = 9
Strawberries = 0
****
Grapes = 10
Strawberries = 0
****
Grapes = 0
Strawberries = 1
****
Grapes = 1
Strawberries = 1
****
Grapes = 2
Strawberries = 1
****
Grapes = 3
Strawberries = 1
****
Grapes = 4
Strawberries = 1
****
Grapes = 5
Strawberries = 1
****
Grapes = 6
Strawberries = 1
****
Grapes = 7
Strawberries = 1
****
Grapes = 8
Strawberries = 1
****
Grapes = 9
Strawberries = 1
****
Grapes = 10
Strawberries = 1
****
Grapes = 0
Strawberries = 2
****
Grapes = 1
Strawberries = 2
****
Grapes = 2
Strawberries = 2
****
Grapes = 3
Strawberries = 2
****
Grapes = 4
Strawberries = 2
****
Grapes = 5
Strawberries = 2
****
Grapes = 6
Strawberries = 2
****
Grapes = 7
Strawberries = 2
****
Grapes = 8
Strawberries = 2
****
Grapes = 9
Strawberries = 2
****
Grapes = 10
Strawberries = 2
****
Grapes = 0
Strawberries = 3
****
Grapes = 1
Strawberries = 3
****
Grapes = 2
Strawberries = 3
****
Grapes = 3
Strawberries = 3
****
Grapes = 4
Strawberries = 3
****
Grapes = 5
Strawberries = 3
****
Grapes = 6
Strawberries = 3
****
Grapes = 7
Strawberries = 3
****
Grapes = 8
Strawberries = 3
****
Grapes = 9
Strawberries = 3
****
Grapes = 10
Strawberries = 3
****
Grapes = 0
Strawberries = 4
****
Grapes = 1
Strawberries = 4
****
Grapes = 2
Strawberries = 4
****
Grapes = 3
Strawberries = 4
****
Grapes = 4
Strawberries = 4
****
Grapes = 5
Strawberries = 4
****
Grapes = 6
Strawberries = 4
****
Grapes = 7
Strawberries = 4
****
Grapes = 8
Strawberries = 4
****
Grapes = 9
Strawberries = 4
****
Grapes = 10
Strawberries = 4
****
Grapes = 0
Strawberries = 5
****
Grapes = 1
Strawberries = 5
****
Grapes = 2
Strawberries = 5
****
Grapes = 3
Strawberries = 5
****
Grapes = 4
Strawberries = 5
****
Grapes = 5
Strawberries = 5
****
Grapes = 6
Strawberries = 5
****
Grapes = 7
Strawberries = 5
****
Grapes = 8
Strawberries = 5
****
Grapes = 9
Strawberries = 5
****
Grapes = 10
Strawberries = 5
****
Grapes = 0
Strawberries = 6
****
Grapes = 1
Strawberries = 6
****
Grapes = 2
Strawberries = 6
****
Grapes = 3
Strawberries = 6
****
Grapes = 4
Strawberries = 6
****
Grapes = 5
Strawberries = 6
****
Grapes = 6
Strawberries = 6
****
Grapes = 7
Strawberries = 6
****
Grapes = 8
Strawberries = 6
****
Grapes = 9
Strawberries = 6
****
Grapes = 10
Strawberries = 6
****
Grapes = 0
Strawberries = 7
****
Grapes = 1
Strawberries = 7
****
Grapes = 2
Strawberries = 7
****
Grapes = 3
Strawberries = 7
****
Grapes = 4
Strawberries = 7
****
Grapes = 5
Strawberries = 7
****
Grapes = 6
Strawberries = 7
****
Grapes = 7
Strawberries = 7
****
Grapes = 8
Strawberries = 7
****
Grapes = 9
Strawberries = 7
****
Grapes = 10
Strawberries = 7
****
Grapes = 0
Strawberries = 8
****
Grapes = 1
Strawberries = 8
****
Grapes = 2
Strawberries = 8
****
Grapes = 3
Strawberries = 8
****
Grapes = 4
Strawberries = 8
****
Grapes = 5
Strawberries = 8
****
Grapes = 6
Strawberries = 8
****
Grapes = 7
Strawberries = 8
****
Grapes = 8
Strawberries = 8
****
Grapes = 9
Strawberries = 8
****
Grapes = 10
Strawberries = 8
****
Grapes = 0
Strawberries = 9
****
Grapes = 1
Strawberries = 9
****
Grapes = 2
Strawberries = 9
****
Grapes = 3
Strawberries = 9
****
Grapes = 4
Strawberries = 9
****
Grapes = 5
Strawberries = 9
****
Grapes = 6
Strawberries = 9
****
Grapes = 7
Strawberries = 9
****
Grapes = 8
Strawberries = 9
****
Grapes = 9
Strawberries = 9
****
Grapes = 10
Strawberries = 9
****
Grapes = 0
Strawberries = 10
****
Grapes = 1
Strawberries = 10
****
Grapes = 2
Strawberries = 10
****
Grapes = 3
Strawberries = 10
****
Grapes = 4
Strawberries = 10
****
Grapes = 5
Strawberries = 10
****
Grapes = 6
Strawberries = 10
****
Grapes = 7
Strawberries = 10
****
Grapes = 8
Strawberries = 10
****
Grapes = 9
Strawberries = 10
****
Grapes = 10
Strawberries = 10

Answer 1

您可以使用单个循环。

有 11^10 种可能的组合。你可以遍历它们

// String[] names = "Grapes,Strawberries,Raspberries,Blackberries,Pineapples,Oranges,Prunes,Pears,Cherries,Peaches,Apples".split(",");
String[] names = "Pineapples,Oranges,Prunes,Pears,Cherries,Peaches,Apples".split(",");
int maxQuantity = 10;
long combinations = 1;
int quantities = maxQuantity + 1;
for (String _ : names)
    combinations *= quantities;

long start = System.currentTimeMillis();
PrintStream out = new PrintStream(new BufferedOutputStream(new FileOutputStream("combinations.tsv")));
// heading
for (String name : names)
    out.print(name + "\t");
out.println();

for (long comb = 0; comb < combinations; comb++) {
    // comb is a base N number of digits 0 to maxQuantity.
    long c = comb;
    for (int i = 0; i < names.length; i++) {
        long n = c % quantities;
        c /= quantities;
        out.print(n);
        out.print('\t');
    }
    out.println();
}
out.close();
System.out.println("Took " + (System.currentTimeMillis() - start) / 1e3 + " seconds" +
        " to write " + combinations + " combinations");

打印

Took 51.585 seconds to write 19487171 combinations

如果你注释掉这些行，它会将值打印到你得到的文件中

Took 0.065 seconds to write 19487171 combinations

注意:此程序将花费大部分时间进行打印。如果您移除打印部分，它将很快完成。 ;)