如何获得一组数组元素的所有可能组合

我知道很多人用谷歌搜索这个任务，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],
                 }
            }
        }
    }
} 

那些。实际上，我们将每个集合嵌套在另一个集合中，并在一个循环中对其进行迭代。现在剩下的工作是弄清楚如何在不绑定特定数量的集合的情况下执行相同的操作。



首先，让我们定义术语：



参数是set元素的名称，例如，模型，颜色等。

参数元素集是分配给参数的列表（例如[“ audi”，“ bmw”，“ toyota”，“ vw”]）

。set项是列表的单独元素，例如audi，bmw，红色，蓝色等。

结果集-我们应该生成什么



看起来如何？我们需要一个函数，每个函数的调用将使迭代器的条件计数器移动一个位置，该条件计数器控制参数（模型，颜色等）的迭代。在此函数内部，除了移位计数器外，还将迭代参数的元素（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);
        }

    }

}