Return 列表列表的叉积
Return the cross product of a list of lists
给定一个大小为 n 的列表，编写一个程序 returns 每个列表中包含的元素的所有可能组合。
示例：
- 列表 A = "x, z"
- 列表 B = "a, b, c"
- 列表 C = "o, p"
输出：
- x o
- x p
- x b o
- xbp
- .....
- z c p
顺序无关紧要，但困难的部分是：您不能使用递归。
我的解决方案：
void combos(const char *string)
{
int i, j, k;
int len = strlen(string);
for (i = 0; i < len - 2; i++)
{
for (j = i + 1; j < len - 1; j++)
{
for (k = j + 1; k < len; k++)
printf("%c%c%c\n", string[i], string[j], string[k]);
}
}
}
如您所见，只有在我事先知道列表数量的情况下它才有效。我很好奇递归是否是解决它的唯一方法。
如您所知，通常的解决方案是递归。然而，出于无聊，我曾经写了一个 java 方法 multiNext 来完成这个而不需要递归。 multiNext 使用数组来跟踪嵌套循环的等效系统中的索引负载。
public static boolean multiNext(int[] current, int[] slotLengths) {
for (int r = current.length - 1; r >= 0; r--) {
if (current[r] < slotLengths[r] - 1) {
current[r]++;
return true;
} else {
current[r] = 0;
}
}
return false;
}
public static void cross(List<List<String>> lists) {
int size = lists.size();
int[] current = new int[size];
int[] slotLengths = new int[size];
for (int i = 0; i < size; i++)
slotLengths[i] = lists.get(i).size();
do {
List<String> temp = new ArrayList<>();
for (int i = 0; i < size; i++)
temp.add(lists.get(i).get(current[i]));
System.out.println(temp);
} while (multiNext(current, slotLengths));
}
public static void main(String[] args) {
cross(Arrays.asList(Arrays.asList("x", "z"), Arrays.asList("a", "b", "c"), Arrays.asList("o", "p")));
}
你不需要递归。您需要做的就是建立一套中间解决方案。这是 Python 中的非递归解决方案：
# This does NOT use recursion!
def all_comb(list_of_lists):
# We start with a list of just the empty set.
answer = [[]]
for list in list_of_lists:
# new_answer will be the list of combinations including this one.
new_answer = []
# Build up the new answer.
for thing in list:
for prev_list in answer:
new_answer.append(prev_list + [thing])
# Replace the old answer with the new one.
answer = new_answer
# We now have all combinations of all lists.
return answer
# Demonstration that it works.
for comb in all_comb([["x", "y"], ["a", "b", "c"], ["o", "p"]]):
print(" ".join(comb))
把它想象成递增数字的方式，例如一个基数为 3 的数字会是：
000
001
002
010
011
...
222
现在把每个数字想象成每个嵌套列表的索引。您将拥有与嵌套列表一样多的数字，即外部列表的大小。
每个数字的"base"可能不同，是对应嵌套列表的大小。如果嵌套列表很大，"digit" 可以是一个非常大的数字。
因此，您首先创建 "digit" 列表或索引值，将它们初始化为 0。然后打印这些索引处的元素值。然后增加最后一个索引值，根据需要滚动，就像普通数字一样，在第一个索引值滚动时停止。
这里是 Java 使用数组的数组实现，即 String[][]。如果需要，您可以轻松更改为 List<List<String>> 或 List<String[]>。
@SafeVarargs
public static void printCombos(String[] ... lists) {
if (lists.length == 0)
throw new IllegalArgumentException("No lists given");
for (String[] list : lists)
if (list.length == 0)
throw new IllegalArgumentException("List is empty");
int[] idx = new int[lists.length];
for (;;) {
// Print combo
for (int i = 0; i < lists.length; i++) {
if (i != 0)
System.out.print(' ');
System.out.print(lists[i][idx[i]]);
}
System.out.println();
// Advance to next combination
for (int i = lists.length - 1; ++idx[i] == lists[i].length; ) {
idx[i] = 0;
if (--i < 0)
return; // We're done
}
}
}
public static void main(String[] args) {
String[][] data = { { "x", "z" }, { "a", "b", "c" }, { "o", "p" } };
printCombos(data);
}
输出
x a o
x a p
x b o
x b p
x c o
x c p
z a o
z a p
z b o
z b p
z c o
z c p
如果您使用列表而不是数组，那么代码将使用 get(int)，这可能并不总是有利于性能，例如LinkedList.
如果是这种情况，请将 int[] idx 替换为 Iterator[]，使用相应列表的迭代器初始化每个数组条目。然后通过从相关列表中检索新的 Iterator 来将 "digit" 重置为 0。
在这种情况下，它们甚至不必是列表，可以是任何类型的集合，或者更具体地说 Iterable 个对象。
编辑：我在 python 中回答这个问题，因为尽管它目前被标记为 language-agnostic，但 python 是一个很好的可执行伪代码。
如果您可以以 尾递归 的形式编写函数，即以类似于 def f(x): return f(g(x)) 的形式编写函数，则很容易将其转换为迭代形式。不幸的是，您通常不会以尾递归调用结束，因此您需要了解一些技巧。
首先，假设我们有一个如下所示的函数：
def my_map(func, my_list):
if not my_list:
return []
return [func(my_list[0])] + change_my_list(my_list[1:])
好的，所以它是递归的，但不是尾递归：它真的是
def my_map(func, my_list):
if not my_list:
return []
result = [func(my_list[0])] + change_my_list(my_list[1:])
return result
相反，我们需要稍微调整函数，添加传统上称为累加器的内容：
def my_map(func, my_list, acc = [])
if not my_list: return acc
acc = acc + func(my_list[0])
return my_map(func, my_list[1:], acc + func(my_list[0]))
现在，我们有了一个真正的尾递归函数：我们已经从 def f(x): return g(f(x)) 变成了 def f(x): return f(g(x))
现在，将该函数转换为非递归形式非常简单：
def my_map(func, my_list, acc=[]):
while True: #added
if not my_list: return acc
#return my_map(func, my_list[1:], acc + func(my_list[0])) #deleted
func, my_list, acc = func, my_list[1:], acc + func(my_list[0]) #added
现在，我们稍微整理一下：
def my_map(func, my_list):
acc = []
while my_list:
acc.append(func(my_list[0])
my_list = my_list[1:]
return acc
请注意，您可以使用 for 循环或列表理解进一步清理它，但这留作 reader.
的练习
好吧，这是一个病态的例子，希望你知道 python 有一个内置的 map 函数，但是过程是一样的：转换成尾递归形式，替换带有参数重新分配的递归调用，并整理。
所以，如果你有：
def make_products(list_of_lists):
if not list_of_lists: return []
first_list = list_of_lists[0]
rest = list_of_lists[1:]
return product_of(first_list, make_products(rest))
可以转换成尾递归形式
def make_products(list_of_lists, acc=[]):
if not list_of_lists: return acc
first_list = list_of_lists[0]
rest = list_of_lists[1:]
acc = product_of(acc, first_list)
return make_products(rest, acc)
然后，简化为：
def make_products(list_of_lists):
acc=[]
while list_of_lists:
first_list = list_of_lists[0]
rest = list_of_lists[1:]
acc = product_of(acc, first_list)
list_of_lists = rest
return acc
同样，这可以进一步清理，进入 for 循环：
def make_products(list_of_lists):
acc=[]
for lst in list_of_lists:
acc = product_of(acc, lst)
return acc
如果您看过内置函数，您可能会注意到这有点熟悉：它本质上是 reduce 函数：
def reduce(function, iterable, initializer):
acc = initializer
for x in iterable:
acc = function(acc, x)
return acc
所以，最终的形式是这样的
def make_products(list_of_lists):
return reduce(product_of, list_of_lists, []) # the last argument is actually optional here
然后您只需担心编写 product_of 函数。
给定一个大小为 n 的列表，编写一个程序 returns 每个列表中包含的元素的所有可能组合。
示例：
- 列表 A = "x, z"
- 列表 B = "a, b, c"
- 列表 C = "o, p"
输出：
- x o
- x p
- x b o
- xbp
- .....
- z c p
顺序无关紧要，但困难的部分是：您不能使用递归。 我的解决方案：
void combos(const char *string)
{
int i, j, k;
int len = strlen(string);
for (i = 0; i < len - 2; i++)
{
for (j = i + 1; j < len - 1; j++)
{
for (k = j + 1; k < len; k++)
printf("%c%c%c\n", string[i], string[j], string[k]);
}
}
}
如您所见，只有在我事先知道列表数量的情况下它才有效。我很好奇递归是否是解决它的唯一方法。
如您所知，通常的解决方案是递归。然而，出于无聊，我曾经写了一个 java 方法 multiNext 来完成这个而不需要递归。 multiNext 使用数组来跟踪嵌套循环的等效系统中的索引负载。
public static boolean multiNext(int[] current, int[] slotLengths) {
for (int r = current.length - 1; r >= 0; r--) {
if (current[r] < slotLengths[r] - 1) {
current[r]++;
return true;
} else {
current[r] = 0;
}
}
return false;
}
public static void cross(List<List<String>> lists) {
int size = lists.size();
int[] current = new int[size];
int[] slotLengths = new int[size];
for (int i = 0; i < size; i++)
slotLengths[i] = lists.get(i).size();
do {
List<String> temp = new ArrayList<>();
for (int i = 0; i < size; i++)
temp.add(lists.get(i).get(current[i]));
System.out.println(temp);
} while (multiNext(current, slotLengths));
}
public static void main(String[] args) {
cross(Arrays.asList(Arrays.asList("x", "z"), Arrays.asList("a", "b", "c"), Arrays.asList("o", "p")));
}
你不需要递归。您需要做的就是建立一套中间解决方案。这是 Python 中的非递归解决方案：
# This does NOT use recursion!
def all_comb(list_of_lists):
# We start with a list of just the empty set.
answer = [[]]
for list in list_of_lists:
# new_answer will be the list of combinations including this one.
new_answer = []
# Build up the new answer.
for thing in list:
for prev_list in answer:
new_answer.append(prev_list + [thing])
# Replace the old answer with the new one.
answer = new_answer
# We now have all combinations of all lists.
return answer
# Demonstration that it works.
for comb in all_comb([["x", "y"], ["a", "b", "c"], ["o", "p"]]):
print(" ".join(comb))
把它想象成递增数字的方式，例如一个基数为 3 的数字会是：
000
001
002
010
011
...
222
现在把每个数字想象成每个嵌套列表的索引。您将拥有与嵌套列表一样多的数字，即外部列表的大小。
每个数字的"base"可能不同，是对应嵌套列表的大小。如果嵌套列表很大，"digit" 可以是一个非常大的数字。
因此，您首先创建 "digit" 列表或索引值，将它们初始化为 0。然后打印这些索引处的元素值。然后增加最后一个索引值，根据需要滚动，就像普通数字一样，在第一个索引值滚动时停止。
这里是 Java 使用数组的数组实现，即 String[][]。如果需要，您可以轻松更改为 List<List<String>> 或 List<String[]>。
@SafeVarargs
public static void printCombos(String[] ... lists) {
if (lists.length == 0)
throw new IllegalArgumentException("No lists given");
for (String[] list : lists)
if (list.length == 0)
throw new IllegalArgumentException("List is empty");
int[] idx = new int[lists.length];
for (;;) {
// Print combo
for (int i = 0; i < lists.length; i++) {
if (i != 0)
System.out.print(' ');
System.out.print(lists[i][idx[i]]);
}
System.out.println();
// Advance to next combination
for (int i = lists.length - 1; ++idx[i] == lists[i].length; ) {
idx[i] = 0;
if (--i < 0)
return; // We're done
}
}
}
public static void main(String[] args) {
String[][] data = { { "x", "z" }, { "a", "b", "c" }, { "o", "p" } };
printCombos(data);
}
输出
x a o
x a p
x b o
x b p
x c o
x c p
z a o
z a p
z b o
z b p
z c o
z c p
如果您使用列表而不是数组，那么代码将使用 get(int)，这可能并不总是有利于性能，例如LinkedList.
如果是这种情况，请将 int[] idx 替换为 Iterator[]，使用相应列表的迭代器初始化每个数组条目。然后通过从相关列表中检索新的 Iterator 来将 "digit" 重置为 0。
在这种情况下，它们甚至不必是列表，可以是任何类型的集合，或者更具体地说 Iterable 个对象。
编辑：我在 python 中回答这个问题，因为尽管它目前被标记为 language-agnostic，但 python 是一个很好的可执行伪代码。
如果您可以以 尾递归 的形式编写函数，即以类似于 def f(x): return f(g(x)) 的形式编写函数，则很容易将其转换为迭代形式。不幸的是，您通常不会以尾递归调用结束，因此您需要了解一些技巧。
首先，假设我们有一个如下所示的函数：
def my_map(func, my_list):
if not my_list:
return []
return [func(my_list[0])] + change_my_list(my_list[1:])
好的，所以它是递归的，但不是尾递归：它真的是
def my_map(func, my_list):
if not my_list:
return []
result = [func(my_list[0])] + change_my_list(my_list[1:])
return result
相反，我们需要稍微调整函数，添加传统上称为累加器的内容：
def my_map(func, my_list, acc = [])
if not my_list: return acc
acc = acc + func(my_list[0])
return my_map(func, my_list[1:], acc + func(my_list[0]))
现在，我们有了一个真正的尾递归函数：我们已经从 def f(x): return g(f(x)) 变成了 def f(x): return f(g(x))
现在，将该函数转换为非递归形式非常简单：
def my_map(func, my_list, acc=[]):
while True: #added
if not my_list: return acc
#return my_map(func, my_list[1:], acc + func(my_list[0])) #deleted
func, my_list, acc = func, my_list[1:], acc + func(my_list[0]) #added
现在，我们稍微整理一下：
def my_map(func, my_list):
acc = []
while my_list:
acc.append(func(my_list[0])
my_list = my_list[1:]
return acc
请注意，您可以使用 for 循环或列表理解进一步清理它，但这留作 reader.
好吧，这是一个病态的例子，希望你知道 python 有一个内置的 map 函数，但是过程是一样的：转换成尾递归形式，替换带有参数重新分配的递归调用，并整理。
所以，如果你有：
def make_products(list_of_lists):
if not list_of_lists: return []
first_list = list_of_lists[0]
rest = list_of_lists[1:]
return product_of(first_list, make_products(rest))
可以转换成尾递归形式
def make_products(list_of_lists, acc=[]):
if not list_of_lists: return acc
first_list = list_of_lists[0]
rest = list_of_lists[1:]
acc = product_of(acc, first_list)
return make_products(rest, acc)
然后，简化为：
def make_products(list_of_lists):
acc=[]
while list_of_lists:
first_list = list_of_lists[0]
rest = list_of_lists[1:]
acc = product_of(acc, first_list)
list_of_lists = rest
return acc
同样，这可以进一步清理，进入 for 循环：
def make_products(list_of_lists):
acc=[]
for lst in list_of_lists:
acc = product_of(acc, lst)
return acc
如果您看过内置函数，您可能会注意到这有点熟悉：它本质上是 reduce 函数：
def reduce(function, iterable, initializer):
acc = initializer
for x in iterable:
acc = function(acc, x)
return acc
所以，最终的形式是这样的
def make_products(list_of_lists):
return reduce(product_of, list_of_lists, []) # the last argument is actually optional here
然后您只需担心编写 product_of 函数。