How to produce cartesian product in bash?

Question

I want to produce such file (cartesian product of [1-3]X[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

I can do this using nested loop like:

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

is there any solution without loops?

Answer 1

Combine two brace expansions!

$ 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

This works by using a single brace expansion:

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

and then combining with another one:

$ 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

Answer 2

鲁本斯答案的一个较短(但很难)的版本:

join -j 999999 -o 1.1,2.1 file1 file2

由于字段999999很可能不存在,因此两个集合被认为是相等的,因此join必须使用笛卡尔积.它使用O(N + M)内存,并在我的机器上以100..200 Mb /秒的速度输出.

我不喜欢像echo {1..100}x{1..100}大型数据集那样的"shell撑杆扩展"方法,因为它使用O(N*M)内存,并且可以在使用时不小心将机器拉到膝盖.它很难停止,因为ctrl + c不会中断由shell本身完成的大括号扩展.

Answer 3

正如@fedorqui指出的那样,bash中笛卡尔积的最佳替代方案肯定是使用参数扩展.但是,如果您的输入不易生产(即,如果{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"列的替代方法.