Efficient Cartesian Product algorithm
The complexity of cartesian product is O(n2), there is no shortcut.
In specific cases, the order you iterate your two axis is important. For example, if your code is visiting every slot in an array — or every pixel in an in image — then you should try to visit the slots in natural order. An image is typically laid out in ‘scanlines’, so the pixels on any Y are adjacent. Therefore, you should iterate over the Y on the outer loop and the X on the inner.
Whether you need the cartesian product or wherther is a more efficient algorithm depends on the problem you are solving.
You can't really change the performance of a nested loop without some additional knowledge, but that would be use-specific. If you have got n items in is and m items in js, it is always going to be O(n*m).
You can change the look of it though:
var qry = from i in is
from j in js
select /*something involving i/j */;
This is still O(n*m), but has nominal extra overhead of LINQ (you won't notice it in normal usage, though).
What are you doing in your case? There may be tricks...
One thing to definitely avoid is anything that forces a cross-join to buffer - the foreach approach is fine and doesn't buffer - but if you add each item to a List<>, then beware the memory implications. Ditto OrderBy etc (if used inappropriately).
I can't propose anything better, than O(n^2), because that's the size of the output, and the algorithm hence can't be any faster.
What I can suggest is using another approach to whether you need to compute product. For example, you may not even need the product set P if only you are going to query whether certain elements belong to it. You only need the information about the sets it's composed of.
Indeed (pseudocode)
bool IsInSet(pair (x,y), CartesianProductSet P)
{
return IsInHash(x,P.set[1]) && IsInHash(y,P.set[2])
}
where Cartesian product is calculated like this:
// Cartesian product of A and B is
P.set[1]=A; P.set[2]=B;
If you implement sets as hashes, then lookup in a cartesian product of m sets is just a lookup in m hashes you get for free. Construction of the cartesian product and IsInSet lookup each take O(m) time, where m is a number of sets you multiply, and it's much less than n--size of each set.
Additional information has been added to the question.
The duplicates can be avoided if you record those you've already computed so as to avoid duplicating them again - it's assumed that the cost of such bookkeeping - a hashmap or a simple list - is less than the cost of computing a duplicate.
The C# runtime is really very fast, but for extreme heavy lifting, you might want to drop into native code.
You might also notice the essential parallelness of this problem. If the computation of a product does not impact the computation of any other product, you could straightforwardly use a multiple processor cores for doing the work in parallel. Look at ThreadPool.QueueUserWorkItem.