This is based on an actual need I encountered, a TestDataGenerator for a system with long compound primary keys and lots of tables. (Whether it was good schema design or not was out of my control. I had to live with it as it was.)

Given a bunch of lists with potentially different lengths, produce the resulting lists of every combination. Using EssExpression-like syntax, here is an example:

  (foo bar) (a b c) (1 2)

Results in:

  (foo a 1)
  (foo a 2)
  (foo b 1)
  (foo b 2)
  (foo c 1)
  (foo c 2)
  (bar a 1)
  (bar a 2)
  (bar b 1)
  (bar b 2)
  (bar c 1)
  (bar c 2)

There are 12 results because we had sets of 2 x 3 x 2. Note that you should not assume one can know the number of input lists ahead of time. Some of the solutions given seem to hard-wire the quantity into code. Thus, they '''falsely assume just 3 lists''', which wouldn't be known at compile time or during the programming stage. 

Perhaps we should mark or separate those solutions that hard-wire in 3 lists from those that don't.

----
PrologLanguage:

comb([],[]).

comb([L|T],[X|Lo]) :- member(X,L), comb(T,Lo).

:- findall(X,comb([[a,b,c],[1,2,3],[i,ii,iii]],X),L), write(L).

Writes:
[[a, 1, i], [a, 1, ii], [a, 1, iii], [a, 2, i], [a, 2, ii], [a, 2, iii], [a, 3, i], [a, 3, ii], [a, 3, iii], [b, 1, i], [b, 1, ii], [b, 1, iii], [b, 2, i], [b, 2, ii], [b, 2, iii], [b, 3, i], [b, 3, ii], [b, 3, iii], [c, 1, i], [c, 1, ii], [c, 1, iii], [c, 2, i], [c, 2, ii], [c, 2, iii], [c, 3, i], [c, 3, ii], [c, 3, iii]]

For free you can get comb([a,1,i], List) which will be true if [a,1,i] is a valid combination of List.


----
VisualBasicNine

Query comprehensions make this a snap.  

''But it appears to hard-wire in a quantity of 3 list, so technically if fails.''

 Dim seq1 as String() = { "foo", "bar" }
 Dim seq2 as String() = { "a", "b", "c" }
 Dim seq3 as Integer() = { 1, 2 }

 Dim query = From a In seq1 From b In seq2 From c In seq3 _
             Select New With { .First=a, .Second=b, .Third=c }

 For Each item In query 
     Console.Write''''''Line("({0} {1} {2})", item.First, item.Second, item.Third)
 Next

This example produced a sequence of statically typed records. If you prefer a loosely typed array, you'd rewrite the query like this:

 Dim seq1 as String() = { "foo", "bar" }
 Dim seq2 as String() = { "a", "b", "c" }
 Dim seq3 as Integer() = { 1, 2 }

 Dim query = From a In seq1 From b In seq2 From c In seq3 _
             Select New Object() { a, b, c }

 For Each item In query 
     Console.Write''''''Line("({0} {1} {2})", item(0), item(1), item(2))
 Next


-- DonBox

   'A not hard-wired implementation, which sadly doesn't use any of the flashier features of VisualBasicNine (only TypeInference, I think)
   Sub Main()
      'Waiting for VisualBasicTen and its list initialization SyntacticSugar
      'Waiting for VisualBasicTen and its CoVariance support, so I can make this list a List of String
      Dim List1 As New List(Of Object)
      List1.Add("foo")
      List1.Add("bar")

      Dim List2 As New List(Of Object)
      List2.Add("a")
      List2.Add("b")
      List2.Add("c")

      Dim List3 As New List(Of Object)
      List3.Add(1)
      List3.Add(2)

      Dim Result''''''List = Cross''''''Join''''''Lists(List1, List2, List3)

   End Sub

   Function Cross''''''Join''''''Lists(ByVal Param''''''Array Lists() As List(Of Object)) As List(Of List(Of Object))
      Dim Result''''''List As New List(Of List(Of Object))

      Dim Result''''''List''''''Length = 1
      For Each List In Lists
         Result''''''List''''''Length *= List.Count
      Next List

      'Initializing the return variable
      For Result''''''List''''''Count = 1 To Result''''''List''''''Length
         Result''''''List.Add(New List(Of Object))
      Next Result''''''List''''''Count

      'Magic variables suffering from BadVariableNames, wouldn't mind finding better names for them
      Dim Dwindling''''''Divisor = Result''''''List''''''Length
      Dim Slower''''''Dwindling''''''Divisor = Result''''''List''''''Length

      'Using magic variables to calculate the correct index of the item
      For Lists''''''Count = 0 To Lists.Count - 1

         Dwindling''''''Divisor \= Lists(Lists''''''Count).Count

         For Result''''''List''''''Count = 0 To Result''''''List''''''Length - 1
            Result''''''List(Result''''''List''''''Count).Add(Lists(Lists''''''Count)((Result''''''List''''''Count Mod Slower''''''Dwindling''''''Divisor) \ Dwindling''''''Divisor))
            'Basically, the index wraps around quicker and quicker with every next list
         Next Result''''''List''''''Count

         Slower''''''Dwindling''''''Divisor \= Lists(Lists''''''Count).Count

      Next Lists''''''Count

      Return Result''''''List
   End Function

-- Alexei Marine

----
CsharpLanguage

Query comprehensions make this a snap.  

 var seq1 = new string[] { "foo", "bar" };
 var seq2 = new string[] { "a", "b", "c" };
 var seq3 = new int[] { 1, 2 };

 var query = 
     from a in seq1 
     from b in seq2
     from c in seq3
     select new {
         First=a, Second=b, Third=c
     };

 foreach (var item in query) 
     Console.Write''''''Line("({0} {1} {2})", item.First, item.Second, item.Third);

This example produced a sequence of statically typed records. If you prefer a loosely typed array, you'd rewrite the query like this:

 var seq1 = new string[] { "foo", "bar" };
 var seq2 = new string[] { "a", "b", "c" };
 var seq3 = new int[] { 1, 2 };

 var query = 
     from a in seq1 
     from b in seq2
     from c in seq3
     select new object[] { a, b, c };

 foreach (var item in query) 
     Console.Write''''''Line("({0} {1} {2})", item[0], item[1], item[2]);

-- DonBox
----
IokeLanguage

	List allCombinations = method(
		result = list(list())
		self each(element,
			temp = result. result = list()
			element each(x, temp each(y, result<<list(y, x) flatten)))
		result)

	[["foo", "bar"], ["a", "b", "c"], [1, 2]] allCombinations println

	[["foo", "bar", "baz"], ["a", "b", "c"], [1, 2, 3], [:symbol, :othersymbol]] allCombinations println

Or you could do an almost word-for-word translation of the recursive RubyLanguage solution given below.

-- JasonGrossman

----
'''JavaLanguage'''

''1.5''
 new P''''''roductList(
	new Set( "foo", "bar"),
	new Set( "a", "b", "c" ),
	new Set( 1, 2 )
 ).forEach(new Print());

''1.2< 1.x <1.5''
 new P''''''roductList(new Set[]{
	new Set( new String[]{ "foo", "bar" } ),
	new Set( new String[]{ "a", "b", "c" } ),
	new Set( new Integer[]{ new Integer(1), new Integer(2) } )
 }).forEach(new Print());

The 1.5 version should produce exactly the same class file as the 1.x version.

The constructors take advantage of a new 1.5 feature allowing the use of a variable number of parameters, equivalent to "REST" or "..." in other languages.

"P''''''roductList" is a cartesian product on its parameters. It is 'live', in that changes to it write through to the originals (although it isn't quite doing the right thing) and changes to the originals show in the product. I would've used a Set instead of a List/bag-like-collection, except that I'm not sure we're guaranteed to have orthogonal input.

"forEach(...)" accepts a method object (as described in BlocksInJava) and, in this case, applies each combination to that method.

"Print" is one of those classes which I use a lot for testing, simply printing whatever is sent to it on standard output (or another stream if one is suppled). I also have "P''''''rintList" which shows a count beside each individual output.

-- WilliamUnderwood

I wrote a combination generator in Java as part of an example in Fit (see http://fit.c2.com/wiki.cgi?AllCombinations). Here is the code:

    protected void combinations() {
        combinations(0, new ArrayList(lists));
    }

    protected void combinations(int index, List combination) {
        if (index == lists.size()) {
            doCase(combination);
        } else {
            List files = (List)lists.get(index);
            for (Iterator i=files.iterator(); i.hasNext(); ) {
                combination.set(index, i.next());
                combinations(index+1, combination);
            }
        }
    }
The much more difficult algorithm is to generate a minimal set of tuples that includes all pairs. This can be much smaller than all combinations and is used in testing where pairing of features is considered sufficient to find bugs in feature interactions.

-- WardCunningham

----
'''RubyLanguage'''

 def combinations(list, *rest)
   crest = rest.empty? ? [[]] : combinations(*rest)
   list.inject([]) { |combs, item| combs + crest.map { |comb| [item] + comb } }
 end

-- JasonArhart

I like the design of that, but I find the style hard to read.
* "rest" doesn't communicate to me that we're talking about additional list arguments.
* "item" is unnecessarily verbose since "i" is idiomatic (personal taste, not value judgement).
* It's easier to read ternary operations w/ non-trivial arguments, when the second alternative is wrapped onto the next line.
* It's easier to read nested blocks when super-blocks use do..end style rather than {..}.
* Of the synonymous "map" and "collect" methods, I think "collect" communicates better in this case.

 def combinations(list1, *more_lists)
   crest = more_lists.empty? ? [[]] : 
                               combinations(*more_lists)
   list1.inject([]) do |combs, i| 
     combs + crest.collect { |comb| [i] + comb } 
   end
 end

-- SteveJorgensen

Using "product" from Ruby 1.9:
 def combinations(list, *rest)
   list.product(*rest)
 end

----
'''UnixShell'''

  echo {foo,bar}\ {a,b,c}\ {1,2}\\n

This feature (originally invented by BillJoy for c shell circa 1978) works in tcsh and bash, but does not exist in many of the Bell Labs-descended shells. The \\n part is shell-dependent, but works with tcsh. With bash, instead pipe to tr.

Ward said: "The much more difficult algorithm is to generate a minimal set of tuples". The tcsh solution is e.g.

   echo {foo,bar}\ {a,a,a}\ {1,2}\\n | sort -b -u

-- DougMerritt

----
'''SchemeLanguage'''

  (map (lambda (first)
         (map (lambda (second)
                (map (lambda (third)
                       (list first second third))
                     '(1 2)))
              '(a b c)))
       '(foo bar))

or, for an arbitrary number of arguments

  (define (product . args)
    (if (null? args)
        (list '())
        (apply append
               (map (lambda (rest)
                      (map (lambda (first)
                             (cons first rest))
                           (car args)))
                    (apply product (cdr args))))))

Another in SchemeLanguage
 (define (crossmap func list1 list2)
   (define (cm-helper l1 l2)
     (cond ((null? l1) '())
           ((null? l2) (cm-helper (cdr l1) list2))
           (else       (cons (func (car l1) (car l2))
                             (cm-helper l1 (cdr l2))))))
   (cm-helper list1 list2))

 (define (allcmb . args)
   (cond ((null? args) '(()))
         (else (crossmap cons (car args) (apply allcmb (cdr args))))))
...and another in SchemeLanguage
 (define (allcmb . args)
   (define (ac-helper sofar args thunk)
     (cond ((null? args) (thunk (reverse sofar)))
           (else (for-each (lambda (elt) (ac-helper (cons elt sofar)
                                                    (cdr args)
                                                    thunk))
                           (car args)))))
   (let ((ret '()))
     (ac-helper '() args (lambda (x) (set! ret (cons x ret))))
     (reverse ret)))

It is even trivial to make a quick syntax for list comprehensions, with 
wider reuse possibilities: 

  (define (return x) (list x))
   
  (define-syntax collect
    (syntax-rules () 
      ((collect () . body) 
       (begin . body))
      ((collect ((x list) . bindings) . body)
       (apply append (map (lambda (x) (collect bindings . body))
                          list)))))
which can then be used as follows:
   
  (collect ((x '(foo bar))
            (y '(a b c))
            (z '(1 2)))
    (return (list x y z)))
to give the required result. By the way, collect and return define an instance of a monad (see OnMonads). In this case the list monad.

----
'''PerlLanguage'''

 sub crossmap {
   my($func, $list1, $list2) = @_;
   my(@ret) = ();
   for my $x1 (@$list1) {
     for my $x2 (@$list2) {
       push(@ret, $func->($x1, $x2));
     }
   }
   return \@ret;
 }

 sub allcomb {
   return [[]] if(@_ == 0);
   my($first, @rest) = @_;
   return crossmap(sub {[$_[0],@{$_[1]}]}, $first, allcomb(@rest));
 }
''allcomb([1, 2, 3], [qw(a b c)]) => [[1,'a'],[1,'b'],[1,'c'],[2,'a'],[2,'b'],[2,'c'],[3,'a'],[3,'b'],[3,'c']]''

A recursive, functional version returning a list:

 sub combs {
   return ([]) if !scalar(@_);

   my $atoms = shift;

   map {$tuple = $_;
     map([$_, @{$tuple}], @{$atoms})
   } combs(@_)
 }

A slightly more readable, non-recursive version returning a list:

 sub combs {
   my @result = ([]);
   foreach my $atoms (@_) {
     @result = map { my @tuple = @$_;
                     map [@tuple, $_], @$atoms }
                   @result;
   }
   @result
 }

Functional version using reduce():
 use List::Util qw(reduce);
 sub combs {
   @{ (reduce { [map { my @tuple = @$_;
                       map [@tuple, $_], @$b }
                     @$a] }
              [[]], @_) }
 }

glob() can also be used to do some cool combination stuff on strings:
 @mycombs = glob('{foo,bar}_{1,2,3}_{a,b,c}');
  => ('foo_1_a', 'foo_1_b', 'foo_1_c',
      'foo_2_a', 'foo_2_b', 'foo_2_c',
      'foo_3_a', 'foo_3_b', 'foo_3_c',
      'bar_1_a', 'bar_1_b', 'bar_1_c',
      'bar_2_a', 'bar_2_b', 'bar_2_c',
      'bar_3_a', 'bar_3_b', 'bar_3_c')
----
'''PerlSix'''
    [X] @list_of_lists; # X is the cross operator.  It's a builtin to do just that.
Programming trick:
    eval [~] (), gather for(@list_of_lists>>.perl) {
        " X $_"
    }

----
'''CommonLisp'''

 (defun combine (&rest lists)
   (flet ((combine-helper (xs ys)
            (loop for x in xs
                  append (loop for y in ys collect (cons x y)))))
     (reduce #'combine-helper lists :initial-value (list nil) :from-end t)))

----
'''PythonLanguage'''

A readable version:
 def combos(curr, *rest):
     if rest:
         rest = combos(*rest)
     else:
         rest = [[]]
     for y in rest:
         for x in curr:
             yield [x] + y

 for elem in combos(a,b,c):
     print elem
And now for something completely different:
 def p(c,*r):
  for y in(r and p(*r)or[[]]):
   for x in c:yield[x]+y

-- TaroOgawa

Similarly, via my favourite trick, ListComprehension''''''s:

 def all_combinations(*lists):
   if not lists: return [[]]
   return [[first] + rest for first in lists[0] for rest in all_combinations(*lists[1:])]
which, of course, can be made a one-liner:
 def p(*l): return [lambda:[[]], lambda:[[f] + r for f in l[0] for r in p(*l[1:])]][bool(l)]()
The selection idiom has been chosen carefully to ensure the behaviour is the same in all cases. The lambda's are then needed to delay evaluation until after the selection is done.

These versions offer the interesting quirk that they may be called with no arguments, resulting in a list of one item, which is a list of no items: [[]]. I think this is natural: if you add zero lists to the set of lists, then you multiply the total number of combinations by one, and add no elements to each combination. Thus the IdentityResult for a set of zero lists ought to have the MultiplicativeIdentity (1) of elements, containing the AdditiveIdentity (0) of elements each.

A few hours later, this version:

 def p(*l): return [[f] + r for f in l[:1] and l[0] for r in p(*l[1:])] or [[[]],[]][bool(l[:1])]
This works by making the list comprehension succeed and return empty when l is empty (by providing l[:1] which is also an empty list), and then returning [[]] if both l and the list comprehension are empty. (We have to avoid changing the result when l is *not* empty.)

Also, as further justification for the zero-argument behaviour: the invariant

len(p(*[range(x)]*y)) == x ** y

is preserved even when y==0.

-- KarlKnechtel

Using reduce():
 def all_combinations(*lists):
   return reduce(lambda results, curr: [xs + [x] for xs in results for x in curr], lists, [[]])

In Python 2.6, there is a library function "product" that does exactly this:
 import itertools
 itertools.product(*lists)

----
'''LogoLanguage'''

It's already there in UCBLogo:
  ? show crossmap "list [[a b] [c d] [e f]]
  [[a c e] [a c f] [a d e] [a d f] [b c e] [b c f] [b d e] [b d f]]
  ? 

----
'''SuperCollider'''

   // using the allTuples built-in function
   [[\foo, \bar],[\a, \b, \c], [1, 2]].allTuples;

   // using ListComprehension''''''s
   all {: [x,y,z], x <- [\foo, \bar], y <- [\a, \b, \c], z <- [1, 2] }

----
Why not do it directly in the database? In Oracle's flavour, that would be:

   CREATE OR REPLACE TYPE Number''''''List AS TABLE OF NUMBER;
   /
   CREATE OR REPLACE TYPE String''''''List AS TABLE OF VARCHAR2(3);  -- pick your length; 3 is enough in this case
   /
   SELECT
     *
   FROM
     table(Number''''''List(1, 2)),
     table(String''''''List('a', 'b', 'c')),
     table(String''''''List('foo', 'bar'))
   /

----
PowerLoops

Untested and probably broken; adapted (probably badly) from example on above page.

 input Set : array 1 .. n of list of string
 variable 1
     Subset : array 1 .. n of integer 
 nest Subset''''''Index := 1 to n 
    for Subset[ Subset''''''Index ] := 1 to n do 
        if OkSoF''''''ar(Subset''''''Index) then 
            deeper
        end
        Subset
    end
 do 
    write(Set[Subset[1..n]])
 end

----
I am not sure, but some of these seem to hard-wire the assumption of 3 lists into the code. Please identify such examples if you make one (the challenge is really potentially many lists). Assigning sample input to a variable is fine as long as it is clear what is sample assignment.

----
As usual '''HaskellLanguage''' makes a good showing.
 cartesian = foldr (\xs yss -> [ x:ys | x <- xs, ys <- yss ]) [[]]

This works on any number of arguments, e.g.

 *Main> cartesian [["fred","barney","wilma"],["foo","bar"],["smurf", "snork"]]
 [["fred","foo","smurf"],["fred","foo","snork"],["fred","bar","smurf"],["fred","bar","snork"],
 ["barney","foo","smurf"],  ["barney","foo","snork"],["barney","bar","smurf"],["barney","bar","snork"],
 ["wilma","foo","smurf"],["wilma","foo","snork"],["wilma","bar","smurf"],["wilma","bar","snork"]]
 *Main>

One big downside is that everything needs to be the same type (because elements of a list must be the same type), but brevity has its costs...

There's a much simpler Haskell implementation:
 sequence

 Prelude> sequence [["fred","barney","wilma"],["foo","bar"],["smurf", "snork"]]
 [["fred","foo","smurf"],["fred","foo","snork"],["fred","bar","smurf"],["fred","bar","snork"],
 ["barney","foo","smurf"],["barney","foo","snork"],["barney","bar","smurf"],["barney","bar","snork"],
 ["wilma","foo","smurf"],["wilma","foo","snork"],["wilma","bar","smurf"],["wilma","bar","snork"]]

This is because the List monad is the cartesian product. This monad instance is often used for backtracking and the like. -- ShaeErisson

----
'''JayLanguage'''

J has an "every combination" operator '''{''' :

 all=.,{(;:'foo bar');(;:'alice bob eve');(<;:'cat dog rat mouse')
This creates a list.  The following selects four of the members
(displayed with the pretty boxes removed).
   >>0 4 19 23 { all
 foo  
 alice
 cat  
 
 foo  
 bob  
 cat  
 
 bar  
 bob  
 mouse
 
 bar  
 eve  
 mouse

-- MarcThibault

----

TemplateMetaprogramming

This would be quite a bit shorter if C++ bothered including much in the way of standard metaprogramming components.

Input: A typelist of typelists L1,L2,...,LN
Output: A typelist of (|L1|*|L2|*...*|LN|) typelists, each with N elements, in order, one from each of L1..LN.

 // Typelist = tycons<Type,Typelist> | tynil
 class tynil; 
 template<typename First,typename Rest> class tycons;

 namespace tyl {  // typical typelist functions (sorting, folding, mapping, searching, etc.)
   // foldr: Fold over a typelist (starting by combining I0 with the last item, and working backwards)
   //   Inputs: 
   //     L  -- a typelist
   //     I0 -- initial input to fold.  If fold over empty typelist, I0::type is final answer.
   //     fn<I,T> is a typefunction taking an input I (derived from I0 using fn repeatedly) and T from the list to produce the next 'I'.
   //         fn<I,T>::type is the final answer over most lists.
   //   Outputs:
   //      '::type' - answer of overall 'fold' 
   template<template<typename I,typename T> class fn, typename I0, typename L> class foldr;
   template<template<typename I,typename T> class fn, typename I0> class foldr<fn,I0,tynil> {
      friend class foldr;
      typedef I0 result;
   public:
      typedef typename result::type type;
   };
   template<template<typename I,typename T> class fn, typename I0, typename T, typename R> class foldr<fn,I0,tycons<T,R> > {
      friend class foldr;
      typedef typename foldr<fn,I0,R>::result result_of_rest;
      typedef typename fn<result_of_rest,T>   result;
   public:
      typedef typename result::type type;     
   };

   // append: (Typelist,Typelist)->Typelist
   template<typename L1, typename L2>
   class append {
     template<typename I, typename T> struct fn_append { 
       typedef tycons<T,typename I::type> type;  // cons last to first of L1 onto L2
     };
     struct I0 { typedef L2 type; }; // initial result is L2
   public:
     typedef typename foldr<fn_append,I0,L1>::type type;
   };

   // flatten: (Typelist of Typelists)->Typelist
   template<typename L>
   class flatten {
     template<typename I,typename L> struct fn_flatten {
        typedef typename append<L,typename I::type>::type type;  // append last list onto result thus far
     };
     struct I0 { typedef tynil type; }; // start by appending onto empty list
   public:
     typedef typename foldr<fn_flatten,I0,L>::type type;
   };

   // map: ((Type->Type),Typelist)->Typelist
   template<template<typename> class fn, typename L>
   class map {
      struct I0 { typedef tynil type; };
      template<typename I,typename T> struct fn_map {
        typedef typename fn<T>::type T_result;
        typedef typename I::type     L_result;
        typedef tycons<T_result,L_result> type;
      };
   public:
     typedef typename foldr<fn_map,I0,L>::type type;
   };

   // pair-wise:
   //  Take two typelists, and return a result of applying function to every combination
   //  of components of L1 and L2.  This is done by mapping an action over L2 that returns
   //  results for every item in L1 in a list, then flattening that list.
   template<template<typename T1,typename T2> class fn, typename L1, typename L2>
   class pairwise {
     template<typename _T2> struct fn_L1_over_L2 {
         template<typename _T1> struct fn_L1_onto_T2 {
           typedef typename fn<_T1,_T2>::type type;
         };
         typedef typename map<fn_L1_onto_T2,L1>::type type; // list of length |L1|
     };
     typedef typename map<fn_L1_over_L2,L2>::type lresults; // list of length |L2|, each a list of length |L1|
   public:
     typedef typename flatten<lresults>::type type;  // list of length |L1|*|L2|
   };

   // All Combos ('nwise'... I define 'combinations' and 'permutations' over a list of single types)
   //   Input:  L2 -- a list of typelists
   //   Output: '::type' -- a list of combinations
   // The function that results in a foldr over a list will create a list-of-lists resulting
   // from appending the 'cons' results of each element from one list onto each list of another
   // (with 'I0' consisting of tycons<tynil,tynil> -- a list containing one element: the empty list).
   template<typename L2> class nwise {
     template<typename T, typename L> struct pairwise_cons {typedef tycons<T,L> type;};
     template<typename I, typename L> struct fn_nwise {
       typedef typename pairwise<pairwise_cons,L,typename I::type>::type type;
     };
     struct I0 {
       typedef tycons<tynil,tynil> type; // initial result
     };
   public:
     typedef typename foldr<fn_nwise,I0,L2>::type type;
   };
 } // end namespace tyl

 //=========//
 // Testing //
 //=========//
 #include <typeinfo>
 template<typename T>
 class typrint {
 public: 
     template<typename W> static void print(W& write) { 
         const char* pName = typeid(T).name();
         if(strncmp(pName,"class ",6) == 0) pName += 6;
         else if(strncmp(pName,"struct ",7) == 0) pName += 7;
         write(pName);
     }
 };
 template<> 
 class typrint<tynil> {
 public:
     template<typename W> static void print(W& write) { write("[]"); }
 };
 template<typename T, typename R> 
 class typrint< tycons<T,R> > {
     template<typename L> struct inner_print;
     template<> struct inner_print<tynil> {
         template<typename W> static void print(W& write) {/* print nothing */}
     };
     template<typename iT, typename iR> 
     struct inner_print<tycons<iT,iR> > {
         template<typename W> static void print(W& write) {
             write(", ");
             typrint<iT>::print(write);
             inner_print<iR>::print(write);
         }
     };
 public:
     template<typename W> static void print(W& write) { 
         write("[");
         typrint<T>::print(write);
         inner_print<R>::print(write);
         write("]");
     };
 };
    // simple writer to standard output stream (I'd prefer a pretty-printer, but I'm not going to define one here).
 #include <fstream>
 template<typename T> struct type{}; // capture type itself as a tag (special action for writers)
 class ostream_writer {
     std::ostream& out;
 public:
     ostream_writer(std::ostream& _out) : out(_out) {}
     ~ostream_writer() {}
     template<typename T> ostream_writer& operator()(const T& t) { out << t; return *this;}
     template<typename T> ostream_writer& operator()(const type<T>& t) {
         typrint<T>::print(*this);
         return *this;
     };
 };
    // 'values' in lists are types.
 struct foo; struct bar; 
 struct a; struct b; struct c;
 template<unsigned n> struct num{enum{value=n};};
    // I didn't bother defining a list builder, above, so I'll do this by hand.
 typedef tycons<foo,tycons<bar,tynil> >        list1; 
 typedef tycons<a,tycons<b,tycons<c,tynil> > > list2;
 typedef tycons<num<1>,tycons<num<2>,tynil> >  list3;
 typedef tycons<list1,tycons<list2,tycons<list3,tynil> > >  list_of_lists;
 typedef tyl::nwise<list_of_lists>::type       all_combos;
    // the actual test code... currently performed by human inspection
 static void all_combo_test() {
     std::ofstream outfile("result.txt");
     ostream_writer myWriter(outfile);
     myWriter("Original List: ")(type<list_of_lists>())("\n");
     myWriter("All Combinations: ")(type<all_combos>())("\n");
 }
'''Test Results:''' 
*'''Original List:''' [[foo, bar], [a, b, c], [num<1>, num<2>]]
*'''All Combinations:''' [[foo, a, num<1>], [bar, a, num<1>], [foo, b, num<1>], [bar, b, num<1>], [foo, c, num<1>], [bar, c, num<1>], [foo, a, num<2>], [bar, a, num<2>], [foo, b, num<2>], [bar, b, num<2>], [foo, c, num<2>], [bar, c, num<2>]]

I was rather surprised... I wrote everything prior to the test on this wiki, and it ran without modification (though there were some complaints about decorated name lengths for some of the typelists).  I usually make a few typographical errors.  Anyhow, this sort of combination is actually useful at times... e.g. when ensuring that every possible input-combination is defined for a multiple-dispatch over variant types.

----
With CeePlusPlus using FunctoidsInCpp and the BoostTupleLibrary, it is possible to do this:

    List<tuple<string,string,int> > ssil =
      list_with(foo,bar) ^bind^ lambda(X)[ 
         list_with(a,b,c) %bind% lambda(Y)[ 
            list_with(1,2) %bind% lambda(Z) [
                unitM<ListM>()[ makeTuple3[X,Y,Z] ] 
            ]
         ] 
      ];

where foo,bar,a,b,c are initialised to strings.  X,Y,Z are polymorphic lambda variables. ListM is a monad implementation. Output can be obtained like this:

   while( !null(ssil) ) {
      cout << get<0>(head(ssil)) << "," << get<1>(head(ssil)) 
                                 << "," << get<2>(head(ssil)) << endl;
      ssil = tail(ssil);
   }

to give this:

 foo,a,1
 foo,a,2
 foo,b,1
 foo,b,2
 foo,c,1
 foo,c,2
 bar,a,1
 bar,a,2
 bar,b,1
 bar,b,2
 bar,c,1
 bar,c,2

Not (as yet) generalisable to any number of lists, and the type of the result needs to be known.

-- JohnFletcher

''Not (as yet) generalisable to any number of lists, and the type of the result needs to be known.''  That sounds like an interesting challenge.  You obviously won't be able to generalize to any number of lists by any solution that involves hand-nesting them, and implicit construction of a result-type is almost /always/ kludgy in C++.  However, this might be doable with something like an input sequence that builds some sort of functor (either with implicit construction of the temporary result, or storage until some sort of 'build' command is given or conversion to a tuple is required).
   myComboBuilder(...options...)(list1)(list2)(list3)(list4)...(listN).build()  // (I hate the '<<' syntax...).
I might give it a try after work.  We'd probably benefit from making the final list-construction lazy, too (at least as an option)... lazy multi-value approaches are very good for AI searches and other memory-intensive tasks, especially with some means of discarding the first elements of the list before processing the back ones. 
   (foo|bar|baz)(a|b|c)(1|2|3)  -- total 27 tuples of 3 items each
     => (foo (a|b|c)(1|2|3))|((bar|baz)(a|b|c)(1|2|3)) 
     => (foo a (1|2|3))|(foo (b|c)(1|2|3))|((bar|baz)(a|b|c)(1|2|3)) 
     => (foo a 1)|(foo a (2|3))|(foo (b|c)(1|2|3))|((bar|baz)(a|b|c)(1|2|3)) 
Total memory cost if you process and discard the first items before processing the latter items is significantly reduced for large lists (not so much for these smaller ones; the above reduces to a cost of 21 units compared to the full expansion's 81, or to only 12 units if list-components are shared.

You cannot totally avoid ''the type of the result needs to be known'' if you wish to store the resulting combination, but if you wish to pass it forward it shouldn't be difficult (C++ provides implicit type inference ONLY for template-functions... no 'auto' type for return values).  Thus, it might be best to pass the result to a procedure that does everything you ever need with it OR to a template-described 'continuation'.  
  template<typename C''''''omboType, typename T> 
    typename sp_type_build<C''''''omboType,T>::return_type //--> warning!  To STORE this result anywhere, the programmer must hand-write ComboType.
      some_procedure(const C''''''omboType& myCombo, const T& anotherParameter) {
         ...
         return (someExpression);
      }
I think that, until 'auto' type is provided, the ability to handle the type of the result implicitly will be somewhat limited.  I can't recall whether there is any 'auto' type on the table, though, for introduction to the C++ standard (I know it exists in D).

My idea is to try something using VariadicTemplatesForGnuCpp, which although an extension to C++, is heading to be in the new standard. I already have a polymorphic '''plusN''' which will add up a variable number of arguments of mixed types, with control of the return type. This works with an experimental version of the new gcc 4.3.

Using this, the specific makeTuple3 used previously can be generalised to makeTupleN which will work with any number of arguments up to some implementation limit. The main advantage of this is to make it much easier to expand to larger sizes of problem, in using, for example, FunctoidsInCpp codes.

  List<tuple<string,string,int> > ssil =
    list_with(foo,bar) ^bind^ lambda(X)
      [ 
       list_with(a,b,c) %::bind% lambda(Y)
         [ 
	  list_with(1,2) %bind% lambda(Z) 
            [
	     unitM<ListM>()[ makeTupleN[X,Y,Z] ] 
            ]
         ] 
      ];

This does not overcome the problem of binding an arbitrary number of lists, as the outer structure is still needed.

Here is an alternative example where a variadic tuple is constructed as a tuple of lists. This can be extended with lists of different types.

  tuple<List<string>,List<string>,List<int> > lssi = make_tuple(list_with(foo,bar),list_with(a,b,c),list_with(1,2));

Within a template function, this construction can be done without knowing the number or the types of the arguments:

 template<typename... XYZ>
 int foo(const XYZ&... args)
 {
   tuple<XYZ...> it = makeTupleN(args...);
 // Do something with ''it'' in here.

   int n = sizeof... (XYZ);
   return n;
 }

For a fuller explanation of what can be done with variadic templates, see VariadicTemplatesForGnuCpp.

-- JohnFletcher

I can't agree to anything not already part of the C++ standard as being in C++.  That said, I'm definitely looking forward to variadic templates! Writing out template-arguments lists of up to some arbitrary length N (whether N is 3 or 20) is both a royal pain AND an inelegant hack. 

You've since added your 'example' for the use of variadic templates.  It isn't well placed, seeing as it doesn't reveal (as examples are intended to do) that which makes variadic-templates fundamentally 'better':  the ability to handle and create tuples of arbitrary size, an improvement to 'once and only once' code, etc.  What you show here can be done without variadic templates... just not elegantly or for arbitrary-length tuples.

''The example is now further extended above, to avoid too much ThreadMode. Examples can explore the limits of what is possible. All that is here is taken from working code and developing them has been part of the creative process of finding what the limits are in tackling this particular problem.''  

One solution to the example would be to convert from the second type of tuple (''lssi'' above) to the first type (''ssil'' above). I would have liked to make ''lssi'' a list of lists, but that would mean that all the lists would have to be of the same type. Here is an example.
  List<tuple<string,string,int> > ssil =
  lambda() [ compM<ListM>() [ makeTupleN[X,Y,Z] | X <= get<0>(lssi), Y <= get<1>(lssi), Z <= get<2>(lssi) ] ]();
This is a combination of VariadicTemplatesForGnuCpp with monads as defined in FunctoidsInCpp. It is possible to wrap this code in such a way as to choose an implementation depending on the number of lists.
  List<tuple<string,string,int> > list3lists = listSomethingN(list_with(foo,bar),list_with(a,b,c),list_with(1,2));
This is not fully general as there is a limit on the number of lists imposed by the implementation.

-- JohnFletcher

Okay, I've written and tested the version I mentioned above:
   nwise(listOne)(listTwo)(listThree)...(listN) 
will, in '''standard C++''', produce a list of tuples with the correct result.  However, the code for this is awfully long (since I defined tuples, first.  They don't exist in standard C++.  Then I defined visitors.  THEN I got to 'nwise'.)  There is an option of a low-memory approach to iteration, too, which essentially yields one value at a time from the initial lists (the actual result of 'nwise(all)(the)(lists)(you)(want).build()' is a pseudo-iterator or stream that carries, internally, all the iterators for each list.  It can be dereferenced into a tuple-value, and it can be incremented or reset.  You can even grab '.begin()' and '.end()' if you wish, and run it through std::for_each... but that approach is slower than using 'has_next()'.)  It will convert to a list or set of tuples if that is needed.

----

'''OcamlLanguage'''

Using a right fold, like the Haskell example:
 open List (* for fold_right, concat, map *)
 let cartesian list =
   fold_right (fun xs yss ->
                concat (map (fun x ->
                              map (fun ys -> x :: ys)
                                  yss)
                            xs))
              list
              [[]]

This works on any number of arguments, e.g.

 # cartesian [["fred";"barney";"wilma"];["foo";"bar"];["smurf";"snork"]];;
 - : string list list =
 [["fred"; "foo"; "smurf"]; ["fred"; "foo"; "snork"];
  ["fred"; "bar"; "smurf"]; ["fred"; "bar"; "snork"];
  ["barney"; "foo"; "smurf"]; ["barney"; "foo"; "snork"];
  ["barney"; "bar"; "smurf"]; ["barney"; "bar"; "snork"];
  ["wilma"; "foo"; "smurf"]; ["wilma"; "foo"; "snork"];
  ["wilma"; "bar"; "smurf"]; ["wilma"; "bar"; "snork"]]
 #

Everything needs to be the same type, because elements of a list must be the same type.

----

'''SmlLanguage'''

Using a right fold, like the Haskell example:
 fun cartesian list = foldr (fn (xs,yss) =>
                              List.concat (map (fn x =>
                                                 map (fn ys => x :: ys)
                                                     yss)
                                               xs))
                            [[]]
                            list

This works on any number of arguments, e.g.

 - cartesian [["fred","barney","wilma"],["foo","bar"],["smurf","snork"]];
 val it =
   [["fred","foo","smurf"],["fred","foo","snork"],["fred","bar","smurf"],
    ["fred","bar","snork"],["barney","foo","smurf"],["barney","foo","snork"],
    ["barney","bar","smurf"],["barney","bar","snork"],["wilma","foo","smurf"],
    ["wilma","foo","snork"],["wilma","bar","smurf"],["wilma","bar","snork"]]
   : string list list

Everything needs to be the same type, because elements of a list must be the same type.

'''SmlNjLanguage'''

 fun cartesian list = foldr (ListXProd.mapX op::) [[]] list


----

'''JavaScript'''

	function allCombinations(listOfArrays) {
		var res = [];
		listOfArrays[0].map(function inner(i, val) {
			var iter = i, current = val;
			return function(x) {
				var next = current + x;
				if(iter == listOfArrays.length - 1) { res.push(next); }
				else { listOfArrays[i+1].map(inner(i + 1, next)); }
			}
		}(0, ""));
		return res;
	}

Because closures can be fun, too.
     allCombinations([["a", "b"], ["A", "B", "C"], ["f"], ["1", "2"]]);
will return
    ["aAf1", "aAf2", "aBf1", "aBf2", "aCf1", "aCf2", "bAf1", "bAf2", "bBf1", "bBf2", "bCf1", "bCf2"]

----

'''ScalaLanguage'''

Taking the straightforward comprehension:
 for (x <- xs; y <- ys; z <- zs) yield List(x, y, z)
which is syntactic sugar for:
 xs flatMap (x => ys flatMap (y => zs map (z => List(x, y, z))))
which is equivalent to:
 xs flatMap (x => ys flatMap (y => zs flatMap (z => List(List(x, y, z)))))
and generalizing it using recursion, I came up with:
 def combinations[T](lists: List[List[T]]) = {
   def f(lists: List[List[T]], items: List[T]): List[List[T]] = lists match {
     case list :: tail => list flatMap (i => f(tail, i :: items))
     case _ => List(items reverse)
   }
   f(lists, Nil)
 }
Of course, translating the Haskell version I get:
 def cartesian[T](lists: List[List[T]]) =
   (lists :\ List(List[T]())) ((xs, yss) => for (x <- xs; ys <- yss) yield x :: ys)
which is much simpler but I never would have come up with that on my own.

After a rare good night's sleep I realized a simpler recursive solution:
 def combinations[T](lists: List[List[T]]): List[List[T]] = lists match {
   case list :: tail => list flatMap (x => combinations(tail) map (ys => x :: ys))
   case _ => List(List[T]())
 }
Or expressed with a comprehension:
 def combinations[T](lists: List[List[T]]): List[List[T]] = lists match {
   case list :: tail => for (x <- list; ys <- combinations(tail)) yield x :: ys
   case _ => List(List[T]())
 }
Which I realized is equivalent to the right-folding solution, so maybe I could have arrived at it eventually.

There is also an iterative solution in case you have a really big list and a really small call stack:
 def cartesian[T](lists: List[List[T]]) =
   (List(List[T]()) /: lists.reverse) ((yss, xs) => for (x <- xs; ys <- yss) yield x :: ys)

-- JasonArhart

----
See also: CartesianJoin
-----
AprilZeroSeven

CategoryInManyProgrammingLanguages, CategoryExample