二維數組的排列

Question

下面是關於排列的另一個問題。我盡我所能來盡我所能來制定我的問題。如果您有不明白的地方，請隨時提問。

我有一個列表，包含一個列表，包含一個列表，包含一個符號。

List<List<List<Symbol>>> list = new ArrayList<List<List<Symbol>>>(); 

符號類只是一個值，並跟蹤我創建的一些重要特徵。結構中的所有符號都彼此不同。

但是也有一些困難，因爲剛剛切換各種不同方式的地方，因爲...

第一個列表是一種包裝了整個事情的。它包含兩個包含符號的列表的分組。這是因爲當包含在一個分組中時，符號不應該彼此分離。

第二個列表始終長度爲2，並且每個列表都包含一個唯一符號列表。至於爲什麼是兩個，不要問我這個問題。這個程序有能力處理這個列表的長度大於兩個，這將是很好的。

第三個列表包含所有符號，並且如上所述，每個包裝中有兩個符號。

我想要的是產生所有可能的排列並分析它們。也就是說，我希望符號切換成所有可能的組合，同時仍然包含在其各自的列表中。

這可能看起來像這樣（用僞代碼寫成，描述了上面提到的類似列表的結構）。

[[a, b, c], [d, e, f]], 
[[g, h, i, j], [k, l, m, n]], 
[[o, p], [q, r]], 
[[s, t, u], [v, x, y]], 

一個例子是什麼（可能是成千上萬）的排列可能是，這是。

[[c, a, b], [d, f, e]], 
[[g, h, j, i], [k, l, m, n]], 
[[o, p], [q, r]], 
[[s, t, u], [v,y, x]], 

我已經試過到目前爲止是把這些變成一個很好的舊傳統的排列方法（如果你願意或列表），對單個陣列的作品，並試圖修改與多維工作陣列。當然有一個很好和簡單的方法來做到這一點，最好使用遞歸。如果沒有方法，那完全沒問題。

再次，如果您有任何問題超出我剛寫的內容，請隨時發表評論。

親切的問候，

Answer 1

這是一個遞歸解決方案。 permutationsList可以帶有任意數量的維度的列表。順便說一句。你給出的例子有近300萬個排列組合。我的程序需要幾秒鐘來計算它們。

import java.util.*; 

public class Perm { 
    static <T> List<List<T>> permutations(List<T> list) { 
    if(list.isEmpty()) return new LinkedList<>(); 
    List<List<T>> result = new LinkedList<>(); 
    for(int i = 0; i < list.size(); i++) { 
     T elem = list.get(i); 
     List<T> copy = new LinkedList<>(list); 
     copy.remove(i); 
     List<List<T>> permRest = permutations(copy); 
     if(permRest.isEmpty()) permRest.add(new LinkedList<>()); 
     for(List<T> perm: permRest) { 
     List<T> permCopy = new LinkedList<>(perm); 
     permCopy.add(0, elem); 
     result.add(permCopy); 
     } 
    } 
    return result; 
    } 

    @SuppressWarnings("unchecked") 
    static List<List> permutationsLists(List list) { 
    if(list.size() == 0) { 
     return new LinkedList<>(); 
    } if(!(list.get(0) instanceof List)) { 
     return permutations(list); 
    } else { 
     List<List> permutationsFirst = permutationsLists((List)list.get(0)); 
     List<List> permutationsRest = (List<List>)permutationsLists(list.subList(1, list.size())); 
     if(permutationsRest.size() == 0) permutationsRest.add(new LinkedList()); 
     List<List> result = new LinkedList<>(); 
     for(List pf: permutationsFirst) { 
     for(List pr: permutationsRest) { 
      List copy = new LinkedList(pr); 
      copy.add(0, pf); 
      result.add(copy); 
     } 
     } 
     return result; 
    } 
    } 

    public static void main(String[] args) { 
    /* 
    List<List<List<String>>> list = Arrays.asList(
     Arrays.asList(Arrays.asList("a", "b", "c"), Arrays.asList("d", "e", "f")), 
     Arrays.asList(Arrays.asList("g", "h", "i", "j"), Arrays.asList("k", "l", "m", "n")), 
     Arrays.asList(Arrays.asList("o", "p"), Arrays.asList("q", "r")), 
     Arrays.asList(Arrays.asList("s", "t", "u"), Arrays.asList("v", "w", "x")) 
    ); 
    */ 
    List<List<Integer>> list = Arrays.asList(Arrays.asList(1,2,3), Arrays.asList(4,5)); 
    System.out.println(permutationsLists(list)); 
    } 
} 

編輯： 這是一個使用流的解決方案。這是非常有效的，可以產生大量的排列而不用太多的內存。順便說一句，你可以將流轉換爲迭代器與iterator()方法。

import java.util.*; 
import java.util.stream.Stream; 
import java.util.stream.IntStream; 

public class Perm { 

    static <T> Stream<List<T>> permutations(List<T> list) { 
    if(list.isEmpty()) return Stream.empty(); 
    return IntStream.range(0, list.size()).boxed().flatMap(i -> { 
     T elem = list.get(i); 
     List<T> copy = new LinkedList<>(list); 
     copy.remove((int)i); 
     Stream<List<T>> permRest = copy.isEmpty()?Stream.of(new LinkedList<>()):permutations(copy); 
     return permRest.map(perm -> { 
     List<T> permCopy = new LinkedList<>(perm); 
     permCopy.add(0, elem); 
     return permCopy; 
     }); 
    }); 
    } 

    @SuppressWarnings("unchecked") 
    static <T> Stream<List<T>> permutationsLists(List<T> list) { 
    if(list.size() == 0) { 
     return Stream.empty(); 
    } if(!(list.get(0) instanceof List)) { 
     return permutations(list); 
    } else { 
     List rawList = list; 
     Stream<List> permutationsFirst = permutationsLists((List)list.get(0)); 

     return permutationsFirst.flatMap(pf -> { 
     Stream<List> permutationsRest = list.size() < 2?Stream.of(new LinkedList()):permutationsLists(rawList.subList(1, list.size())); 
     return permutationsRest.map(pr -> { 
      List<T> copy = new LinkedList<>(pr); 
      copy.add(0, (T)pf); 
      return copy; 
     }); 
     }); 
    } 
    } 

    public static void main(String[] args) throws Exception { 
    List<List<List<String>>> list = Arrays.asList(
     Arrays.asList(Arrays.asList("a", "b", "c"), Arrays.asList("d", "e", "f")), 
     Arrays.asList(Arrays.asList("g", "h", "i", "j"), Arrays.asList("k", "l", "m", "n")), 
     Arrays.asList(Arrays.asList("o", "p"), Arrays.asList("q", "r")), 
     Arrays.asList(Arrays.asList("s", "t", "u"), Arrays.asList("v", "w", "x")) 
    ); 

    Stream<List<List<List<String>>>> result = permutationsLists(list); 
    result.forEach(p -> System.out.println(p)); 
    } 
}