I'm basically trying to play with recursions and created a small program that finds all the combinations from 0-10 of 10 items({1 apple, 0 grapes}, {2 apple, 0 grapes}, {0 apple, 1 grapes}, etc..) .
我基本上尝试使用递归并创建了一个小程序,可以找到10个项目中的0-10个所有组合({1 apple,0 grape},{2 apple,0 grape},{0 apple,1 grapes}等等。)。
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);
}
}
}
}
Right now it has 10,000,000,000 loops(10^10) so I understand why it takes long, but I'm wondering is there any Java or algorithm tricks I can use to reduce the number of loops to speed it up?
现在它有10,000,000,000个循环(10 ^ 10)所以我理解为什么它需要很长时间,但我想知道是否有任何Java或算法技巧我可以用来减少循环次数来加速它?
I've thought of using threading/multiprocessing but the same number of loops will still need to happen which will still take a long time. I'm not sure if there's any data structures, sorting algorithms or caching algorithms that could be employed here. or can I add the results to an array in parallel and then bring them together for the final results? I'm not familiar with any other existing approaches so any suggestions of language specific tricks or algorithm solutions are very welcomed.
我曾想过使用线程/多处理,但仍需要相同数量的循环,这仍然需要很长时间。我不确定这里是否有任何数据结构,排序算法或缓存算法。或者我可以将结果并行添加到数组中,然后将它们组合在一起以获得最终结果吗?我不熟悉任何其他现有方法,因此非常欢迎任何语言特定技巧或算法解决方案的建议。
Update: To clarify what I'm doing and the performance I'll post a few examples. To increase processing time, simply add/remove zeros to list_to_start(results below are in miliseconds):
更新:为了澄清我正在做什么和性能,我将发布几个例子。要增加处理时间,只需在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.
The output(which I disabled to make it run a bit faster) is this for 2 variables(the above code is running 10):
输出(我禁用它使它运行得更快)是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
2 个解决方案
#1
3
You can use a single loop.
您可以使用单个循环。
There are 11^10 possible combinations. you can iterate through them all
有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");
prints
Took 51.585 seconds to write 19487171 combinations
if you comment out the lines were it prints the values to a file you get
如果你注释掉这些行,它会将值打印到你得到的文件中
Took 0.065 seconds to write 19487171 combinations
Note: This program will spend most of its time printing. If you remove the printing part it will finish very quickly. ;)
注意:此程序将花费大部分时间进行打印。如果您取下打印部件,它将很快完成。 ;)
#2
0
Assuming that you will only care about the first instance of the same item you can break the loop when you match to avoid extra loops. Can you provide a better break down of what the 'problem' is here (what your program is supposed to do)?
假设你只关心同一个项目的第一个实例,你可以在匹配时打破循环以避免额外的循环。你能否更好地分解这里的'问题'(你的计划应该做什么)?
#1
3
You can use a single loop.
您可以使用单个循环。
There are 11^10 possible combinations. you can iterate through them all
有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");
prints
Took 51.585 seconds to write 19487171 combinations
if you comment out the lines were it prints the values to a file you get
如果你注释掉这些行,它会将值打印到你得到的文件中
Took 0.065 seconds to write 19487171 combinations
Note: This program will spend most of its time printing. If you remove the printing part it will finish very quickly. ;)
注意:此程序将花费大部分时间进行打印。如果您取下打印部件,它将很快完成。 ;)
#2
0
Assuming that you will only care about the first instance of the same item you can break the loop when you match to avoid extra loops. Can you provide a better break down of what the 'problem' is here (what your program is supposed to do)?
假设你只关心同一个项目的第一个实例,你可以在匹配时打破循环以避免额外的循环。你能否更好地分解这里的'问题'(你的计划应该做什么)?