CODEWITHSUNDEEP
c++combinations
paul23
paul23

Reputation: 9435

How to "iterate" over this set

Hello say I have some data A -> .... (n data points). Now I take from this data a given number of values (m) - and now I wish to iterate over all unique combinations of these values.

An example for 5 values where you take 2 unique: A unique combination would be a something like "a + b" or "a + c" - however "c + d" is the same as "b + c". And "B + E" is the same as "A + D"

A x x x x 
B x       x x
C   x     x 
D     x     x
E       x

Those describe some geometrical "lines", and the whole specimen can be "mirrored" around the middle point. So for an arbitrary number of lines, is there a clever algorithm to iterate over everything considering this "mirror ability"?

And what is a formula to calculate the number of elements given the set size n and the number of items m?

---- an example with "3 out 6":
It also resembles closely the function combine(6,3) - however now I marked the duplicate rows with - instead of x.

                    1 1 1 1 1 1 1 1 1 1 2
  1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0
A x x x x x x x x - -                     A
B x x x x             x x - - - -         B
C x       x x x       x x -       - - -   C
D   x     x     x -   x     - -   - -   - D
E     x     x   x   -   x   -   - -   - - E
F       x     x   - -     -   - - - - - - F

So possible list would be:

ABC, ABD, ABE, ABF, ACD, ACE, ACF, ADE, BCD, BCE

10 out of 20 potential candidates ignoring the symetry.

Upvotes: 2

Views: 113

Answers (2)

Mooing Duck
Mooing Duck

Reputation: 66922

Not easily. In fact it's quite difficult. But here's the rundown:

for_each_unmirrored() 
   mark first element as part of the set.
   mark last element as definitely NOT part of the set.
   //we know no matter whats inside, this isnt't semetrical, so all combinations
   for_each_mirrored() on all elements between these.

   mark first element as part of the set.
   mark last element as part of the set.
   //ends are semetrical, so insides cannot be
   for_each_unmirrored() on all elements between these

   mark first element as definitely not part of the set.
   mark last element as definitely not in the set.
   //ends are semetrical, so insides cannot be
   for_each_unmirrored() on all elements between these

for_each_mirrored() 
    for each element
        mark it as part of the set.
        if more elements are needed
            for_each_mirrored on elements to the right but in range

Yeah, even the abreviated pseudocode is complicated. The real code is here: http://ideone.com/WDEn40 (including showing that it works for 6 elements pick 3). The linked code isn't as simple as it could be, because I optimized it to avoid allocations and minimize function calls. (As a side effect, the for_each_call_helper isn't threadsafe. If this needs to be threadsafe, simply remove the static keyword from the variables in this function.)

Upvotes: 1

Marc Shapiro
Marc Shapiro

Reputation: 571

I confess that I don't fully understand the question either. However, the general way to solve problems like this is to come up with a good notation and a canonical form, and an algorithm to convert something to canonical form. Then you just do the heavy stuff on canonical forms, and don't repeat.

Upvotes: 0

Related Questions