如何獲取包含列表

Question

正如你可能已經與冠軍理解的列表中的每個列表中的一個要素的所有列表的列表，我需要在這裏一些聰明的想法:)

我有一個List<List<Object>>對象。如果您認爲對象對象爲整數，你可以看到它是這樣的：

{{1,2},{10,20,30},{100}} 

我需要包含每個列表中的一個要素的所有可能的名單，就是想出這樣的：

{{1,10,100},{1,20,100},{1,30,100},{2,10,100},{2,20,100},{2,30,100}} 

你當然不知道在編譯時的名單將有多少項目包含，所以你不能依靠for圈的重疊......

你會怎麼想出這個？時間限制與我的問題無關，因爲列表可能會包含很少的元素。

Answer 1

我不會實現它，但這裏有一個遞歸算法的想法：

• 如果我們面對的是包含元素（即例如{{1,2,3}}）的一個列表的列表，那麼結果就是 - 當然，每個列表都包含一個元素（例如：{{1},{2},{3}}
• 如果我們列表中有多個列表，我們做一個遞歸調用算法，我們從這個遞歸調用中得到所有列表，列表的第一個列表中的元素與遞歸調用中的每個列表。

這裏的原始Python代碼：

def combiner(ll): 
    if len(ll)==1: 
     return [[x] for x in ll[0]] # base case 
    firstlist = ll[0] 
    result = [] 
    for i in combiner(ll[1:]): # recursive call 
     for firstelem in firstlist: 
      result.append([firstelem]+i) # combining lists 
    return result 

Answer 2

迭代算法。

public class A { 
    public static List<List<Integer>> combinations(List<List<Integer>> inputList) { 
     List<List<Integer>> result = new LinkedList<List<Integer>>(); 
     for (Integer i : inputList.get(0)) { 
      List<Integer> temp = new ArrayList<Integer>(1); 
      temp.add(i); 
      result.add(temp); 
     } 
     for (int i = 1; i < inputList.size(); i++) { 
      result = make(result, inputList.get(i)); 
     } 
     return result; 
    } 

    private static List<List<Integer>> make(List<List<Integer>> in, List<Integer> n) { 
     List<List<Integer>> res = new LinkedList<List<Integer>>(); 
     for (List<Integer> l : in) { 
      for (Integer i : n) { 
       List<Integer> cur = new ArrayList<Integer>(l.size() + 1); 
       cur.addAll(l); 
       cur.add(i); 
       res.add(cur); 
      } 
     } 
     return res; 
    } 
    public static void main(String[] args) { 
     List<List<Integer>> inputList = new ArrayList(); 
     inputList.add(new ArrayList<Integer>() {{ 
      add(1); 
      add(2); 
     }}); 
     inputList.add(new ArrayList<Integer>() {{ 
      add(10); 
      add(20); 
      add(30); 
     }}); 
     inputList.add(new ArrayList<Integer>() {{ 
      add(100); 
     }}); 
     System.out.println(combinations(inputList)); 
    } 
} 

*請注意，該號碼不適用於製作！您應該使用ArrayList替換LinkedList，並使用初始大小，進行檢查等。

upd提供使用示例。有一些代碼改進。但它仍然只是草案。我不建議你在真正的任務中使用它。

Answer 3

爲了完整起見，您正在搜索的內容被稱爲笛卡爾產品您的列表，因爲我們的結果列表的大小是單個列表大小的乘積。

---

編輯：這是一個實現它可以用於Iterables的任意Iterables，並創建一個List的Iterable。它會在迭代過程中懶散地創建元素，所以它適用於真正的大型產品，這些產品也不適合內存。

package de.fencing_game.paul.examples; 

import java.util.*; 

/** 
* A iterable over the cartesian product of a iterable of iterables 
* with some common element type. 
*<p> 
* The elements of the product are tuples (lists) of elements, one of 
* each of the original iterables. 
*<p> 
* The iterator iterates the elements in lexicographic order, ordered by 
* the appearance of their components in their respective iterators. 
*<p> 
* Since we are iterating the iterables lazily, the iterators should 
* act the same each time, otherwise you'll get strange results (but it 
* will still be well-defined). 
*</p> 
* 
* Inspired by the question <a href="http://stackoverflow.com/questions/5220701/how-to-get-a-list-of-all-lists-containing-exactly-one-element-of-each-list-of-a-l/5222370#5222370">How to get a list of all lists containing exactly one element of each list of a list of lists</a> on Stackoverflow (by Dunaril). 
* 
* @author Paŭlo Ebermann 
*/ 
public class ProductIterable<X> 
    implements Iterable<List<X>> 
{ 

    private Iterable<? extends Iterable<? extends X>> factors; 

    public ProductIterable(Iterable<? extends Iterable<? extends X>> factors) { 
     this.factors = factors; 
    } 

    public Iterator<List<X>> iterator() { 
     return new ProductIterator(); 
    } 

    private class ProductIterator 
     implements Iterator<List<X>> 
    { 

     /** 
     * an element of our stack, which contains 
     * an iterator, the last element returned by 
     * this iterator, and the Iterable which created 
     * this iterator. 
     */ 
     private class StackElement { 
      X item; 
      Iterator<? extends X> iterator; 
      Iterable<? extends X> factor; 
      boolean has; 

      StackElement(Iterable<? extends X> fac) { 
       this.factor = fac; 
       newIterator(); 
      } 

      /** 
      * checks whether the {@link #step} call can 
      * get a new item. 
      * 
      */ 
      boolean hasNext() { 
       return has || 
        (has = iterator.hasNext()); 
      } 

      /** 
      * steps to the next item. 
      */ 
      void step() { 
       item = iterator.next(); 
       has = false; 
      } 

      /** 
      * creates a new iterator. 
      */ 
      void newIterator() { 
       iterator = factor.iterator(); 
       has = false; 
      } 

      /** 
      * for debugging: a string view of this StackElement. 
      */ 
      public String toString() { 
       return "SE[ i: " + item + ", f: " + factor + "]"; 
      } 
     } 

     /** 
     * our stack of iterators to run through 
     */ 
     private Deque<StackElement> stack; 
     /** 
     * is our next element already produced (= contained in 
     * the `item`s of the stack? 
     */ 
     private boolean hasNext; 


     /** 
     * constructor. 
     */ 
     ProductIterator() { 
      stack = new ArrayDeque<StackElement>(); 
      try { 
       fillStack(); 
       hasNext = true; 
      } 
      catch(NoSuchElementException ex) { 
       hasNext = false; 
      } 
     } 

     /** 
     * creates the stack. only called from constructor. 
     */ 
     private void fillStack() { 
      for(Iterable<? extends X> fac : factors) { 
       StackElement el = new StackElement(fac); 
       el.step(); 
       stack.push(el); 
      } 
     } 

     /** 
     * steps the iterator on top of the stack, and maybe the iterators 
     * below, too. 
     * @return true if more elements are available. 
     */ 
     private boolean stepIterator() { 
      if(stack.isEmpty()) 
       return false; 
      StackElement top = stack.peek(); 
      while(!top.hasNext()) { 
       stack.pop(); 
       if (!stepIterator()) { 
        return false; 
       } 
       top.newIterator(); 
       stack.push(top); 
      } 
      top.step(); 
      return true; 
     } 

     /** 
     * returns true if `next` will return a next element. 
     */ 
     public boolean hasNext() { 
      return 
       hasNext || 
       (hasNext = stepIterator()); 
     } 

     /** 
     * returns the next element of the cartesian product. 
     */ 
     public List<X> next() { 
      if(!hasNext()) { 
       throw new NoSuchElementException(); 
      } 
      hasNext = false; 
      return makeList(); 
     } 

     /** 
     * creates a list from the StackElements in reverse order. 
     */ 
     private List<X> makeList() { 
      List<X> list = new ArrayList<X>(stack.size()); 
      // TODO: more efficient reverse copying 
      for(StackElement se : stack) { 
       list.add(0, se.item); 
      } 
      return list; 
     } 

     /** 
     * the remove method is not supported, 
     * the cartesian product is immutable. 
     */ 
     public void remove() { 
      throw new UnsupportedOperationException(); 
     } 

    } // class ProductIterator 


    /** 
    * a test method which creates a list of lists and 
    * from this the cartesian product. 
    */ 
    public static void main(String[] params) { 

     @SuppressWarnings("unchecked") 
     List<List<Integer>> factors = 
      Arrays.asList(Arrays.asList(1,2), 
          Arrays.asList(10,20,30), 
          Arrays.asList(100)); 
     Iterable<List<Integer>> product = 
      new ProductIterable<Integer>(factors); 
     List<List<Integer>> productList = 
      new ArrayList<List<Integer>>(); 
     for(List<Integer> pEl : product) { 
      productList.add(pEl); 
      System.out.println(pEl); 
     } 
     System.out.println(productList); 
    } 

} 

---

還有一個編輯：這裏是一個基於索引的懶列表實現。

package de.fencing_game.paul.examples; 

import java.util.*; 

/** 
* The cartesian product of lists, in an (unmodifiable) index-based 
* implementation. 
* 
*<p> 
* The elements of the product are tuples (lists) of elements, one from 
* each of the base list's element lists. 
* These are ordered in lexicographic order, by their appearance in the 
* base lists. 
*</p> 
*<p> 
* This class works lazily, creating the elements of the product only 
* on demand. It needs no additional memory to the base list. 
*</p> 
*<p> 
* This class works even after changes of the base list or its elements - 
* the size of this list changes if any of the factor lists changes size. 
* Such changes should not occur during calls to this method, or 
* you'll get inconsistent results. 
*</p> 
* <p> 
* The product of the sizes of the component lists should be smaller than 
* Integer.MAX_INT, otherwise you'll get strange behaviour. 
* </p> 
* 
*<p> 
* Inspired by the question <a href="http://stackoverflow.com/questions/5220701/how-to-get-a-list-of-all-lists-containing-exactly-one-element-of-each-list-of-a-l/5222370#5222370">How to get a list of all lists containing exactly one element of each list of a list of lists</a> on Stackoverflow (by Dunaril). 
* 
* @author Paŭlo Ebermann 
*/ 
public class ProductList<X> 
    extends AbstractList<List<X>> 
{ 

    private List<? extends List<? extends X>> factors; 

    /** 
    * create a new product list, based on the given list of factors. 
    */ 
    public ProductList(List<? extends List<? extends X>> factors) { 
     this.factors = factors; 
    } 

    /** 
    * calculates the total size of this list. 
    * This method takes O(# factors) time. 
    */ 
    public int size() { 
     int product = 1; 
     for(List<?> l : factors) { 
      product *= l.size(); 
     } 
     return product; 
    } 

    /** 
    * returns an element of the product list by index. 
    * 
    * This method calls the get method of each list, 
    * so needs needs O(#factors) time if the individual 
    * list's get methods are in O(1). 
    * The space complexity is O(#factors), since we have to store 
    * the result somewhere. 
    * 
    * @return the element at the given index. 
    * The resulting list is of fixed-length and after return independent 
    * of this product list. (You may freely modify it like an array.) 
    */ 
    public List<X> get(int index) { 
     if(index < 0) 
      throw new IndexOutOfBoundsException("index " + index+ " < 0"); 
     // we can't create a generic X[], so we take an Object[] 
     // here and wrap it later in Arrays.asList(). 
     Object[] array = new Object[factors.size()]; 

     // we iteratively lookup the components, using 
     // modulo and division to calculate the right 
     // indexes. 
     for(int i = factors.size() - 1; i >= 0; i--) { 
      List<?> subList = factors.get(i); 
      int subIndex = index % subList.size(); 
      array[i] = subList.get(subIndex); 
      index = index/subList.size(); 
     } 
     if(index > 0) 
      throw new IndexOutOfBoundsException("too large index"); 

     @SuppressWarnings("unchecked") 
     List<X> list = (List<X>)Arrays.asList(array); 
     return list; 
    } 

    /** 
    * an optimized indexOf() implementation, runs in 
    * O(sum n_i) instead of O(prod n_i) 
    * (if the individual indexOf() calls take O(n_i) time). 
    * 
    * Runs in O(1) space. 
    */ 
    public int indexOf(Object o) 
    { 
     if(!(o instanceof List)) 
      return -1; 
     List<?> list = (List<?>)o; 
     if (list.size() != factors.size()) 
      return -1; 
     int index = 0; 
     for(int i = 0; i < factors.size(); i++) { 
      List<?> subList = factors.get(i); 
      Object candidate = list.get(i); 
      int subIndex = subList.indexOf(candidate); 
      if(subIndex < 0) 
       return -1; 
      index = index * subList.size() + subIndex; 
     } 
     return index; 
    } 

    /** 
    * an optimized lastIndexOf() implementation, runs in 
    * O(sum n_i) time instead of O(prod n_i) time 
    * (if the individual indexOf() calls take O(n_i) time). 
    * Runs in O(1) space. 
    */ 
    public int lastIndexOf(Object o) 
    { 
     if(!(o instanceof List)) 
      return -1; 
     List<?> list = (List<?>)o; 
     if (list.size() != factors.size()) 
      return -1; 
     int index = 0; 
     for(int i = 0; i < factors.size(); i++) { 
      List<?> subList = factors.get(i); 
      Object candidate = list.get(i); 
      int subIndex = subList.lastIndexOf(candidate); 
      if(subIndex < 0) 
       return -1; 
      index = index * subList.size() + subIndex; 
     } 
     return index; 
    } 

    /** 
    * an optimized contains check, based on {@link #indexOf}. 
    */ 
    public boolean contains(Object o) { 
     return indexOf(o) != -1; 
    } 


    /** 
    * a test method which creates a list of lists and 
    * shows the cartesian product of this. 
    */ 
    public static void main(String[] params) { 

     @SuppressWarnings("unchecked") 
     List<List<Integer>> factors = 
      Arrays.asList(Arrays.asList(1,2), 
          Arrays.asList(10,20,30, 20), 
          Arrays.asList(100)); 
     System.out.println("factors: " + factors); 
     List<List<Integer>> product = 
      new ProductList<Integer>(factors); 
     System.out.println("product: " + product); 
     List<Integer> example = Arrays.asList(2,20,100); 
     System.out.println("indexOf(" + example +") = " + 
          product.indexOf(example)); 
     System.out.println("lastIndexOf(" + example +") = " + 
          product.lastIndexOf(example)); 
    } 

} 

我加的實現包含，的indexOf和lastIndexOf這比原有的從AbstractList中（或類AbstractCollection）相當好（更大的因素，而不是在你的榜樣，至少）。這些沒有針對子列表進行優化，因爲子列表僅取自AbstractList。

Answer 4

簡單的迭代算法。

public static List<List<Object>> doStaff(List<List<Object>> objectList) { 

     List<List<Object>> retList = new ArrayList<List<Object>>(); 

     int[] positions = new int[objectList.size()]; 
     Arrays.fill(positions,0); 

     int idx = objectList.size() -1; 
     int size = idx; 

     boolean cont = idx > -1; 

     while(cont) { 

      idx = objectList.size() -1; 

      while(cont && positions[idx] == objectList.get(idx).size()) { 

       positions[idx] = 0; 
       idx--; 
       if(idx > -1) { 
        positions[idx] = positions[idx]+ 1; 
       } else { 
        cont = false; 
       } 
      } 

      if(cont) { 
       List<Object> tmp = new ArrayList<Object>(size); 
       for(int t = 0; t < objectList.size(); t++) { 
        tmp.add(t, objectList.get(t).get(positions[t])); 
        //System.out.print(objectList.get(t).get(positions[t])+ " "); 
       } 
       retList.add(tmp); 
//    System.out.println(); 
       positions[size] = positions[size] + 1; 
      } 
     } 
     return retList; 
    } 

如果有必要的話，請讓我知道。

Answer 5

你可能會使用Scala代碼：

def xproduct (xx: List [List[_]]) : List [List[_]] = 
    xx match { 
    case aa :: bb :: Nil => 
     aa.map (a => bb.map (b => List (a, b))).flatten  
    case aa :: bb :: cc => 
     xproduct (bb :: cc).map (li => aa.map (a => a :: li)).flatten 
    case _ => xx 
} 

由於雙重交叉是笛卡爾積的另一個名字，它的名字是xproduct。

Answer 6

這裏是phimuemue的Python算法的java實現。

private static List<List<Item>> getAllPossibleLists(List<List<Item>> itemsLists) { 
    List<List<Item>> returned = new ArrayList<List<Item>>(); 
    if(itemsLists.size() == 1){ 
     for (Item item : itemsLists.get(0)) { 
      List<Item> list = new ArrayList<Item>(); 
      list.add(item); 
      returned.add(list); 
     } 
     return returned; 
    } 
    List<Item> firstList = itemsLists.get(0); 
    for (List<Item> possibleList : getAllPossibleLists(itemsLists.subList(1, itemsLists.size()))) { 
     for(Item firstItem : firstList){ 
      List<Item> addedList = new ArrayList<Item>(); 
      addedList.add(firstItem); 
      addedList.addAll(possibleList); 
      returned.add(addedList); 
     } 
    } 
    return returned; 
} 

隨時可以進一步評論。感謝您的所有努力！