Every Combination In Many Programming Languages
Every Combination In Many Programming LanguagesThis 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.
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.
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.WriteLine("({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.WriteLine("({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 ResultList = CrossJoinLists(List1, List2, List3) End Sub Function CrossJoinLists(ByVal ParamArray Lists() As List(Of Object)) As List(Of List(Of Object)) Dim ResultList As New List(Of List(Of Object)) Dim ResultListLength = 1 For Each List In Lists ResultListLength *= List.Count Next List 'Initializing the return variable For ResultListCount = 1 To ResultListLength ResultList.Add(New List(Of Object)) Next ResultListCount 'Magic variables suffering from BadVariableNames, wouldn't mind finding better names for them Dim DwindlingDivisor = ResultListLength Dim SlowerDwindlingDivisor = ResultListLength 'Using magic variables to calculate the correct index of the item For ListsCount = 0 To Lists.Count - 1 DwindlingDivisor \= Lists(ListsCount).Count For ResultListCount = 0 To ResultListLength - 1 ResultList(ResultListCount).Add(Lists(ListsCount)((ResultListCount Mod SlowerDwindlingDivisor) \ DwindlingDivisor)) 'Basically, the index wraps around quicker and quicker with every next list Next ResultListCount SlowerDwindlingDivisor \= Lists(ListsCount).Count Next ListsCount Return ResultList End Function-- Alexei Marine
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.WriteLine("({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.WriteLine("({0} {1} {2})", item[0], item[1], item[2]);
-- DonBox
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 printlnOr you could do an almost word-for-word translation of the recursive RubyLanguage solution given below.
1.5
new ProductList( new Set( "foo", "bar"), new Set( "a", "b", "c" ), new Set( 1, 2 ) ).forEach(new Print());1.2< 1.x <1.5
new ProductList(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.
"ProductList" 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 "PrintList" which shows a count beside each individual output.
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.
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.
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
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
(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.
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')
[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 $_"
}
(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)))
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, ListComprehensions:
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)
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]] ?
// using the allTuples built-in function [[\foo, \bar],[\a, \b, \c], [1, 2]].allTuples; // using ListComprehensions 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 NumberList AS TABLE OF NUMBER;
/
CREATE OR REPLACE TYPE StringList AS TABLE OF VARCHAR2(3); -- pick your length; 3 is enough in this case
/
SELECT
*
FROM
table(NumberList(1, 2)),
table(StringList('a', 'b', 'c')),
table(StringList('foo', 'bar'))
/
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 SubsetIndex := 1 to n
for Subset[ SubsetIndex ] := 1 to n do
if OkSoFar(SubsetIndex) 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
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
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:
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,2Not (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 ComboType, typename T>
typename sp_type_build<ComboType,T>::return_type //--> warning! To STORE this result anywhere, the programmer must hand-write ComboType?.
some_procedure(const ComboType& 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.
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.
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.
fun cartesian list = foldr (ListXProd.mapX op::) [[]] list
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"]
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
EditText of this page
(last edited September 16, 2013)
or FindPage with title or text search