合并串列串列

我們有串列串列：

List<List<String>> source = List.of(
                List.of("a", "b"),
                List.of("A", "B", "C"),
                List.of("1", "2", "3", "4"));

source.size()可以是隨機的，每個子串列的大小也是隨機的。

并且演算法應該將其轉換為一個List<String>進一步的順序：

List<String> transform(List<List<String>> source) {
    // ... Implementation ...
    return List.of ("aA1", "aA2", "aA3", "aA4",
                    "aB1", "aB2", "aB3", "aB4",
                    "aC1", "aC2", "aC3", "aC4",
                    "bA1", "bA2", "bA3", "bA4",
                    "bB1", "bB2", "bB3", "bB4",
                    "bC1", "bC2", "bC3", "bC4");;
}

如何實作上述transform獲取結果串列的方法？

uj5u.com熱心網友回復：

它可以通過一點遞回來完成，前提是您沒有太多的專案，source也沒有從每個子串列的長度中得到組合爆炸。

import java.util.ArrayList;
import java.util.List;

public class AllCombinations {

    static void AddCombination(List<List<String>> source, int depth, 
            String prefix, List<String> output) {
        for (String layer : source.get(depth)) {
            String str = prefix   layer;
            if (depth < source.size() - 1) {
                AddCombination(source, depth   1, str, output);
            } else {
                output.add(str);
            }
        }
    }
    
    public static void main(String[] args) {
        List<List<String>> source = List.of(
                List.of("a", "b"),
                List.of("A", "B", "C"),
                List.of("1", "2", "3", "4"));
        
        List<String> output = new ArrayList<>();
        
        AddCombination(source, 0, "", output);
        
        output.forEach(System.out::println);
    }
}

uj5u.com熱心網友回復：

我確信有更好的方法可以做到這一點，但我是這樣做的：

public static Collection<String> allPermutations(List<List<String>> source) {
    
    Set<String> allPermutations = new TreeSet<>();

    for (List<String> list : source) {
        if (allPermutations.isEmpty()) {
            allPermutations.addAll(list);
        } else {
            Set<String> newValues = new HashSet<>();
            for (String s : allPermutations) {
                for (String v : list) {
                    newValues.add(s v);
                }
            }
            allPermutations.clear();
            allPermutations.addAll(newValues);
        }
    }

    return allPermutations;
}

uj5u.com熱心網友回復：

在發布我的解決方案之前，我通常會等待 O/P 顯示更多參與。但是，既然已經有兩個答案，這是我的“老狗”解決方案。它類似于 Ryan 的那個：

package cartesianproduct;

import java.util.Collection;
import java.util.LinkedList;
import java.util.List;

public class CartesianProduct {
        
    public static Collection<String> 
        cartesianProduct (Collection<String> product,
                          Collection<String> m1,
                          Collection<String> m2) {
            
            product.clear ();
            if (m1.isEmpty() ) { 
                product.addAll(m2);
                return product;
            } 
            if (m2.isEmpty()) {
                product.addAll (m1);
                return product;
            }
            for (String str1: m1) {
                for (String str2: m2) {
                    product.add (str1.concat(str2));
                }
            }            
            return product;
        }  

    public static void main(String[] args) {
        List<List<String>> source = List.of(
                List.of("a", "b"), 
                List.of("A", "B", "C"),
                List.of("1", "2", "3", "4"));
        
        Collection<String> theProduct = new LinkedList<> ();  
        for (List<String> a: source) {      
              theProduct = (LinkedList<String>) cartesianProduct 
                      (new LinkedList<> (), theProduct, a);
        }
        System.out.println (theProduct.toString());
    }   
}

這是輸出： [aA1, aA2, aA3, aA4, aB1, aB2, aB3, aB4, aC1, aC2, aC3, aC4, bA1, bA2, bA3, bA4, bB1, bB2, bB3, bB4, bC1, bC2, bC3, bC4]

上面的部分解決方案在main. 要退出回圈main，您可以添加此方法：

public static Collection<String> cartesianProduct (
        Collection<String> destination,
        List<List<String>> source ) {
        Collection<String> product = new LinkedList<> ();
        for (Collection<String> s :source) {
            product = cartesianProduct (new LinkedList<> (), 
                       product, s);
        }
        destination.clear();
        destination.addAll(product);
        return destination; 
}

并將回圈替換main為

    theProduct = cartesianProduct(theProduct, source);

.

標籤：爪哇 算法

上一篇：對未排序陣列中最大的n個數求和

下一篇：MaxPairwiseProduct問題整數溢位