CODEWITHSUNDEEP
algorithmlanguage-agnostic
Deyan Georgiev
Deyan Georgiev

Reputation: 339

Implementing cartesian product, such that it can skip iterations

I want to implement a function which will return cartesian product of set, repeated given number. For example

input: {a, b}, 2
output:
aa
ab
bb
ba

input: {a, b}, 3
aaa
aab
aba
baa
bab
bba
bbb

However the only way I can implement it is firstly doing cartesion product for 2 sets("ab", "ab), then from the output of the set, add the same set. Here is pseudo-code:

function product(A, B):
    result = []
    for i in A:
        for j in B:
            result.append([i,j])
    return result
function product1(chars, count):
    result = product(chars, chars)
    for i in range(2, count):
        result = product(result, chars)
    return result

What I want is to start computing directly the last set, without computing all of the sets before it. Is this possible, also a solution which will give me similar result, but it isn't cartesian product is acceptable. I don't have problem reading most of the general purpose programming languages, so if you need to post code you can do it in any language you fell comfortable with.

Upvotes: 1

Views: 415

Answers (1)

Patrick87
Patrick87

Reputation: 28302

Here's a recursive algorithm that builds S^n without building S^(n-1) "first". Imagine an infinite k-ary tree where |S| = k. Label with the elements of S each of the edges connecting any parent to its k children. An element of S^m can be thought of as any path of length m from the root. The set S^m, in that way of thinking, is the set of all such paths. Now the problem of finding S^n is a problem of enumerating all paths of length n - and we can name a path by considering the sequence of edge labels from beginning to end. We want to directly generate S^n without first enumerating all of S^(n-1), so a depth-first search modified to find all nodes at depth n seems appropriate. This is essentially how the below algorithm works:

// collection to hold generated output
members = []

// recursive function to explore product space
Products(set[1...n], length, current[1...m])

    // if the product we're working on is of the
    // desired length then record it and return
    if m = length then
        members.append(current)
        return

    // otherwise we add each possible value to the end
    // and generate all products of the desired length
    // with the new vector as a prefix
    for i = 1 to n do
        current.addLast(set[i])
        Products(set, length, current)
        currents.removeLast()

// reset the result collection and request the set be generated
members = []
Products([a, b], 3, [])

Now, a breadth-first approach is no less efficient than a depth-first one, and if you think about it would be no different from exactly what you're already doing. Indeed, and approach that generates S^n must necessarily generate S^(n-1) at least once, since that can be found in a solution to S^n.

Upvotes: 2

Related Questions