2

これが私の問題の背景です(宿題ではありません)。食料品店で 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

編集:プログラムは重複を生成していません。それは、最終的には逆転するように思われる予測を生成します。逆順列がすべて既存の結果と一致するポイントを捉えたいので、データをさらに処理する代わりに、既存の結果を元に戻すことができます。私が説明していることについては、上記の出力を確認してください。

4

2 に答える 2

1

質問を完全には理解していませんが、同様の問題を解決するための秘訣があります。たとえば、1から6までの3つの数値[1、4、2]を生成したいが、重複を無視したいとします。つまり、[1,2,3] = [3,2,1]

方法は次のとおりです。

for(int i=1; i <= 6; i++) {
    for(int j=i+1; j <= 6; j++) {
        for(int k=j+1; k <= 6; k++) {
            System.out.println(i+","+j+","+k);
            }
        }
    }

出力にはすべての可能性が含まれますが、重複する順列は含まれません。

編集-これが出力です...

1,2,3
1,2,4
1,2,5
1,2,6
1,3,4
1,3,5
1,3,6
1,4,5
1,4,6
1,5,6
2,3,4
2,3,5
2,3,6
2,4,5
2,4,6
2,5,6
3,4,5
3,4,6
3,5,6
4,5,6

編集2-制限が20と60の4つのアイテムがあるOPの問題の場合、101,270の順列があります。これは、整数パーセントが許容可能であることを前提としています。つまり、25.1%ではなく25%です。

編集3-うん、これは楽しい。OPは、パーセンテージを合計して100にする必要があると述べました。私はそれを見逃しました。108の可能性があります。彼らです:

1 : [20,20,20,40]
2 : [20,20,21,39]
3 : [20,20,22,38]
4 : [20,20,23,37]
5 : [20,20,24,36]
6 : [20,20,25,35]
7 : [20,20,26,34]
8 : [20,20,27,33]
9 : [20,20,28,32]
10 : [20,20,29,31]
11 : [20,20,30,30]
12 : [20,21,21,38]
13 : [20,21,22,37]
14 : [20,21,23,36]
15 : [20,21,24,35]
16 : [20,21,25,34]
17 : [20,21,26,33]
18 : [20,21,27,32]
19 : [20,21,28,31]
20 : [20,21,29,30]
21 : [20,22,22,36]
22 : [20,22,23,35]
23 : [20,22,24,34]
24 : [20,22,25,33]
25 : [20,22,26,32]
26 : [20,22,27,31]
27 : [20,22,28,30]
28 : [20,22,29,29]
29 : [20,23,23,34]
30 : [20,23,24,33]
31 : [20,23,25,32]
32 : [20,23,26,31]
33 : [20,23,27,30]
34 : [20,23,28,29]
35 : [20,24,24,32]
36 : [20,24,25,31]
37 : [20,24,26,30]
38 : [20,24,27,29]
39 : [20,24,28,28]
40 : [20,25,25,30]
41 : [20,25,26,29]
42 : [20,25,27,28]
43 : [20,26,26,28]
44 : [20,26,27,27]
45 : [21,21,21,37]
46 : [21,21,22,36]
47 : [21,21,23,35]
48 : [21,21,24,34]
49 : [21,21,25,33]
50 : [21,21,26,32]
51 : [21,21,27,31]
52 : [21,21,28,30]
53 : [21,21,29,29]
54 : [21,22,22,35]
55 : [21,22,23,34]
56 : [21,22,24,33]
57 : [21,22,25,32]
58 : [21,22,26,31]
59 : [21,22,27,30]
60 : [21,22,28,29]
61 : [21,23,23,33]
62 : [21,23,24,32]
63 : [21,23,25,31]
64 : [21,23,26,30]
65 : [21,23,27,29]
66 : [21,23,28,28]
67 : [21,24,24,31]
68 : [21,24,25,30]
69 : [21,24,26,29]
70 : [21,24,27,28]
71 : [21,25,25,29]
72 : [21,25,26,28]
73 : [21,25,27,27]
74 : [21,26,26,27]
75 : [22,22,22,34]
76 : [22,22,23,33]
77 : [22,22,24,32]
78 : [22,22,25,31]
79 : [22,22,26,30]
80 : [22,22,27,29]
81 : [22,22,28,28]
82 : [22,23,23,32]
83 : [22,23,24,31]
84 : [22,23,25,30]
85 : [22,23,26,29]
86 : [22,23,27,28]
87 : [22,24,24,30]
88 : [22,24,25,29]
89 : [22,24,26,28]
90 : [22,24,27,27]
91 : [22,25,25,28]
92 : [22,25,26,27]
93 : [22,26,26,26]
94 : [23,23,23,31]
95 : [23,23,24,30]
96 : [23,23,25,29]
97 : [23,23,26,28]
98 : [23,23,27,27]
99 : [23,24,24,29]
100 : [23,24,25,28]
101 : [23,24,26,27]
102 : [23,25,25,27]
103 : [23,25,26,26]
104 : [24,24,24,28]
105 : [24,24,25,27]
106 : [24,24,26,26]
107 : [24,25,25,26]
108 : [25,25,25,25]

60の上限が大きすぎることに気付きました。他の3つのアイテムは、最小値である20%で追加できません。それは120%になります。

于 2012-05-26T23:35:34.213 に答える
0

偽陰性が発生しないことを保証する ブルームフィルターを使用することをお勧めします。

誤検知は可能ですが、誤検知はできません。つまり、クエリは「セット内(間違っている可能性があります)」または「間違いなくセット内にない」のいずれかを返します

Javaの実装

ソースコード

もちろん、問題は配列が等しいかどうかを比較することです。これを行うことをお勧めします。

Arrays.sort(arrayToCompare);  
Arrays.equals(initialArray,arrayToCompare);

ソートのオーバーヘッドを取りますが、2つの配列が等しいかどうかがわかるため、以前のブルームフィルターで十分です。

于 2012-05-26T23:31:28.357 に答える