Cartesian product of two files (as sets of lines) in GNU/Linux

Question

How can I use shell one-liners and common GNU tools to concatenate lines in two files as in Cartesian product? What is the most succinct, beautiful and "linuxy" way?

For example, if I have two files:

$ cat file1
a
b
$ cat file2
c
d
e

The result should be

a, c
a, d
a, e
b, c
b, d
b, e

Answer 1

Edit: Oops... Sorry, I thought this was tagged python...

If you have python 2.6:

from itertools import product
print('\n'.join((', '.join(elt) for elt in (product(*((line.strip() for line in fh) for fh in (open('file1','r'), open('file2','r'))))))))

a, c
a, d
a, e
b, c
b, d
b, e

If you have python pre-2.6:

def product(*args, **kwds):
    '''
    Source: http://docs.python.org/library/itertools.html#itertools.product
    '''
    # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
    # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111
    pools = map(tuple, args) * kwds.get('repeat', 1)
    result = [[]]
    for pool in pools:
        result = [x+[y] for x in result for y in pool]
    for prod in result:
        yield tuple(prod)
print('\n'.join((', '.join(elt) for elt in (product(*((line.strip() for line in fh) for fh in (open('file1','r'), open('file2','r'))))))))

Answer 2

Solution 1:

perl -e '{use File::Slurp; @f1 = read_file("file1"); @f2 = read_file("file2"); map { chomp; $v1 = $_; map { print "$v1,$_"; } @f2 } @f1;}'

Answer 3

Here's shell script to do it

while read a; do while read b; do echo "$a, $b"; done < file2; done < file1

Though that will be quite slow. I can't think of any precompiled logic to accomplish this. The next step for speed would be to do the above in awk/perl.

awk 'NR==FNR { a[$0]; next } { for (i in a) print i",", $0 }' file1 file2

Hmm, how about this hacky solution to use precompiled logic?

paste -d, <(sed -n "$(yes 'p;' | head -n $(wc -l < file2))" file1) \
          <(cat $(yes 'file2' | head -n $(wc -l < file1)))

Answer 4

The mechanical way to do it in shell, not using Perl or Python, is:

while read line1
do
    while read line2
    do echo "$line1, $line2"
    done < file2
done < file1

The join command can sometimes be used for these operations - however, I'm not clear that it can do cartesian product as a degenerate case.

One step up from the double loop would be:

while read line1
do
    sed "s/^/$line1, /" file2
done < file1

Answer 5

awk 'FNR==NR{ a[++d]=$1; next}
{
  for ( i=1;i<=d;i++){
    print $1","a[i]
  }
}' file2 file1

# ./shell.sh
a,c
a,d
a,e
b,c
b,d
b,e

Answer 6

OK, this is derivation of Dennis Williamson's solution above since he noted that his does not read from file:

$ echo {`cat a | tr "\012" ","`}\,\ {`cat b | tr "\012" ","`}$'\n'
a, c
 a, d
 a, e
 b, c
 b, d
 b, e

Answer 7

A solution using join, awk and process substitution:

join <(xargs -I_ echo 1 _ < setA) <(xargs -I_ echo 1 _ < setB)
  | awk '{ printf("%s, %s\n", $2, $3) }'