Writing this loop in Mathematica

Question

OK, so I've never had to write a line of Mathematica code (except for using it interactively as a calculator), but for this it looks like I have to. If someone could provide me with the code for the following, then I can edit it to do what I'm actually trying to accomplish. I need to do the following:

1. Input is a set $S$ of integers and some positive integers $n,m$

2. I want to generate all the possible vectors $X$ and $Y$, where $X$ has length $n$ and $Y$ has length $m$ and the elements of each vector belong to the set $S$.

3. I need to loop over all the possible values of $X$ and $Y$.

Something like this would be trivial to write down in, say, Haskell using list comprehensions, but having flipped through the Mathematica language reference for an hour, I couldn't figure out an easy way to do this.

The values of $n$ and $m$ are such that there are about 300 million possible combinations. Therefore, it's not possible to just take Cartesian products of $S$ and then iterate over the set, unless there's a way of generating the elements in a lazy way. Otherwise the machine would run out of memory.

Answer 1

Mathematica has no built-in notion of Haskell-like lazy computation. Although there have been attempts to simulate it, I would probably tackle this problem with a simple imperative loop.

Let's start with an example generator set, which we will call $s:

$s = Array[Prime, 20]
(* {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71} *)

We will now define a helper function s that can return a vector of any rank using elements from that set:

s[i__] := $s[[{i}]]

So now:

s[3, 7]
(* {5, 17} *)

s[12, 9, 15]
(* {37, 23, 47} *)

This enables us to write a simple Do loop to scan over pairs of vectors of any size. Here is an example that scans pairs of 2-vectors and 3-vectors to find the first such pair with a nonsense property:

Module[{c = Length @ $s, x, y}
, Do[
    x = s[x0, x1]
  ; y = s[y0, y1, y2]
  ; If[Total[x] - Total[y] == 39, Return[{x, y}]]
  , {x0, c}, {x1, c}
  , {y0, c}, {y1, c}, {y2, c}
  ]
]

(* {{2, 43}, {2, 2, 2}} *)