Cara mendapatkan semua kemungkinan kombinasi elemen dari sekelompok array

Saya tahu banyak orang meng-google tugas ini, tk. Saya sendiri baru-baru ini mengalami ini. Karena saya tidak pernah menemukan solusi yang berhasil, saya harus mencari solusi sendiri.



Jadi, data pengantar. Kami memiliki sekelompok array, misalnya:

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

Sekarang mari kita bayangkan bahwa kita perlu mengumpulkan satu set array asosiatif (peta) seperti ini:

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" }

Dalam bentuk yang disederhanakan, algoritme untuk pekerjaan tersebut terlihat seperti ini:

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],
                 }
            }
        }
    }
} 

Itu. pada kenyataannya, kita menumpuk setiap set di dalam set lain, dan mengulanginya dalam satu lingkaran. Sekarang tinggal mencari cara untuk melakukan hal yang sama tanpa terikat pada sejumlah set tertentu.



Pertama, mari kita tentukan istilahnya:



Parameter adalah nama elemen yang ditetapkan, misalnya model, warna, dll.

Satu set elemen parameter adalah daftar yang ditetapkan ke parameter (misalnya, ["audi", "bmw", "toyota", "vw"])

Elemen set adalah elemen terpisah dari daftar, misalnya, audi, bmw, merah, biru, dll.

Kumpulan Hasil - Yang Harus Kita Hasilkan



Akan terlihat seperti apa? Kita membutuhkan sebuah fungsi, yang setiap panggilannya akan bergeser dengan satu posisi penghitung bersyarat dari iterator yang mengontrol iterasi parameter (model, warna, dll.). Di dalam fungsi ini, selain menggeser penghitung, ini akan melakukan iterasi terhadap elemen parameter (audi, bmw ...; merah, biru ... dll.). Dan di dalam loop bersarang ini, fungsi kita akan memanggil dirinya sendiri secara rekursif.



Berikut ini adalah contoh kerja di Java dengan komentar:

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);
        }

    }

}