给定两个列表,我可以生成这两个列表的笛卡尔积的所有排列的列表:
permute :: [a] -> [a] -> [[a]]
permute xs ys = [ [x, y] | x <- xs, y <- ys ]
Example> permute [1,2] [3,4] == [ [1,3], [1,4], [2,3], [2,4] ]
如何扩展置换,以便不使用两个列表,而是获取列表的列表(长度为n)并返回列表列表(长度为n)
permute :: [[a]] -> [[a]]
Example> permute [ [1,2], [3,4], [5,6] ]
== [ [1,3,5], [1,3,6], [1,4,5], [1,4,6] ] --etc
我在Hoogle上找不到任何相关的东西..唯一与签名相匹配的功能是transpose,它不会产生所需的输出.
我正在寻找对关系代数中theta连接概念的清晰,基本的解释,也许是一个例子(或许使用SQL)来说明它的用法.
如果我理解正确的话,theta join是一个添加了条件的自然连接.那么,自然连接强制同名属性之间的相等(并删除副本？),theta连接做同样的事情,但添加在一个条件.我有这个权利吗？任何明确的解释,简单来说(对于非数学家)将不胜感激.
另外(对不起,最后只是把它扔进去,但它有点相关),有人可以解释笛卡尔积的重要性或想法吗？我认为我遗漏了一些关于基本概念的东西,因为对我来说它似乎只是一个基本事实的重述,即一组13 X一组4 = 52 ......
sql relational-algebra cartesian-product relational-database
假设我有两组数字:
{1, 2, 3},
{4, 5}
我想创建一个输出以下6种组合的算法(在Java中):
1,4
1,5
2,4
2,5
3,4
3,5
每组中可以有任意数量的组和任意数量的成员.因此在上面的例子中,有2组,第一组有3个成员,第二组有2个成员.另一个例子如下(3组,第一组3名成员,第2组和第3组2名成员):
{1, 2, 3},
{4, 5},
{6, 7}
这将产生以下12种组合:
1,4,6
1,4,7
1,5,6
1,5,7
2,4,6
2,4,7
2,5,6
2,5,7
3,4,6
3,4,7
3,5,6
3,5,7
我怎么能用Java做到这一点？我正在尝试使用递归,我已经看了一个类似的问题,但我仍然很短.谢谢您的帮助!(PS这不是作业作业)
这个问题询问如何计算给定数量向量的笛卡尔乘积.由于向量的数量是预先知道的并且相当小,因此使用嵌套的for循环很容易获得解决方案.
现在假设您以您选择的语言给出了向量(或列表列表或集合等)的向量:
l = [ [1,2,3], [4,5], [6,7], [8,9,10], [11,12], [13] ]
如果我被要求计算其笛卡尔积,那就是
[ [1,4,6,8,11,13], [1,4,6,8,12,13], [1,4,6,9,11,13], [1,4,6,9,12,13], ... ]
我会继续递归.例如,在快速和肮脏的python中,
def cartesianProduct(aListOfLists):
if not aListOfLists:
yield []
else:
for item in aListOfLists[0]:
for product in cartesianProduct(aListOfLists[1:]):
yield [item] + product
有一种简单的方法可以迭代计算它吗？
(注意:答案不需要在python中,无论如何我都知道在python中,itertools可以更好地完成工作,就像在这个问题中一样.)
我认为这是一个常见的组合问题,但我似乎无法找到它的名称或任何有关它的材料.我在Python和numpy中这样做,但如果有一个快速矩阵方法,我可以翻译.
基本上,给定n个项目,我需要生成所有方法将它们放入m个箱子中.举个例子,将4个项目合并为3个区域会产生类似的结果[(4, 0, 0), (3, 1, 0), (3, 0, 1), (2, 2, 0), (2, 1, 1), ...].这是一个固定总额的产品.
使用itertools实现这一点非常简单.
import itertools
def fixed_total_product(bins, num_items):
""" Return iterator of all item binning possibilities. """
return itertools.ifilter(lambda combo: sum(combo) == num_items,
itertools.product(xrange(num_items + 1), repeat=bins))
不幸的是,我认为在循环中进行后续计算将是低效的.使用它作为2D numpy数组稍后会更快,但我无法找到一种有效的方法来构建一个数组.我可以遍历ifilter结果,构建一个可能性列表,并使用它来构建数组,但这似乎是一个巨大的浪费.
我猜这样做的最好方法是建立一切"笨拙的方式",但我不知道该怎么做.stackoverflow上有一个快速的产品实现:使用numpy构建两个数组的所有组合的数组.我猜你可以修改它只是输出正确总和的产品.数组的大小应该是((m-1)+ n)选择n,因为有m-1个bin边界.
有任何想法吗？基准非常感谢,但不是必需的.
如果我有这个:
val a = Array("a ","b ","c ")
val b = Array("x","y")
我想知道是否存在允许我遍历第一个集合的这种方法,并且对于每个元素,遍历整个第二个集合.例如,如果我们采取的阵列a,我们将有a,x,a,y,b,x,b,y,c,x,c,y.我知道拉链,但从我看到的它只适用于相同尺寸的集合,并且它关联来自相同位置的元素.
我有一个未知数量的桶(集合),每个桶具有未知数量的实体
我需要生成所有实体的笛卡尔积,这样我最终会得到一个具有ARRAYS实体的COLLECTION,并且在每个数组中,每个桶都有1个代表性.
因此,如果我有5个桶(B1..B5),并且桶B1,B2各有1个项目,而桶B3,B4和B5各有4个,8个和10个项目,我将拥有320个阵列的集合,每个数组将有5个项目.
这里唯一的问题是,在开发时,桶的大小和桶的数量都是未知的.
性能在这里并不是非常重要,因为大多数时候,我的桶只有1个实体,而且很少有时候我的桶会包含20-30个项目...而且我通常会有5个30桶
我想在某种程度上使用linq,但是当我试图想象这是如何工作的时候,我的大脑正在变得油腻
使用GNU-make,假设我的Makefile中有两个列表,并且我想将它们组合起来以将其笛卡尔积作为另一个列表,以便我可以将其用作目标列表.
作为一个我不太清楚的语言的例子,R有一个函数expand.grid()可以实现这个目的.
我实际上想出了一种使用Makefile执行此操作的方法:
.PHONY: all
prefix := 1 2
base := A B
add_prefix = $(addsuffix $(base), $(prefix))
Obj = $(foreach base, $(base), $(add_prefix))
all:
@echo $(Obj)
但是,这非常hacky并且不以直观的方式使用addsuffix功能.有没有更好的方法呢？
我想创建一个方法来创建一个元素流,这些元素是多个给定流的笛卡尔积(由二元运算符在末尾聚合到相同类型).请注意,参数和结果都是流,而不是集合.
例如,对于{A,B}和{X,Y}的两个流,我希望它生成值{AX,AY,BX,BY}的流(简单串联用于聚合字符串).到目前为止,我已经提出了这个代码:
private static <T> Stream<T> cartesian(BinaryOperator<T> aggregator, Stream<T>... streams) {
Stream<T> result = null;
for (Stream<T> stream : streams) {
if (result == null) {
result = stream;
} else {
result = result.flatMap(m -> stream.map(n -> aggregator.apply(m, n)));
}
}
return result;
}
这是我想要的用例:
Stream<String> result = cartesian(
(a, b) -> a + b,
Stream.of("A", "B"),
Stream.of("X", "Y")
);
System.out.println(result.collect(Collectors.toList()));
预期结果:AX, AY, BX, BY.
另一个例子:
Stream<String> result = …假设您有n整数列表,其中每个列表仅包含from 1到的整数n.例如,对于n = 4,我们可能有:
a_1 = [1, 2]
a_2 = [3]
a_3 = [4, 1, 1]
a_4 = [2, 3]
现在我的问题是:我可以勾选这些列表之间1和之间的所有整数,但是一旦我找到一个数字,我就不能再使用该列表来查找后续数字了吗？nn
例如,在上面的示例中n = 4,我可以选择1,from a_1,from a_4,3 from a_2和4 for a_3,因此我填充了从1到4的所有数字,但仅使用每个列表一次.
我无法找到范围(因此应该返回False)的示例将是:
a_1 = [1, 2]
a_2 = [3, 3, 5]
a_3 = [4]
a_4 = [5]
a_5 = [3, 4, 5]
原因是因为如果我从a_1中选择1,我就不能从任何列表中选择2.
这是我目前直截了当的方法.我制作列表的笛卡尔积,并检查是否有任何,排序,将是一个范围.
import itertools
def …