これが私の問題の背景です（宿題ではありません）。食料品店で 4 つのアイテムから選択する必要があり、それぞれの何パーセントがバスケットに収まるかを知りたいのですが、どのアイテムも 20% 未満で 60% を超えないように範囲を設定しています。現在、プログラムは 0 から開始し、徐々に上に向かって動作します (0 はこの場合の最小値 20 であり、それより上の値は最小値を何パーセント上回っているかに等しい)。上記の最小20,0,0,0]値 20 の例を使用すると、[ は 40 + 20 + 20 + 20 = 100 になり、すべてのアイテムの順列が生成されます。
[20,0,0,0]実行した後、（上記の例を使用して）最初のアイテムがで、最後のアイテムが であることに気付きました[0,0,0,20]。すべての結果を逆バージョンと比較してテストしましたが、それらはすべて存在するため、リストの半分だけを処理し、結果を取得して反転させることで、処理時間を半分に短縮できる方法を見つけることができると考えました。プログラムがまだ結果を生成しているときに、逆の一致をチェックし始めたときに問題が発生しました。反転して複製を開始する単一のポイントがないようです（正確に半分がそれを行うことを望んでいました）。ここに結果の出力があります、最初の列は結果自体で、2 番目の列はそれを反転したバージョンの indexOf です (-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
編集：プログラムは重複を生成していません。それは、最終的には逆転するように思われる予測を生成します。逆順列がすべて既存の結果と一致するポイントを捉えたいので、データをさらに処理する代わりに、既存の結果を元に戻すことができます。私が説明していることについては、上記の出力を確認してください。