ansaurus

Question

How can I combine pairs of elements from a std::set?

Answer 1

+4 A:

Use a two-level loop:

// Loop over all members.
for (set<string>::iterator j = s.begin(); j != s.end(); ++j)
{
    // Loop over all members up to, but excluding, the current outer-loop member.
    for (set<string>::iterator i = s.begin(); i != j; ++i)
    {
        do_something_with(*i, *j);
    }
}

Marcelo Cantos 2010-05-28 11:24:56

thanks but it is not optimal solution (

vinnitu 2010-05-28 11:52:38

Yes it is. You have to enumerate O(N^2) pairs, which inevitably requires O(N^2) iterations.

Marcelo Cantos 2010-05-28 12:05:08

In my project I make helper vector from set and work with it.But maybe exists better solution?

vinnitu 2010-05-28 12:23:15

If you have 100 elements in your set, you have to generate 9900 pairs, and the above loop will iterate 9900 times. How do you expect to do better than that? If you want to populate a vector efficiently, simply call `v.reserve(s.size() * (s.size() - 1))` before entering the loops, which call `v.push_back(make_pair(*i, *j))`.

Marcelo Cantos 2010-05-28 12:34:34

Assuming the ++i operation on a set iterator takes O(log n) time, then these two loops are O(n^2 * log^2 n), whereas copying the set to a vector first (O(n log n)) and then looping would give O(n^2 + n log n). I think vinnitu does the right thing.

Michał Trybus 2010-05-28 13:00:48

Why not just start i at j+1? Then there isn't any need for i != j and you won't be iterating over each pair twice since the OP appeared to be asking for all combinations, not permutations.

Justin Peel 2010-05-28 13:04:30

@Justin, that wouldn't change anything. On the first iteration of Marcelo's `j` loop, the `i` loop generates zero pairs. On the second iteration, it generates one pair. If the inner loop started with `i = j + 1`, then the termination condition would be `i != s.end()`. The first iteration of the `j` loop would generate `s.size() - 1` pairs, the penultimate iteration would generate one pair, and the final iteration would generate zero pairs. Your suggestion just turns the result upside-down, but doesn't change the number of results or the amount of wasted effort.

Rob Kennedy 2010-05-28 13:35:56

@Marcelo, if there are 100 elements in the set, we want C(100, 2) = 4950 pairs, not 9900. But that's also how many times you loop will run.

Rob Kennedy 2010-05-28 13:38:10

@Rob, yes, you're right. I wasn't paying attention to the ending condition. I agree with you that there are 4950 combinations though.

Justin Peel 2010-05-28 14:03:02

@Michał: I wouldn't assume that `++i` takes O(log N) time; the standard requires that it takes amortised constant time.

Mike Seymour 2010-05-28 14:23:22

I didn't know that, if it does, there's not much to optimize here;)

Michał Trybus 2010-05-28 15:12:16

@Rob, thank you for the correction. I forgot to divide by two.

Marcelo Cantos 2010-05-28 21:23:06

ansaurus

tags:

views:

answers:

How can I combine pairs of elements from a std::set?

related questions