如何获取包含列表列表的每个列表的一个元素的所有列表的列表
你可能已经理解了标题，我需要一些聪明的想法:)
我有一个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循环的重叠……
你怎么想出来的？ 时间限制与我的问题无关，因为列表可能包含很少的元素。
我不会实现它，但这是一个递归算法的想法：
- 如果我们正在处理包含单个元素列表的列表（ieeg
{{1,2,3}}），那么结果当然是 – 每个包含一个元素的列表列表（ieeg{{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
迭代算法。
public class A { public static List> combinations(List> inputList) { List> result = new LinkedList>(); for (Integer i : inputList.get(0)) { List temp = new ArrayList (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> make(List> in, List n) { List> res = new LinkedList>(); for (List l : in) { for (Integer i : n) { List cur = new ArrayList (l.size() + 1); cur.addAll(l); cur.add(i); res.add(cur); } } return res; } public static void main(String[] args) { List> inputList = new ArrayList(); inputList.add(new ArrayList () {{ add(1); add(2); }}); inputList.add(new ArrayList () {{ add(10); add(20); add(30); }}); inputList.add(new ArrayList () {{ add(100); }}); System.out.println(combinations(inputList)); } }
*请注意，此代码不适用于生产！ 您应该将LinkedList替换为具有初始大小的ArrayList ，进行检查等。
提供了upd使用示例。 有一些代码改进。 但它仍然只是起草。 我不建议你在实际任务中使用它。
为了完整起见，您所搜索的内容称为列表中的笛卡尔积 ，称为此类，因为结果列表的大小是各个列表大小的乘积。
编辑：这是一个适用于Iterables的任意Iterables的实现，并创建一个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. * * The elements of the product are tuples (lists) of elements, one of * each of the original iterables. *
* The iterator iterates the elements in lexicographic order, ordered by * the appearance of their components in their respective iterators. *
* 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). *
* * Inspired by the question How to get a list of all lists containing exactly one element of each list of a list of lists on Stackoverflow (by Dunaril). * * @author Paŭlo Ebermann */ public class ProductIterable implements Iterable> { private Iterable> factors; public ProductIterable(Iterable> factors) { this.factors = factors; } public Iterator> iterator() { return new ProductIterator(); } private class ProductIterator implements Iterator> { /** * 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 iterator; Iterable factor; boolean has; StackElement(Iterable 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 stack; /** * is our next element already produced (= contained in * the `item`s of the stack? */ private boolean hasNext; /** * constructor. */ ProductIterator() { stack = new ArrayDeque (); try { fillStack(); hasNext = true; } catch(NoSuchElementException ex) { hasNext = false; } } /** * creates the stack. only called from constructor. */ private void fillStack() { for(Iterable 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 next() { if(!hasNext()) { throw new NoSuchElementException(); } hasNext = false; return makeList(); } /** * creates a list from the StackElements in reverse order. */ private List makeList() { List list = new ArrayList (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> factors = Arrays.asList(Arrays.asList(1,2), Arrays.asList(10,20,30), Arrays.asList(100)); Iterable> product = new ProductIterable (factors); List> productList = new ArrayList>(); for(List 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. * * * 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. *
* * This class works lazily, creating the elements of the product only * on demand. It needs no additional memory to the base list. *
* * 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. *
* * The product of the sizes of the component lists should be smaller than * Integer.MAX_INT, otherwise you'll get strange behaviour. *
* * * Inspired by the question How to get a list of all lists containing exactly one element of each list of a list of lists on Stackoverflow (by Dunaril). * * @author Paŭlo Ebermann */ public class ProductList extends AbstractList> { private List> factors; /** * create a new product list, based on the given list of factors. */ public ProductList(List> 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 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 list = (List )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> factors = Arrays.asList(Arrays.asList(1,2), Arrays.asList(10,20,30, 20), Arrays.asList(100)); System.out.println("factors: " + factors); List> product = new ProductList (factors); System.out.println("product: " + product); List example = Arrays.asList(2,20,100); System.out.println("indexOf(" + example +") = " + product.indexOf(example)); System.out.println("lastIndexOf(" + example +") = " + product.lastIndexOf(example)); } }
我添加了contains，indexOf和lastIndexOf的实现，它们比AbstractList（或AbstractCollection）中的原始实现要好得多（至少比你的例子中更大的因素）。 这些未针对子列表进行优化，因为子列表仅来自AbstractList。
简单的迭代算法。
public static List> doStaff(List> objectList) { List> retList = new ArrayList>(); 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
如果有必要，请解释一下，让我知道。
您可以使用该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 }
由于crossproduct是笛卡儿产品的另一个名称，因此它的名称是xproduct。
这是phimuemue的Python算法的java实现。
private static List> getAllPossibleLists(List- > itemsLists) { List
- > returned = new ArrayList
- >(); if(itemsLists.size() == 1){ for (Item item : itemsLists.get(0)) { List
- list = new ArrayList
- (); list.add(item); returned.add(list); } return returned; } List
- firstList = itemsLists.get(0); for (List
- possibleList : getAllPossibleLists(itemsLists.subList(1, itemsLists.size()))) { for(Item firstItem : firstList){ List
- addedList = new ArrayList
- (); addedList.add(firstItem); addedList.addAll(possibleList); returned.add(addedList); } } return returned; }
随意发表评论。 谢谢你的所有努力！