1443

34
+15  Q:

## Nested for loops in different languages

Here is a fairly common problem. We have an array of arrays. We'd like to call some function for every combination of elements from the different arrays. Conceptually we'd like to do something like this:

``````for my \$x (1, 2) {
for my \$y ('a', 'b') {
for my \$z ('A', 'B') {
print "\$x \$y \$z\n";
}
}
}
``````

except that we don't want to have to write out a different number of loops if we have a different number of elements. In other words we want to be able to implement the above as something like:

``````nested_for(
sub {print "@_\n"},
[1, 2], ['a', 'b'], ['A', 'B']
);
``````

and get the same result. (Exact syntax may vary by language.)

## Index of Solutions

(with at least +1 vote)

+5  A:

To get things going, here is a Perl solution:

``````nested_for(
sub {print "@_\n";},
[1, 2], ['a', 'b'], ['A', 'B']
);

sub nested_for {
ret_iter(@_)->();
}

sub ret_iter {
my \$fn = shift;
my \$range = pop;
my \$sub = sub {\$fn->(@_, \$_) for @\$range};
return @_ ? ret_iter(\$sub, @_) : \$sub;
}
``````
I almost forgot how ugly Perl is :)
Ugly? Have you seen the Lisp version?
+2  A:

It's not just 'conceptually' that you'd want to do that: it's what you would end up doing in any imperative language. In Python, you could use a generator function and a function to generate all combinations that together would pretty neatly express what you are doing, but in truth, it's still a for .. for .. for ..

Unless you think recursive answers, such as I see appearing now, are more intuitive and expressive, but I sure as hell do not agree with that. :)

It is not a matter of taste that sometimes you don't want to have to rewrite your code if you have more levels of nesting. Recursion is merely one possible technique to accomplish that.
+3  A:

In Nemerle using a macro:

``````macro nested_for(lists, block)
syntax("nested_for", lists, block) {
def build(lists) {
| [] => block
| <[ \$name in \$sub ]> :: tail =>
<[
foreach(\$(name.ToString() : dyn) in \$sub)
\${ build(tail) }
]>
}

build(lists)
}
``````

To use (note: the print and <- string formatting macros are from the Nextem library):

``````nested_for(x in [1, 2], y in ['a', 'b'], z in ['A', 'B'])
print "{0} {1} {2}" <- (x, y, z)
``````
+2  A:

Here is a Ruby answer due to Christoph Rippel

``````def each (arg,*more_args)
( [] != more_args ) ?
arg.each {|l| each(*more_args) {|r| yield [l]+ r }} :
arg.each { |r| yield [r] }
end

each( 1..2, 'a'..'b', 'A'..'B') { |args|   puts args.join(" ") }
``````
+1  A:

tested D

``````template T(t...)
{
alias t T;
}

template Tof(uint i, Ty)
{
static if(i >0) alias T!(Ty, Tof!(i-1,Ty)) Tof;
else            alias T!() Tof;
}

void Loop(T, int i)(T[][i] arr, void delegate(Tof!(i, T)) dg)
{
Inner!(T,i,i)(arr, dg);
}

void Inner(T, int i, int j)(T[][i] arr, void delegate(Tof!(i, T)) dg, Tof!(i-j, T) val)
{
static if(j > 0)
foreach(v;arr[j-1])
Inner!(T,i,j-1)(arr,dg,v,val);
else
dg(val);
}

void main()
{
Loop!(int,4)([[1,2][], [1], [1,2,3],[1,2,3,4,5,6,7,8]],
(int i, int j, int k, int m)
{
writef("%s,%s,%s,%s\n",i,j,k,m);
});
}
``````
+1  A:

In Python:

``````def loop(action, values, *args):
if values is None:
values = []
if args:
for value in args[0]:
loop(action, values + [value], *args[1:])
else:
action(*values)

def action(a, b, c):
print a, b, c

loop(action, None, [1, 2], ['a', 'b'], ['A', 'B'])
``````
+2  A:

Ruby:

``````def loopme( list, reg = [], &block )
if( list.length > 0 )
list[0].each{ |x|
m = list.clone;
m.shift;
loopme( m, reg +[x] , &block );
}
else
block.call( reg )
end
end
loopme( [[1,2],[3,4],[5,6]] ) {  |x|  p x }
``````

( Note, the double bracketing is needed to pass all the positional registers down the stack )

Output:

```[1, 3, 5]
[1, 3, 6]
[1, 4, 5]
[1, 4, 6]
[2, 3, 5]
[2, 3, 6]
[2, 4, 5]
[2, 4, 6]
```

And heres a variant with mapping instead.

``````def loopme( list, reg = [], &block )
if( list.length > 1 )
out = [];
list[0].each{ |x|
m = list.clone;
m.shift;
out = out + loopme( m,  reg + [x] , &block )
}
return out
else
return list[0].map{ |x|
block.call( reg + [x] )
}
end
end

require "pp";

pp loopme( [[1,2],[3,4],[5,6]] ) {  |x|  ['hello',x,'world'] }
``````
```[["hello", [1, 3, 5], "world"],
["hello", [1, 3, 6], "world"],
["hello", [1, 4, 5], "world"],
["hello", [1, 4, 6], "world"],
["hello", [2, 3, 5], "world"],
["hello", [2, 3, 6], "world"],
["hello", [2, 4, 5], "world"],
["hello", [2, 4, 6], "world"]]
```

( Note: Using tree flattening for ease of use.

+1  A:

D, no (extra) template stuff, no recursion, no "nested for loops"

``````void Loop(T)(T[][] arr, void delegate(T[]) dg)
{
int[] index = new int[arr.length];  // set of indexes
foreach(ref i;index)i=0;

T[] val = new T[arr.length]; // set of values

// main loop
outer: while(true)
{
// select values
foreach(int i, a;arr) val[i] = a[index[i]];

dg(val); // call function

for(int i=0; i < arr.length; i++) // inc, roll & continue on overflow
{
index[i]++;
if(index[i] < arr[i].length) continue outer;
index[i]=0;
}

return; // for loop continues outer on non-terminating case
}
}

void main()
{
Loop!(int)([[1,2][], [1], [1,2,3],[1,2,3,4,5,6,7,8]],
(int[] i){   writef("%s\n",i);   });
}
``````
For those of us who don't want to dig up a D compiler, would you mind testing it? Thanks.
tested it. OK? <G>
+1  A:

Ruby:

``````def nested_for(axes, args = [], &block)
if axes.empty?
yield args
else
axes[0].each do |value|
nested_for(axes[1,axes.length], args + [value], &block)
end
end
end

nested_for([[1, 2], [3, 4], [5, 6]]) do |args|
puts args.join(" ")
end
``````
+1  A:

# Permutative/Generative version:

( Nonrecursive / Ruby )

``````def loopme( list, &block )
perms = [];
list[0].each{ |set|
perms.push([set])
}
list[1..-1].each{ |set|
newperms = [];
perms.each{ |oldperms|
set.each{ |item|
newperms.push( oldperms + [item] )
}
}
perms = newperms
}
return perms.each{ |x| block.call(x) }
end
``````

To make into a map equivalent, change the last line.

+1  A:

Javascript:

``````function nested_for(axes, args, delegate) {
if (axes.length == 0) {
delegate(args);
}
else {
var axis = axes[0];
for (var i = 0; i < axis.length; i++) {
nested_for(axes.slice(1), args.concat([axis[i]]), delegate);
}
}
}

nested_for([[1, 2], [3, 4], [5, 6]], [], function(args) {
});
``````
+2  A:

Cheating Perl version. (Sometimes useful in golf.)

``````print "\$_\n" for glob "{1,2}\\ {a,b}\\ {A,B}"
``````
+4  A:

Java w/ Decorators. Iterates over last list first, first list last (easily reversed, of course).

``````public final class Loop {

public static void nestedFor(final Method sub, final List... lists) {
Method m = sub;
for (final List list : lists) {
m = new Iterator(list, m);
}
m.execute(new ArrayList());
}

interface Method {
void execute(List objs);
}

private static class Iterator implements Method {

private final List list;
private final Method method;

public Iterator(final List list, final Method method) {
this.list = list;
this.method = method;
}

@Override
public void execute(final List objs) {
for (final Object o : list) {
method.execute(objs);
objs.remove(o);
}
}
}

private static class Printer implements Method {

@Override
public void execute(final List objs) {
for (final Object o : objs) {
System.out.print(o + " ");
}
System.out.println();
}

}

}
``````
+5  A:

In Common Lisp see the Alexandria package and search for `map-product`:

``````(defun map-product (function list &rest more-lists) ...)
``````

Returns a list containing the results of calling `FUNCTION` with one argument from `LIST`, and one from each of `MORE-LISTS` for each combination of arguments. In other words, returns the product of `LIST` and `MORE-LISTS` using `FUNCTION`.

Example:

``````(map-product 'list '(1 2) '(3 4) '(5 6)) => ((1 3 5) (1 3 6) (1 4 5) (1 4 6)
(2 3 5) (2 3 6) (2 4 5) (2 4 6))
``````

In case you are interested in the details it is implemented as:

``````(defun map-product (function list &rest more-lists)
(labels ((%map-product (f lists)
(let ((more (cdr lists))
(one (car lists)))
(if (not more)
(mapcar f one)
(mappend (lambda (x)
(%map-product (curry f x) more))
one)))))
(%map-product (if (functionp function)
function
(fdefinition function))
(cons list more-lists))))
``````
Currying! That's a nice way to implement it. :-)
+1  A:

Apart from levy's answer, I decided to try writing a Common Lisp version too. I don't like my version very much, because of the need to modify the expansion "after the fact"; I'm a newbie, and could do with some tips on how to make it better. :-)

``````(defmacro nested-for (func &rest sets)
(let* ((holder `(funcall ,func))
syms
(result holder))
(dolist (set (nreverse sets))
(let ((sym (gensym)))
(push sym syms)
(setq result `(dolist (,sym ,set) ,result))))
(setf (cddr holder) syms)
result))
``````
+3  A:

``````cartesianProduct [] = [[]]
where subProduct = cartesianProduct rest
``````
+7  A:

## APL (one-liner):

(Unicode characters in code snippet may not show in some browsers.)

``````x←'1' '2'
y←'a' 'b'
z←'A' 'B'
⎕←,x∘.,y∘.,z
``````

Outputs:

`````` 1aA  1aB  1bA  1bB  2aA  2aB  2bA  2bB
``````

I'm using the outer product (`∘.,`) to combine three vectors to a matrix, then flatten the matrix (`,`) back to a vector. Finally, `⎕←` shows the result.

As noted in my own example below, what happens if the arrays have different numbers of elements? I know that was not specified as a parameter to the problem, but in real life you may well have different length arrays to combine elements from...
No problem, it works just as well.
+3  A:

In Python, with generators & recursion:

``````def nested_for(items):
def _outer_product(depth, current):
if depth == 1:
return (current + [elem] for elem in items[-depth])
else:
return (res
for elem in items[-depth]
for res in _outer_product(depth - 1, current + [elem]))
if items:
return _outer_product(len(items), [])
else:
return []

def apply_all(action, iterable):
for elem in iterable:
action(elem)

def action(elem):
print elem

apply_all(action, nested_for([[1, 2], ['a', 'b'], ['A', 'B']]))
``````
+3  A:

Haskell, for lists of different types:

``````[printf "%d %s %s\n" x y z | x <- [1, 2], y <- ["ab"], z <- ["AB"]]
``````

For lists of lists:

``````cp []       =  [[]]
cp (xs:xss) =  [y:ys | y <- xs, ys <- cp xss]

printEm xs = mapM (putStrLn . intercalate " " . map show) (cp xs)

main = printEm [[1,2], [3,4], [5,6]]
``````
A:

# Perl6

``````multi sub nested_join( String \$join, String \$join_line, Int :\$index, Array *@data ){
return undef unless @data.length;
return undef unless \$index < @data.length;
\$index //= 0;
my @return;

if( \$index == @data.length -1 ){
return @{@data[\$index]};
}else{
my @lower = nested( \$code, :index(\$index+1), @data );

for @{@data[\$index]} -> (\$left) {
for @lower -> \$right {
push @return, \$left ~ \$join ~ \$right;
}
}
}

if( \$index == 0 ){
return join \$join_line, @return;
} else {
return @return;
}
}

multi sub nested_join( String \$join, String \$join_line, Array *@data ){
nested_join( \$join, \$join_line, 0, @data );
}

print nested_join( ' ', "\n", [1, 2], ['a', 'b'], ['A', 'B'] );
``````
+5  A:
+7  A:

## Perl 6

Built in!

``````my @x = 1..2;
my @y = 'a'..'b';
my @z = 'A'..'B';

for @x X @y X @z -> \$x, \$y, \$z {
say "\$x \$y \$z";
}
``````

If using the cross operator multiple times or more than one loop variable is still cheating, you could get away with the following somewhat less sane solution that uses the reduction operator:

``````for @@( [X] \@x, \@y, \@z ) -> @slice {
say @slice.join(' ');
}
``````

Alternatively, to operate on a list of lists:

``````my @foo = \@x, \@y, \@z;
for @@( [X] @foo ) -> @slice {
say @slice.join(' ');
}
``````
Sorry, the point is to build a function that stays the same if ayou change the number of arrays. Using the cross operator your code for 3 arrays is different from 4 arrays.
How is using the cross operator one more time any different than using one more comma for another sub argument? I guess you could use the reduction operator and write it as [X] @x, @y, @z. (Syntax not guaranteed.) You could also use slice context @@() and get arrays instead of listing variables.
The difference is that the sub arguments could be a data structure that comes from some external source outside of your code entirely.
Okay, so use the second solution and flatten first. @foo = (@x, @y, @z); for @@( [X] |@foo ) -> @slice { ... }
Edited my answer to include a list-of-lists version and a revision after some poring over the p6 spec. You really should make your constraints explicit in the question instead of arbitrarily rejecting answers; all you asked is that nesting more loops not be necessary.
I know he rejected my answer, because I had the gall to say that it generated permutations. Which is what every example on this page does.
+4  A:

Scala:

``````val nums = List(1, 2)
val lows = List('a', 'b')
val highs = List('A', 'B')

for (x <- nums; y <- lows; z <- highs) {
printf("%s %s %s%n", x, y, z)
}
``````

Or if you prefer:

``````for {
x <- nums
y <- lows
z <- highs
} printf("%s %s %s%n", x, y, z)
``````

The neat thing about this construct is not defined by Scala specifically for `List`, the transformation is more generic than that. In fact, it's even better than Java's enhanced for-loop, which works on all `Iterable`. Both of the above Scala snippets will be translated into the following higher-order invocations:

``````nums.foreach { x =>
lows.foreach { y =>
highs.foreach { z =>
printf("%s %s %s%n", x, y, z)
}
}
}
``````

This means that any type which declares `foreach` accepting a function of arity-1 as a single parameter can be used with Scala's imperative for-comprehensions as shown. Thus, you can do this for arrays, maps, sets, or even custom types. It's a lot like C#'s LINQ, and reasonably so considering they both have their roots in Haskell's `do`-notation.

Oh, and in case there was any ambiguity, this works for anything that declares `foreach`, thus including all supported collections (heterogeneous and homogeneous alike).

But it doesn't solve the general case for a variable number of lists.
A:

Scheme:

`````` (define-syntax foreach
(lambda (x)
(syntax-case x (=>)
[(_ (v => l) ... e)
(let ((p (map cons #'(v ...) #'(l ...))))
(let f ((p p))
(cond
[(null? p) #'e]
[(null? (cdr p))
#`(map (lambda (#,(caar p)) e)
#,(cdar p))]
[else
#`(apply append
(map
(lambda (#,(caar p))
#,(f (cdr p)))
#,(cdar p)))])))])))

(foreach
[a  => '(1 2 3)]
[b  => '(4 5 6)]
(cons a b))
``````
+1  A:

No LINQ sample, so here is one:

``````var query =
from a in list1
from b in list2
from c in list3
select new { a = a, b = b, c = c };
``````
Downvote? jesus some people suck...
I think it was downvoted because you used nested loops. The question asks for ways to do it without nesting loops.
@Herms: WTF? That is exactly what is asked!
Nope, you are supposed to provide code that works without being changed, for an arbitrary number of arrays (lists).What happens when you come along with a list4 in your example? Code must be edited.
Funny, I dont see a single post where adding more lists does not involve adding/removing code. The code even looks like the OP's sample.
A:

C# using delegates and anonymous methods

``````using System;
using System.Collections.Generic;

class MainClass
{

delegate void Action(List<object> arguments);

static void nestFor(Action action, List<object> arguments, List<List<object>> listOfLists)
{
if (listOfLists.Count == 0)
{
action(arguments);
return;
}
List<object> targets = listOfLists[0];
List<List<object>> newLol = new List<List<object>>(listOfLists);
newLol.RemoveAt(0);
foreach(object o in targets)
{
List<object> newArgs = new List<object>(arguments);
nestFor(action, newArgs, newLol);
}
}

public static void Main(string[] args)
{
List<List<object>> lol = new List<List<object>>();
List<object> a = new List<object>(new object[]{0,1,2,3});
List<object> b = new List<object>(new object[]{"a", "b", "c"});
List<object> c = new List<object>(new object[]{"A", "B"});

nestFor(delegate(List<object> arguments) {
arguments.ForEach( delegate(object o) {
Console.Write(o.ToString() + " ");
});
Console.WriteLine();
}, new List<object>(), lol);
}
}
``````
A:
+1  A:

# Python 2.6

``````import itertools

def nested_for(func, *iterables):
for item in itertools.product(*iterables):
func(*item)

def print_em(*args):
print " ".join("%s" % arg for arg in args)

nested_for(print_em, [1, 2], ['a', 'b'], ['A', 'B'])
``````
A:

Objective C:

First, the final output: 1 a A, 1 a B, 1 b A, 1 b B, 1 c A, 1 c B, 2 a A, 2 a B, 2 b A, 2 b B, 2 c A, 2 c B

Some of the matrix based approaches are interesting, but what happens when arrays have different numbers of elements?

Here's the code, recursive in nature (this first bit here I just included to show the data I initialized the array with):

``````NSMutableArray *allArrays = [NSMutableArray array];
[allArrays addObject:[NSArray arrayWithObjects:@"a", @"b", @"c", nil]];
[self doGatherResultsFromArray:allArrays
baseString:@""
performSelector:@selector(doPrintResult:)];
``````

.....

``````  // Here's the method called when all the elements are together
- (void) doPrintResult:(NSString *)result  { NSLog(@"%@", result); }

-(void) doGatherResultsFromArray:(NSArray *)currentArray baseString:(NSString *)baseString performSelector:(SEL)selector
{
if ( [currentArray count] == 0 )
[self performSelector:selector withObject:baseString];
else
for ( NSObject *currentObject in [currentArray objectAtIndex:0] )
{
[self doGatherResultsFromArray:[currentArray subarrayWithRange:NSMakeRange(1, [currentArray count]-1 )]
baseString:[NSString stringWithFormat:@"%@ %@", baseString, currentObject]
performSelector:selector];
}
}
``````
A:

## Simple Java solution

``````public static void main(String[] args) {
Object[][] arrayOfArrays = new Object[][] { { 1, 2 }, { "a", "b" }, { "A", "B" } };
print(arrayOfArrays);

}

private static void print(Object[][] arrayOfArrays) {
print("", arrayOfArrays, 0);

}

private static void print(String prefix, Object[][] arrayOfArrays, int start) {
if (arrayOfArrays.length == start + 1) {
for (Object o : arrayOfArrays[start]) {
System.out.println(prefix + o);
}
} else {
for (Object o : arrayOfArrays[start]) {
print(prefix + o + " ", arrayOfArrays, start + 1);
}
}
}
``````
A:

Here's an Erlang version

``````nested(Fun, ListOfLists) ->
nested(Fun, ListOfLists, {}).

nested(Fun, [], Current) ->
Fun(Current);
nested(Fun, ListOfLists, Current) ->
[List|T] = ListOfLists,
lists:foreach(fun(Item) -> nested(Fun, T, erlang:append_element(Current, Item)) end, List).
``````

And it would be called like:

``````nested(fun(Item) -> io:format("~w~n", [Item]) end, [ [1,2], ['a','b'], ['A', 'B']]).
``````

Although to be honest, I would normally just use a list comprehension as follows:

``````lists:foreach(fun(Item) -> io:format("~w~n", [Item]) end, [{X,Y,Z} || X <- [1,2], Y <- ['a','b'], Z <- ['A', 'B'] ]).
``````
A:

using Linq's aggregate and select many

``````var a = new string[] { "1", "2" };
var b = new string[] { "a", "b" };
var c = new string[] { "A", "B" };

var result = new[] { a, b, c }.Aggregate<IEnumerable<String>>((l1, l2) => l1.SelectMany(s => l2, (s1, s2) => s1.ToString() + s2.ToString()));

foreach (var val in result)
Console.WriteLine(val);
``````

Anders should get a Nobel prize for the Linq thing!

A:

Python, list comprehensions (useful for problems that can be translated to the map-reduce paradigm):

``````#totally random example made generic
#average length of words starting with 'a' in US and UK english
files = ['en_uk.dic', 'en_us.dic']
avg = lambda nums: sum(nums)/len(nums)
result = avg([len(word) for dictfile in files
The ability to nest `if` statements as well makes this construct very powerful.