كيفية الحصول على كل التركيبات الممكنة لعناصر مجموعة من المصفوفات

أعلم أن العديد من الأشخاص يستخدمون Google هذه المهمة ، 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 ، الأحمر ، الأزرق ، إلخ.

مجموعات النتائج - ما يجب أن نولده



كيف سيبدو؟ نحن بحاجة إلى وظيفة ، كل استدعاء منها سينتقل بموضع واحد إلى العداد الشرطي للمكرر الذي يتحكم في تكرار المعلمات (النموذج ، اللون ، إلخ). داخل هذه الوظيفة ، بالإضافة إلى إزاحة العداد ، فإنه سيتكرر على عناصر المعامل (أودي ، بي ام دبليو ... ؛ أحمر ، أزرق ... إلخ). وداخل هذه الحلقة المتداخلة ، ستستدعي الدالة نفسها بشكل متكرر.



ما يلي هو مثال عملي في 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);
        }

    }

}