Clever Geek Handbook

配列のグループの要素のすべての可能な組み合わせを取得する方法

私は多くの人がこのタスクをググるのを知っています、tk。私自身、最近これに遭遇しました。実用的な解決策が見つからなかったので、自分で解決策を考え出す必要がありました。



だから、紹介データ。配列のグループがあります。次に例を示します。 



models = [ "audi", "bmw", "toyota", "vw" ];
colors = [ "red", "green", "blue", "yellow", "pink" ];
engines = [ "diesel", "gasoline", "hybrid" ];
transmissions = [ "manual", "auto", "robot" ];


ここで、次のような連想配列（マップ）のセットを収集する必要があると想像してみましょう。 



variant1 = { "model": "audi", "color": "red", "engine": "diesel", "transmission": "manual" }
variant2 = { "model": "audi", "color": "red", "engine": "diesel", "transmission": "auto" }
variant3 = { "model": "audi", "color": "red", "engine": "diesel", "transmission": "robot" }
variant4 = { "model": "audi", "color": "red", "engine": "gasoline", "transmission": "manual" }
…
variantN = { "model": "vw", "color": "pink", "engine": "hybrid", "transmission": "robot" }


簡略化した形式では、このような作業のアルゴリズムは次のようになります。 



for(i1 = 0; i1 < models.length; i1 ++){ //  
    for(i2 = 0; i2 < colors.length; i2 ++){ //   
        for(i3 = 0; i3 < engines.length; i3 ++){ //   
            for(i4 = 0; i4 < transmissions.length; i4 ++){ //   
                 variant = {
                      "model": models[i1],
                      "color": colors[i2],
                      "engine": engines[i3],
                      "transmission": transmissions[i4],
                 }
            }
        }
    }
}


それら。実際、各セットを別のセット内にネストし、ループで繰り返します。今では、特定の数のセットに縛られることなく同じことを行う方法を理解する必要があります。



まず、用語を定義しましょう。



パラメータは、モデル、色など、設定された要素の名前です。

パラメータ要素のセットは、パラメータに割り当てられたリストです（たとえば、["audi"、 "bmw"、 "toyota"、 "vw"]）

。セット要素は、リストの個別の要素です。たとえば、audi、bmw、red、blueなどです。

結果セット-生成するもの



それはどのように見えるでしょうか？パラメータ（モデル、色など）の反復を制御するイテレータの条件付きカウンタを1つの位置だけシフトする関数が必要です。この関数内では、カウンターをシフトすることに加えて、パラメーター要素（audi、bmw ...; red、blue ...など）を繰り返し処理します。そして、このネストされたループ内で、関数はそれ自体を再帰的に呼び出します。



以下は、コメント付きのJavaでの実用的な例です。 



public class App {

    public static void main(String[] args) {
        Map<String, List<String>> source = Map.of(
            "model", Arrays.asList("audy", "bmw", "toyota", "vw"),
            "color", Arrays.asList("red", "green", "blue", "yellow", "pink"),
            "engine", Arrays.asList("diesel", "gasoline", "hybrid"),
            "transmission", Arrays.asList("manual", "auto", "robot")
        );

        Combinator<String, String> combinator = new Combinator<>(source);
        List<Map<String, String>> result = combinator.makeCombinations();

        for(Map variant : result){
            System.out.println(variant);
        }
    }

    public static class Combinator<K,V> {

        //       
        private Map<K, List<V>> sources;

        //   .     
        //ListIterator, ..    previous
        private ListIterator<K> keysIterator;

        //       
        //  -  ,   -     
        private Map<K, Integer> counter;

        //    
        private List<Map<K,V>> result;


        public Combinator(Map<K, List<V>> sources) {
            this.sources = sources;
            counter = new HashMap<>();
            keysIterator = new ArrayList<>(sources.keySet())
                    .listIterator();
        }

        //     
        public List<Map<K,V>> makeCombinations() {
            result = new ArrayList<>();
            //  
            loop();
            return result;
        }

        private void loop(){
            //,      
            if(keysIterator.hasNext()){

                //  
                K key = keysIterator.next();

                //   (  ,
                //     )
                counter.put(key, 0);


                //  
                while(counter.get(key) < sources.get(key).size()){
                    //   loop     
                    loop();

                    //   
                    counter.put(key, counter.get(key) + 1);
                }

                //      -    
                keysIterator.previous();
            }
            else{
                //    , ..     
                //   
                fill();
            }
        }

        //      
        private void fill() {
            Map<K,V> variant = new HashMap<>();

            //  
            for(K key : sources.keySet()){
                //     
                Integer position = counter.get(key);

                //   
                variant.put(key, sources.get(key).get(position));
            }

            result.add(variant);
        }

    }

}


More articles:


All Articles