如何在bash中产生笛卡尔积？

Question

如何在bash中产生笛卡尔积？

14

我想生成这样的文件（[1-3]X[1-5]的笛卡尔积）：

我可以使用嵌套循环来完成这个操作，如下所示：

for i in $(seq 3) 
do
  for j in $(seq 5)
  do
      echo $i $j
  done
done

有没有不用循环的解决方案？

- Farvardin

3个回答

13

Rubens的回答有一个更简短但有些Hack的版本：

join -j 999999 -o 1.1,2.1 file1 file2

由于字段 999999 很可能不存在，因此对于两个集合来说被认为是相等的，因此 join 必须执行笛卡尔积。它使用 O(N+M) 内存，在我的机器上产生 100..200 Mb/sec 的输出。

我不喜欢使用 "shell brace expansion" 方法，例如 echo {1..100}x{1..100}，因为它使用 O(N*M) 内存，并且在使用不当时可能会使您的机器崩溃。这很难停止，因为 ctrl+c 不会中断由 shell 自身执行的大括号展开。

- legolegs

这是最通用的解决方案，因为它适用于文件而不仅仅是数字序列。 - kvantour

10

在bash中，替代笛卡尔积的最佳方法当然是使用参数扩展，正如@fedorqui所指出的那样。但是，如果你的输入不太容易生成（即，如果{1..3}和{1..5}不足以满足要求），你可以简单地使用join。

例如，如果你想对两个常规文件a.txt和b.txt执行笛卡尔积，可以按照以下步骤进行。首先，这两个文件：

$ echo -en {a..c}"\tx\n" | sed 's/^/1\t/' > a.txt
$ cat a.txt
1    a    x
1    b    x
1    c    x

$ echo -en "foo\nbar\n" | sed 's/^/1\t/' > b.txt
$ cat b.txt
1    foo
1    bar

请注意，sed 命令用于添加每行的标识符。这个标识符必须对于所有行以及所有文件都是相同的，这样 join 命令才能给你一个笛卡尔积，而不是放弃一些结果行。因此，join 的使用方法如下：

$ join -j 1 -t $'\t' a.txt b.txt | cut -d $'\t' -f 2-
a    x    foo
a    x    bar
b    x    foo
b    x    bar
c    x    foo
c    x    bar

在合并这两个文件之后，使用 cut 命令作为替代方法来删除前面加上的“1”列。

- Rubens

你写的“join”实际上是一个连接（http://en.wikipedia.org/wiki/Join_%28relational_algebra%29#Joins_and_join-like_operators），我不需要连接。我想要的是笛卡尔积（http://en.wikipedia.org/wiki/Cartesian_product）。 - Farvardin

1

@طاهر 当你将一个表的每一行与另一个表的每一行连接起来时，也就是进行交叉连接时，输出结果是笛卡尔积。 - Rubens

2

这种解决方案的好处在于bash本身不允许在花括号扩展中使用变量。你可以使用eval在花括号扩展中使用变量，但这样你就要使用eval。 - Erik

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- fedorqui · Accepted Answer

合并两个花括号展开！

$ printf "%s\n" {1..3}" "{1..5}
1 1
1 2
1 3
1 4
1 5
2 1
2 2
2 3
2 4
2 5
3 1
3 2
3 3
3 4
3 5

这可以通过使用单个花括号扩展来实现：

$ echo {1..5}
1 2 3 4 5

然后与另一个合并:

$ echo {1..5}+{a,b,c}
1+a 1+b 1+c 2+a 2+b 2+c 3+a 3+b 3+c 4+a 4+b 4+c 5+a 5+b 5+c