The choice depends on the file size, relative to the available memory.
The simplest solution is going to be to read one of the files into an
in-memory data structure, such as an ArrayList. Once you have done that,
you can read the other file a line at a time and output all pairs for
that line.

The fact that outputting all pairs seems reasonable to you suggests that
at least one of the files is reasonably small. For example, if the
smaller file contains a million lines, the list of pairs has at least
10**12 elements.

However, if neither file fits in memory, you are going to have to open
one of them as a RandomAccessFile. For each line of the other file, you
need to seek(0) in the RandomAccessFile and use readLine to advance
through it a line at a time.

Patricia

There's a simple solution to this problem: use a relational database.
Load each list into a separate table and then do a join. The result is
exactly what you want.

Here's a test script I ran using Postgres:
==========================================
create table atab ( a char(3) );
create table btab ( b char(3) );
insert into atab ( a ) values ( 'aaa' );
insert into atab ( a ) values ( 'bbb' );
insert into atab ( a ) values ( 'ccc' );
insert into atab ( a ) values ( 'ddd' );
select a from atab;

insert into btab ( b ) values ( 'eee' );
insert into btab ( b ) values ( 'fff' );
insert into btab ( b ) values ( 'ggg' );
insert into btab ( b ) values ( 'hhh' );
insert into btab ( b ) values ( 'iii' );

select b from btab;

select a,b from atab, btab;

drop table atab;
drop table btab;

and here is the output from the three SELECT statements:
========================================================
  a
-----
 aaa
 bbb
 ccc
 ddd
(4 rows)

  b
-----
 eee
 fff
 ggg
 hhh
 iii
(5 rows)

  a  |  b
-----+-----
 aaa | eee
 aaa | fff
 aaa | ggg
 aaa | hhh
 aaa | iii
 bbb | eee
 bbb | fff
 bbb | ggg
 bbb | hhh
 bbb | iii
 ccc | eee
 ccc | fff
 ccc | ggg
 ccc | hhh
 ccc | iii
 ddd | eee
 ddd | fff
 ddd | ggg
 ddd | hhh
 ddd | iii
(20 rows)

...and the beauty of this approach is that the file sizes are only
limited by the disk space available for the database. Its fast too:

$ time psql -f dbtest.sql >dbtest.txt


real    0m0.088s
user    0m0.002s
sys     0m0.011s

This was run on a 256 MB, 866 MHz NetVista running Postgres 8.2.5 under
Linux (Fedora Core 7).

Obligatory Java content: If this is written in Java you'd use JDBC to
insert the files into the tables and write the file containing the
output. If you use the Derby database you can have an all-Java solution.
I ran the test under Postgres because that's what I have installed.

However, there may be faster approaches. Its likely that the database
has table loading utilities that will be at least as fast as anything
you can write (e.g. the Postgres COPY verb). If the output must simply
go to a file a script may handle this too: I'd probably just pipe the
SELECT output through gawk to adjust the line format and remove the
header and trailer lines.