这是我的问题的一些背景（不是家庭作业）。我在杂货店有 4 种物品可供选择，我想弄清楚我的购物篮中每种物品的百分比，但我设置了一个范围，即任何物品都不能低于 20% 且不超过 60%。该程序当前从 0 开始并向上运行（在这种情况下，0 是最小值 20，高于它的任何值都等于它是最小值的百分比）。使用上面最小值为 20 的示例，那么 [20,0,0,0]将等于 40 + 20 + 20 + 20 = 100 并为所有项目生成排列。
运行后，我意识到（使用上面的例子）第一项是[20,0,0,0]，最后一项是[0,0,0,20]。我通过将所有结果与自身的反向版本进行比较来测试它，它们都存在，所以我想我可以找到一种方法，通过只处理一半列表然后获取结果并将它们翻转过来，将我的处理时间缩短一半。当我开始检查反向匹配时，我遇到了一个问题，而程序仍在生成结果，似乎没有一个点可以翻转并开始复制（我希望它正好在一半时会这样做）。这是结果的输出，第一列是结果本身，第二列是它的反转版本的索引（-1 表示未找到）。它从全 -1 开始，然后开始找到一些反向匹配，但仍然有许多 -1，然后它最终过渡到所有重复的结果，但它似乎以可预测的清晰方式进行。
我的最终目标是使用更大的列表，并且我试图找到一种方法来生成尽可能多的数据，因此任何关于如何识别模式或其他速度改进的建议都会很棒。我在想，在这种情况下，我要么需要一种方法来识别模式一旦完全开发（即不再有机会-1），要么调整算法以便它以完全切换而不是缓慢的部分变化的顺序生成。
如果有帮助，这是我正在使用的代码（注意：项目和范围的数量是变量，所以我试图找到一个通用模式，而不是特定于任何硬数字）：
import java.util.*;
public class Distributor {
//correct output is 1771
private ArrayList<int[]> result = new ArrayList <int[]> ();
/*
*/
public Distributor (final String [] names, int [] low, int [] high)
{
final int rest = 100;
int minimum = 0;
for (int l : low)
minimum += l;
int [] sizes = new int [names.length];
distribute (0, low, high, rest - minimum, sizes);
System.out.println ("total size of results are " + result.size ());
}
public static void main (String [] args) {
System.out.println("starting..Hold on!!");
final String [] names = new String [] {"a", "b", "c", "d"}; //name of items
int [] low = new int [names.length];
int [] high = new int [names.length];
Arrays.fill(low, 20); //auto fill the range of items with a min/max range
Arrays.fill(high, 60);
new Distributor (names, low, high);
}
/*
distribute the rest of values over the elements in sizes, beginning with index i.
*/
void distribute (int i, int [] low, int [] high, final int rest, int [] sizes) {
if (i == sizes.length - 1) { //this area procesess the final item and adds it to the solution queue
if (rest < high [i]) {
sizes[i] = rest;
checkResultsDuringRuntime(Arrays.copyOf (sizes, sizes.length),result);
result.add (Arrays.copyOf (sizes, sizes.length));
}
}
else {
int StartLoop = 0;
//this area checks if the remaining value can be reached used the max values of remaining items
//if its not possible then the current min range of the loop must be increased
if ( rest > (low.length-(i + 1))*high[i]) {
System.out.println("rest is higher than high");
StartLoop = (rest - (low.length-(i + 1))*high[i]);
}
//this area runs a loop for each coeffient and then sends it back to this function to further processing
for (int c = StartLoop;
c <= java.lang.Math.min (high [i] - low [i], rest);
++c) {
sizes [i] = c;
distribute (i + 1, low, high, rest - c, sizes);
}
}
}
private static void checkResultsDuringRuntime(int[] defaultlist, ArrayList<int[]> result2) {
//check results list for list
//first lets flip the list around
int[] ReversedList = new int[defaultlist.length];
for (int x = defaultlist.length-1, y=0; x>=0;x--, y++) {
ReversedList[y] = defaultlist[x];
}
int MatchLocation = -1;
for (int[] item : result2) {
if ( Arrays.toString(item).equals(Arrays.toString(ReversedList)))
{
//System.out.println("theres a match");
MatchLocation = result2.indexOf(item);
}
}
System.out.println(Arrays.toString(defaultlist) + " = " + MatchLocation);
}
}
输出： http: //pastebin.com/6vXRvVit
编辑：该程序不会生成重复项。它的产生似乎最终会逆转。我想尝试捕获反向排列将全部匹配现有结果的点，因此我无需进一步处理数据，而是可以反转现有结果。查看上面的输出以了解我所描述的内容。