标签: cartesian-product

我遇到Hibernate生成无效SQL的问题.具体来说,混合和匹配隐式和显式连接.这似乎是一个开放的bug.

但是,我不确定为什么这是无效的SQL.我想出了一个生成相同语法异常的小玩具示例.

架构

CREATE TABLE Employee (
    employeeID INT,
    name VARCHAR(255),
    managerEmployeeID INT   
)

数据

INSERT INTO Employee (employeeID, name) VALUES (1, 'Gary')
INSERT INTO Employee (employeeID, name, managerEmployeeID) VALUES (2, 'Bob', 1)

工作SQL

这两个查询都有效.我意识到有笛卡尔积; 那是故意的.

明确的加入:

SELECT e1.name,
       e2.name,
       e1Manager.name
  FROM Employee e1
 CROSS JOIN Employee e2
 INNER JOIN Employee e1Manager
    ON e1.managerEmployeeID = e1Manager.employeeID

隐含的JOIN:

SELECT e1.name,
       e2.name,
       e1Manager.name
  FROM Employee e1,
       Employee e2,
       Employee e1Manager
 WHERE e1.managerEmployeeID = e1Manager.employeeID

无效的SQL

此查询不适用于MSSQL 2000/2008或MySQL:

SELECT …

需要提示设计一个有效的算法,该算法采用以下输入并吐出以下输出.

输入:两个整数A和B的排序数组,每个长度为n

输出:一个排序数组,由数组A和B的笛卡尔积组成.

For Example: 

Input:
A is 1, 3, 5
B is 4, 8, 10
here n is 3.

Output:
4, 8, 10, 12, 20, 24, 30, 40, 50

以下是我尝试解决此问题的方法.

1)鉴于输出为n ^ 2,有效算法不能比O(n ^ 2)时间复杂度做得更好.

2)首先,我尝试了一种简单但效率低下的方法.生成A和B的笛卡尔积.它可以在O(n ^ 2)时间复杂度下完成.我们需要存储,所以我们可以对它进行排序.因此O(n ^ 2)空间复杂度也是如此.现在我们排序n ^ 2个元素,这些元素不能比O(n ^ 2logn)做得更好,而不对输入做任何假设.

最后我有O(n ^ 2logn)时间和O(n ^ 2)空间复杂度算法.

必须有一个更好的算法,因为我没有使用输入数组的排序性质.

我有一些ArrayList每个ArrayList都有对象,每个可以有不同的长度.我需要生成排列,如下例所示:

假设我有2个arraylist

arraylist A有对象a,对象b和对象c
arraylist B有对象d,对象e

那么输出应该是6个新的arraylist与这个组合:

组合1对象a和对象d,
组合2对象a和对象e,
组合3对象b和对象d,
组合4对象b和对象e,
组合5对象c和对象d,
组合6对象c和对象e,

谁能帮我？

假设我有4个字母,我想在3个地方安排它们(允许重复),所以我会有4 ³ = 64个可能的排列.我该如何计算和打印它们？

我有一本字典:

mydict = {'item1':[1,2,3],'item2':[10,20,30]}

我想创建两者的笛卡尔积,以便得到每个可能对的元组.

output: [(1,10),(1,20),(1,30),
         (2,10),(2,20),(2,30),
         (3,10),(3,20),(3,30)]

似乎有一种简单的方法可以做到这一点,如果我有三个项目,它会扩展.有点像动态循环次数.感觉像我错过了一个明显的方法来做到这一点......

我有3个numpy阵列,需要在它们之间形成笛卡尔积.阵列的尺寸不固定,因此它们可以采用不同的值,一个例子可以是A =(10000,50),B =(40,50),C =(10000,50).

然后,我执行一些处理(如a + bc)以下是我用于产品的功能.

def cartesian_2d(arrays, out=None):

    arrays = [np.asarray(x) for x in arrays]
    dtype = arrays[0].dtype

    n = np.prod([x.shape[0] for x in arrays])
    if out is None:
        out = np.empty([n, len(arrays), arrays[0].shape[1]], dtype=dtype)

    m = n // arrays[0].shape[0]
    out[:, 0] = np.repeat(arrays[0], m, axis=0)
    if arrays[1:]:
        cartesian_2d(arrays[1:], out=out[0:m, 1:, :])
        for j in range(1, arrays[0].shape[0]):
            out[j * m:(j + 1) * m, 1:] = out[0:m, 1:]
    return out

a = [[ 0, -0.02], [1, -0.15]]
b …

我的代码使用如下列表的笛卡尔积：

import itertools

cartesian_product = itertools.product(list('ABCDEF'), repeat=n)

n可以是 0 到 4 之间的任意值。

numba目前不支持itertools.product. 到目前为止我还无法想出一个可行的替代方案。欢迎任何建议！

我正在尝试使用 JUnit 5 编写一个测试，该测试应该测试某些参数的多种组合。本质上我想测试来自不同来源的输入的一些笛卡尔积。考虑以下测试：

import static org.junit.jupiter.api.Assertions.assertEquals;
import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.CsvFileSource;
class CartesianProductTest {

    @ParameterizedTest
    @CsvFileSource(resources = { "values.csv" })
    void testIt(int input, int expected, int otherParameter) {
        assertEquals(expected, methodUnderTest(input, otherParameter));
    }
}

现在的问题是，我只有input和 ，expected并且values.csv应该otherParameter测试一些固定值，这些固定methodUnderTest()值总是返回所有这些值的预期值。不知何故，我必须提供 CSV 中所有值以及所有值otherParameter可以采用的笛卡尔积。我查看了/sf/answers/4035366191/，但这需要对我的所有测试用例进行硬编码或手动读取 CSV 以提供值流。我更多地想到了类似的事情

import static org.junit.jupiter.api.Assertions.assertEquals;
import java.util.stream.Stream;
import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.Arguments;
import org.junit.jupiter.params.provider.CsvFileSource;
class CartesianProductTest {

    @ParameterizedTest
    @MethodSource
    void testIt(int input, int expected, int otherParameter) {
        assertEquals(expected, methodUnderTest(input, otherParameter)); …

我有以下代码将两个任意类型的向量组合成一个组合,即std::vector<std::tuple<A, B>>.

template<class A, class B>
std::vector<std::tuple<A, B>> combine(const std::vector<A>& a, const std::vector<B>& b) {

    const auto combine_parts_ = [](const A& x, const B& y) {
        auto result = std::tuple_cat(std::make_tuple(x), std::make_tuple(y));
        return result;
    };

    std::vector<std::tuple<A, B>> results;

    for (const auto& x : a) {
        for (const auto& y : b) {
            results.push_back(combine_parts_(x, y));
        }
    }

    return results;
}

但是,我不清楚如何将其扩展到任意数量的类型/向量.我不关心重复类型; 实际上可能涉及两组或更多组相同类型.没关系.

一些示例用例,例如:

const auto combinations = combine(
    std::vector<int>({1,2,3})
    , std::vector<int>({1,2,3})
);
const auto combinations2 = combine(
    std::vector<int>({1,2,3})
    , std::vector<int>({1,2,3}) …

因此，我正在编写一个函数allCoords，该函数返回宽度w和高度h两者的网格中每个可能坐标的列表，width并且height必须是非负整数才能返回合理的结果。

示例：allCoords 3 2应该返回[(0,0),(0,1),(0,2),(1,0),(1,1),(1,2)]

到目前为止，这就是我所拥有的，但我什至不知道如何开始编写函数

type GridCoord = (Int, Int)

allCoords :: Int -> Int -> [GridCoord]