生成多个列表中的所有组合

Question

生成多个列表中的所有组合

给定未知数量的列表，每个列表具有未知长度，我需要生成具有所有可能的唯一组合的单个列表。例如，给出以下列表：

X: [A, B, C] Y: [W, X, Y, Z]

然后我应该能够生成12种组合：

[AW, AX, AY, AZ, BW, BX, BY, BZ, CW, CX, CY, CZ]

如果添加了3个元素的第三个列表，我将有36个组合，依此类推。

关于如何用Java做到这一点的任何想法？
（伪代码也可以）

Answer 1

你需要递归：假设您的所有列表都在lists，这是一个列表列表。让我们result列出您所需的排列。你可以像这样实现它：void&nbsp;generatePermutations(List<List<Character>>&nbsp;lists,&nbsp;List<String>&nbsp;result,&nbsp;int&nbsp;depth,&nbsp;String&nbsp;current)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(depth&nbsp;==&nbsp;lists.size())&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;result.add(current); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return; &nbsp;&nbsp;&nbsp;&nbsp;} &nbsp;&nbsp;&nbsp;&nbsp;for&nbsp;(int&nbsp;i&nbsp;=&nbsp;0;&nbsp;i&nbsp;<&nbsp;lists.get(depth).size();&nbsp;i++)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;generatePermutations(lists,&nbsp;result,&nbsp;depth&nbsp;+&nbsp;1,&nbsp;current&nbsp;+&nbsp;lists.get(depth).get(i)); &nbsp;&nbsp;&nbsp;&nbsp;}}最终的电话会是这样的：generatePermutations(lists,&nbsp;result,&nbsp;0,&nbsp;"");

Answer 2

这个话题派上了用场。我用Java完全重写了以前的解决方案，更加用户友好。此外，我使用集合和泛型来获得更大的灵活性：/** &nbsp;*&nbsp;Combines&nbsp;several&nbsp;collections&nbsp;of&nbsp;elements&nbsp;and&nbsp;create&nbsp;permutations&nbsp;of&nbsp;all&nbsp;of&nbsp;them,&nbsp;taking&nbsp;one&nbsp;element&nbsp;from&nbsp;each &nbsp;*&nbsp;collection,&nbsp;and&nbsp;keeping&nbsp;the&nbsp;same&nbsp;order&nbsp;in&nbsp;resultant&nbsp;lists&nbsp;as&nbsp;the&nbsp;one&nbsp;in&nbsp;original&nbsp;list&nbsp;of&nbsp;collections. &nbsp;*&nbsp; &nbsp;*&nbsp;<ul>Example &nbsp;*&nbsp;<li>Input&nbsp;&nbsp;=&nbsp;{&nbsp;{a,b,c}&nbsp;,&nbsp;{1,2,3,4}&nbsp;}</li> &nbsp;*&nbsp;<li>Output&nbsp;=&nbsp;{&nbsp;{a,1}&nbsp;,&nbsp;{a,2}&nbsp;,&nbsp;{a,3}&nbsp;,&nbsp;{a,4}&nbsp;,&nbsp;{b,1}&nbsp;,&nbsp;{b,2}&nbsp;,&nbsp;{b,3}&nbsp;,&nbsp;{b,4}&nbsp;,&nbsp;{c,1}&nbsp;,&nbsp;{c,2}&nbsp;,&nbsp;{c,3}&nbsp;,&nbsp;{c,4}&nbsp;}</li> &nbsp;*&nbsp;</ul> &nbsp;*&nbsp; &nbsp;*&nbsp;@param&nbsp;collections&nbsp;Original&nbsp;list&nbsp;of&nbsp;collections&nbsp;which&nbsp;elements&nbsp;have&nbsp;to&nbsp;be&nbsp;combined. &nbsp;*&nbsp;@return&nbsp;Resultant&nbsp;collection&nbsp;of&nbsp;lists&nbsp;with&nbsp;all&nbsp;permutations&nbsp;of&nbsp;original&nbsp;list. &nbsp;*/public&nbsp;static&nbsp;<T>&nbsp;Collection<List<T>>&nbsp;permutations(List<Collection<T>>&nbsp;collections)&nbsp;{ &nbsp;&nbsp;if&nbsp;(collections&nbsp;==&nbsp;null&nbsp;||&nbsp;collections.isEmpty())&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;Collections.emptyList(); &nbsp;&nbsp;}&nbsp;else&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;Collection<List<T>>&nbsp;res&nbsp;=&nbsp;Lists.newLinkedList(); &nbsp;&nbsp;&nbsp;&nbsp;permutationsImpl(collections,&nbsp;res,&nbsp;0,&nbsp;new&nbsp;LinkedList<T>()); &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;res; &nbsp;&nbsp;}}/**&nbsp;Recursive&nbsp;implementation&nbsp;for&nbsp;{@link&nbsp;#permutations(List,&nbsp;Collection)}&nbsp;*/private&nbsp;static&nbsp;<T>&nbsp;void&nbsp;permutationsImpl(List<Collection<T>>&nbsp;ori,&nbsp;Collection<List<T>>&nbsp;res,&nbsp;int&nbsp;d,&nbsp;List<T>&nbsp;current)&nbsp;{ &nbsp;&nbsp;//&nbsp;if&nbsp;depth&nbsp;equals&nbsp;number&nbsp;of&nbsp;original&nbsp;collections,&nbsp;final&nbsp;reached,&nbsp;add&nbsp;and&nbsp;return &nbsp;&nbsp;if&nbsp;(d&nbsp;==&nbsp;ori.size())&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;res.add(current); &nbsp;&nbsp;&nbsp;&nbsp;return; &nbsp;&nbsp;} &nbsp;&nbsp;//&nbsp;iterate&nbsp;from&nbsp;current&nbsp;collection&nbsp;and&nbsp;copy&nbsp;'current'&nbsp;element&nbsp;N&nbsp;times,&nbsp;one&nbsp;for&nbsp;each&nbsp;element &nbsp;&nbsp;Collection<T>&nbsp;currentCollection&nbsp;=&nbsp;ori.get(d); &nbsp;&nbsp;for&nbsp;(T&nbsp;element&nbsp;:&nbsp;currentCollection)&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;List<T>&nbsp;copy&nbsp;=&nbsp;Lists.newLinkedList(current); &nbsp;&nbsp;&nbsp;&nbsp;copy.add(element); &nbsp;&nbsp;&nbsp;&nbsp;permutationsImpl(ori,&nbsp;res,&nbsp;d&nbsp;+&nbsp;1,&nbsp;copy); &nbsp;&nbsp;}}我正在使用guava库来创建集合。

Answer 3

此操作称为笛卡尔积。Guava提供了一个实用功能：Lists.cartesianProduct