Generate all possible combinations for Columns(cross join or Cartesian product)

I have a Google SpreadSheets doc with three columns A, B and C.

I need to populate the Column C with all the possible combinations of the values in Columns A and B. Please take a look a the capture to see what I mean.

I found this to be done in Excel, here, but it doesn't work in google spreadsheets.

The formula should be useful even for more columns (e.g.: four instead of two)

Can I do this?

Update 201810

Original formula crashes for a big dataset. I described a way to make cross-join with any size of data here.

Try formula:

=ArrayFormula(transpose(split(rept(concatenate(A2:A&char(9)),counta(B2:B)),char(9)))
 &" "&transpose(split(concatenate(rept(B2:B&char(9),counta(A2:A))),char(9))))

The result:

car red
train red
car yellow
train yellow
car blue
train blue

You may use it again to add another list:

The formula is in cells C2 and E2,

C2 is:

=ArrayFormula(transpose(split(rept(concatenate(A2:A&char(9)),counta(B2:B)),char(9)))&" "&transpose(split(concatenate(rept(B2:B&char(9),counta(A2:A))),char(9))) )

and E2 is:

=ArrayFormula(transpose(split(rept(concatenate(C2:C&char(9)),counta(D2:D)),char(9)))&" "&transpose(split(concatenate(rept(D2:D&char(9),counta(C2:C))),char(9))) )

in post-pandemic new world we can solve this with:

=INDEX(FLATTEN(A2:A3&" "&TRANSPOSE(B2:B4)))

to account for future expansion we can do:

=INDEX(FLATTEN(FILTER(A2:A; A2:A<>"")&" "&TRANSPOSE(FILTER(B2:B; B2:B<>""))))

for 3 columns:

=INDEX(FLATTEN(FLATTEN(
 FILTER(A2:A; A2:A<>"")&" "&TRANSPOSE(
 FILTER(B2:B; B2:B<>"")))&" "&TRANSPOSE(
 FILTER(C2:C; C2:C<>""))))

4 columns:

=INDEX(FLATTEN(FLATTEN(FLATTEN(
 FILTER(A2:A; A2:A<>"")&" "&TRANSPOSE(
 FILTER(B2:B; B2:B<>"")))&" "&TRANSPOSE(
 FILTER(C2:C; C2:C<>"")))&" "&TRANSPOSE(
 FILTER(D2:D; D2:D<>""))))