Quote:

---

Сложность в том, что {...|...} может быть сколько угодно

---

code:

void GenerateVariants(int depth, List<string> variants, char[] current, List<string> result)
{
  if (depth >= variants.Count) 
  {
      result.Add(new String(current));
  }
  for (int i = 0; i < variants[depth].Length; i++)
  {
     current[depth] = variants[depth][i];
     GenerateVariants(depth+1, variants, current, result);
  }
}

code:

main()
{
  //цикл, пока массивы не совпадут
  while (1)
  {
    PrintSet(CurrentLetters, N);
    int i;
    for (i = 0; i < N; i++)
    {
      if (!IncrementNumber(CurrentLetters + i, Limits + i)) 
         break;
    }
    if (i == N) break;
  }
}
bool IncrementNumber(int* current, int* limit)
{
  (*current)++;
  if (*current > *limit)
  {
     *current = 0;
     return true;
  }
  return false;
}
void PrintSet(int* current, int size)
{
  for(int i=0; i < size; i++)
  {
     std::cout << Data[i][current[i]] << "," 
  }
  std::cout << std::endl;
}

code:
$ cat a.php 
<?php
$x = array(
        array(1, 2, 3),
        array('a', 'b', 'c'),
        array('X', 'Y'),
);

function go($x, $n = 0, $res = array()) {
        if ($n == count($x)) {
                echo implode(',', $res), "\n";
                return;
        }
        foreach ($x[$n] as $v) {
                array_push($res, $v);
                go($x, $n + 1, $res);
                array_pop($res);
        }
}

go($x);
?>
$ php a.php 
1,a,X
1,a,Y
1,b,X
1,b,Y
1,c,X
1,c,Y
2,a,X
2,a,Y
2,b,X
2,b,Y
2,c,X
2,c,Y
3,a,X
3,a,Y
3,b,X
3,b,Y
3,c,X
3,c,Y

code:
mGauss :: [[a]] -> [[a]]
mGauss [] = []
mGauss [x] = [[ksi]|ksi <- x]
mGauss (x:s) = [ksi:y|y <- mGauss s, ksi <- x]

code:

int[] Init(int[] variants)
{
    return new int[variants.Length];
}
//true - есть еще один вариант, false - перебор окончен
bool Next(int[] variant, int[] variants)
{
    for(int i = variant.Length-1; i>=0; --i)
    {
        variant[i]++;
        if (variant[i] < variants[i])
           return true;
       variant[i] = 0;
    }
   return false;
}

В ответ на:

---

Скобочек {} ну штук 10, каждых элементов то же 10 макс, т.е. на скорость алгоритма пофиг.

---

code:
f:: [[a]]->[[a]]
f=foldr (flip $ (flip (>>=)).(flip $ map.(:))) [[]]