0

I am trying to find the permutation and combination of elements with 2 objects each - nC2 or nP2. I can find the combinations by the below code. Is there any elegant way to rewrite this? Also, is there any way to find permutations? The below is just an example, My datasets consists of close to 2000 elements. So, speed is a factor too.

#include <iostream>
#include <vector>
#include <string>
int main() {

  std::vector<std::string> array = {"a", "b", "c", "d", "e"};
  std::vector<std::string>::iterator it = array.begin();
  for ( ; it < array.end(); it++ ) {
    for (std::vector<std::string>::iterator it_next = it+1 ; it_next < array.end(); it_next++ ) {
        std::cout << *it << *it_next << "\n";
    }
  }
}

Program output -

gcc version 4.6.3

ab ac ad ae bc bd be cd ce de

infoclogged
  • 3,641
  • 5
  • 32
  • 53

2 Answers2

0

Well, if you just want the permutation of all combinations, it is real simple as you only have two items in each combination. So simply reverse the printing - like:

  std::vector<std::string> array = {"a", "b", "c", "d", "e"};
  std::vector<std::string>::iterator it = array.begin();
  for ( ; it < array.end(); it++ ) {
    for (std::vector<std::string>::iterator it_next = it+1 ; it_next < array.end(); it_next++ ) {
        std::cout << *it << *it_next << "\n";

        // Print the permutation - simply swap the order
        std::cout << *it_next << *it << "\n";
    }
  }
}

Old answer where I misunderstood what OP wanted

Also, is there any way to find permutations?

yes, it can be done in several ways but std::next_permutation seems a good fit.

#include <algorithm>
#include <string>
#include <iostream>
#include <vector> 

// Print the vector
void pv(const std::vector<std::string>& v)
{
    for (const auto& s : v)
    {
        std::cout << s << " ";
    }
    std::cout << std::endl;
}

int main()
{
    std::vector<std::string> array = {"a", "b", "c"};
    std::sort(array.begin(), array.end());
    do 
    {
        pv(array);
    } while(std::next_permutation(array.begin(), array.end()));
}

Output:

a b c 
a c b 
b a c 
b c a 
c a b 
c b a
Support Ukraine
  • 42,271
  • 4
  • 38
  • 63
  • thank you.. I will have a look on std::next_permutation. But my question was to find permutation of two of the n elements. In your answer, its all the elements of the array. – infoclogged Feb 04 '18 at 13:36
  • @infoclogged ok, seems I misunderstood your question. So I'm trying to figure out what you want instead. A permutation of `ab` would be `ba` - is that what you are looking for? And done for every combination? – Support Ukraine Feb 04 '18 at 14:04
  • @infoclogged - is the output you want simply: `ab ba ac ca ad da ae ea bc cb bd db be eb cd dc ce ec de ed` ? – Support Ukraine Feb 04 '18 at 14:06
  • sorry, for the late reply. Yes, exactly, thats also the definition of permutation ( the order matters i.e ab is not the same as ba ). So, combination would return 10 sets and permutation would return 20 (5!/3!) – infoclogged Feb 04 '18 at 15:44
0

Relative to your initial code for combinations, you can improve the performance by going through the vector using [], instead of iterators:

#include <iostream>
#include <vector>
#include <string>
#include <chrono>

int main() {

    std::vector<std::string> array = { "a", "b", "c", "d", "e" };

    int current;
    int next;

    for (current = 0; current < array.size(); ++current)
    {
        for (next = current + 1; next < array.size(); ++next)
        {
            std::cout << array[current] << array[next] << "\n";
        }
    }

    return 0;
}
Ashley Prazeres
  • 21
  • 4