标签: cartesian-product

这是一个后续:在Scala中将一组字符串扩展为笛卡尔积

你想要的想法是:

val sets = Set(Set("a","b","c"), Set("1","2"), Set("S","T"))

并回来:

Set("a&1&S", "a&1&T", "a&2&S", ..., "c&2&T")

一般解决方案是:

def combine[A](f:(A, A) => A)(xs:Iterable[Iterable[A]]) =
    xs.reduceLeft { (x, y) => x.view.flatMap {a => y.map(f(a, _)) } } 

用法如下:

val expanded = combine{(x:String, y:String) => x + "&" + y}(sets).toSet

从理论上讲,应该有一种方法来获取类型的输入Set[Set[A]]并获得一个Set[B].也就是说,在组合元素的同时转换类型.

一个示例用法是接受字符串集(如上所述)并输出其串联的长度.该f函数combine将一些形式:

(a:Int, b:String) => a + b.length 

我无法想出一个实现.有人有答案吗？

甲骨文似乎不时更倾向于MERGE JOIN CARTESIAN常规操作MERGE JOIN.知道数据并查看具体的执行计划,我可以看到这个操作通常不是问题,因为其中一个连接的实体只能在手头的查询中返回一个记录.

但是,由于历史原因,我们的DBA对笛卡尔产品普遍不满意.

所以我想更好地分析这些案例,并在我的论证中备份文档.是否有关于查询转换和CBO的官方Oracle文档,我可以在其中了解Oracle更喜欢MERGE JOIN CARTESIAN(或类似)操作的情况？

在这种情况下,我正在使用Oracle 11g(11.2.0.2.0)

更新:

这些是类似的问题,但它们没有解释为什么或何时 Oracle更喜欢MJC常规MERGE JOIN:

• 为什么此查询会导致Oracle中的MERGE JOIN CARTESIAN？
• 为什么此查询会导致Oracle中的Merge Cartesian Join

作为后续行动,以我的问题在这里,我想实现在Objective-C以下PHP函数,这将产生一个笛卡尔乘积:

function array_cartesian_product($arrays)
{
    $result = array();
    $arrays = array_values($arrays);
    $sizeIn = sizeof($arrays);
    $size = $sizeIn > 0 ? 1 : 0;
    foreach ($arrays as $array)
        $size = $size * sizeof($array);
    for ($i = 0; $i < $size; $i ++)
    {
        $result[$i] = array();
        for ($j = 0; $j < $sizeIn; $j ++)
            array_push($result[$i], current($arrays[$j]));
        for ($j = ($sizeIn -1); $j >= 0; $j --)
        {
            if (next($arrays[$j]))
                break;
            elseif (isset ($arrays[$j]))
                reset($arrays[$j]);
        }
    }
    return $result;
} …

我有以下嵌套循环:

for (x in xs) {
    for (y in ys) {
        # Do something with x and y
    }
}

我想拉平,所以我想建立两个向量的笛卡尔乘积的xs和ys并遍历结果.在Python中,这将是微不足道的:

for xy in product(xs, ys):
    # x, y = xy[0], xy[1]

但在R中,我发现的最简单的等价物看起来令人生畏:

xys <- expand.grid(xs, ys)
for (i in 1 : nrow(xys)) {
    xy <- as.vector(xys[i, ])
    # x <- xy[1], y <- xy[2]
}

当然必须有更好的方法,不是吗？(为了澄清,我不想迭代索引 ......我认为必须有一种方法可以直接迭代产品中的元组.)

我需要根据N个属性列表生成一组完整的变体,同时保持属性名称不变.

var input = [
    { 'colour' : ['red', 'green'] },
    { 'material' : ['cotton', 'wool', 'silk'] },
    { 'shape' : ['round', 'square', 'rectangle'] }
];

var expected = [
    { 'colour': 'red', 'material': 'cotton', 'shape': 'round' },
    { 'colour': 'red', 'material': 'cotton', 'shape': 'square' },
    { 'colour': 'red', 'material': 'cotton', 'shape': 'rectangle' },
    { 'colour': 'red', 'material': 'wool', 'shape': 'round' },
    { 'colour': 'red', 'material': 'wool', 'shape': 'square' },
    { 'colour': 'red', 'material': 'wool', 'shape': 'rectangle' },
    { 'colour': …

假设我有A_1,...A_n,例如[[a b c][d e][f]].我想找到这些集合的笛卡尔积,但不包括任何忽略列表元素的超集.

例如,如果我的忽略列表是[[a e][c]],笛卡尔积的结果将是[[a d f][b d f][b e f]].注意任何术语c都不在那里,也不是[a e f].

当然,我可以做到这一点的方法是找到完整的笛卡尔积,然后删除有问题的物品,但我想要一种更有效的方法,这样我就可以避免首先检查解决方案.

我有一个初步的解决方案,涉及逐步建立购物车产品中的每个术语,并在每个阶段我删除任何元素,A_i如果将它们添加到我正在构建的术语将导致它成为任何一个忽略的超集.这样工作正常,并且比天真的解决方案更好,但仍然有大量的冗余检查,这也取决于集合的呈现顺序.例如,如果[f]在我的忽略列表中,我仍会继续尝试创建术语,直到我到达[f]然后丢弃.

具体来说,我的clojure实现是

(defn first-elements
  "Get the first elements of a set of sets, unless ignored"
  [sets ignores in-ignore?]
  (loop [product-tuple [] sets sets]
    (println "sets " sets)
    (cond
      (or (nil? sets) (nil? (first sets)))
      product-tuple

      :else
      (if-let [set-op (remove #(in-ignore? product-tuple ignores %) (first sets))]
        (if (and …

我有一个列表字典:

In [72]: params
Out[72]: {'a': [1, 2, 3], 'b': [5, 6, 7, 8]}

我可能有两个以上的键/值对.我想创建一个字典列表,它给出了对应于a和的列表的所有可能组合b:

例如

[{'a':1, 'b'=5}, 
{'a':1, 'b'=6},
{'a':1, 'b'=7},
 ...
{'a':3, 'b'=8},]

我可以通过硬编码键来做到这一点:

for a,b in itertools.product(*p.itervalues()):
    print {'a':a, 'b':b}

但我不想硬编码

1. 我不知道有多少键/值对
2. 我不一定知道先进的名字

可以说,我有

• 两个非类型模板参数列表(可能有不同的类型)
• 一个模板foo,它将每个列表的一个值作为参数

如何创建foos 的可变参数包,使用两个列表元素的笛卡尔积进行参数化？

这就是我的意思:

template<int ...>
struct u_list {};

template<char ...>
struct c_list {};

template<int, char >
struct foo {};

template<class ...>
struct bar {};

using int_vals = u_list<1, 5, 7>;
using char_vals = c_list<-3, 3>;


using result_t = /* magic happens*/
using ref_t = bar<
    foo<1, -3>, foo<1, 3>,
    foo<5, -3>, foo<5, 3>,
    foo<7, -3>, foo<7, 3>
>;

static_assert(std::is_same<result_t, ref_t >::value, "");

我正在寻找一个适用于c ++ 11的解决方案,并且不使用除c ++ 11标准库之外的任何库.我也有我的handroled版本的c ++ 14's index_sequence/ make_index_sequence并且可以提供非类型参数列表作为数组,如果这简化了代码. …

我正在尝试构建不同(但每个同类)类型的遍历的多个交叉产品.期望的返回类型是元组的遍历,其类型与输入遍历中的类型匹配.例如:

List(1, 2, 3) cross Seq("a", "b") cross Set(0.5, 7.3)

这应该Traversable[(Int, String, Double)]从三个来源给出所有可能的组合.结合两个来源的情况在这里很好地回答.给出的想法是:

implicit class Crossable[X](xs: Traversable[X]) {
  def cross[A](ys: Traversable[A]) = for { x <- xs; y <- ys } yield (x, y)
}

那里的评论简要地提到了更多来源的问题,但我希望找到一种不依赖于无形或scalaz的解决方案(另一方面,我不介意有一些样板可以扩展到Tuple22).我想做的是如下:

implicit class Crossable[X](xs: Traversable[X]) {
  def cross[A](ys: Traversable[A]) = for { x <- xs; y <- ys } yield (x, y)
  def cross[A,B](ys: Traversable[(A,B)]) = // ... extend all Tuple2's in ys with x in xs …

我目前正在尝试合并三个数据集以进行分析.我正在使用某些常用字段来建立数据集之间的连接.为了创建连接,我尝试使用以下类型的查询:

MATCH (p1:Person),(p2:Person)
WHERE p1.email = p2.email AND p1.name = p2.name AND p1 <> p2 
CREATE UNIQUE (p1)-[IS]-(p2);

可以类似地写成:

MATCH (p1:Person),(p2:Person {name:p1.name, email:p1.email})
WHERE p1 <> p2 
CREATE UNIQUE (p1)-[IS]-(p2);

不用说,对于具有大约100,000个Person节点的数据库,这是一个非常慢的查询,特别是假设Neo4j不并行处理单个查询.

现在,我的问题是是否有更好的方法在Neo4j中运行此类查询.我有至少8个CPU核心专用于Neo4j,只要单独的线程不会通过锁定彼此所需的资源来占用.

问题是我不知道Neo4j如何构建其Cypher执行计划.例如,假设我运行以下测试查询:

MATCH (p1:Person),(p2:Person {name:p1.name, email:p1.email})
WHERE p1 <> p2 
RETURN p1, p2
LIMIT 100;

尽管有LIMIT条款,Neo4j仍然需要相当长的时间来交付结果,这让我想知道即使是这样有限的查询,Neo4j在考虑LIMIT语句之前是否产生了整个笛卡尔积表.

我感谢任何帮助,无论是解决这个特定问题,还是让我了解Neo4j如何建立Cypher执行计划(以及如何优化查询).传统的Lucene索引可以在这里提供任何帮助吗？