CODEWITHSUNDEEP
c++algorithmtreemultiset
Othman Benchekroun
Othman Benchekroun

Reputation: 2018

Loop through all combinations of a multiset elements

I need to find the best path in a tree, the tree is all possible combinations of elements of a multiset. For example for this multiset : A - B - C, the tree would be composed of all the 6 possible combinations : A - B - C | A - C - B | B - A - C | B - C - A | C - A - B | C - B - A

enter image description here

I want to loop trough this tree using the multiset only,

Something like this :

// I think this must be initialized, but that is not a problem
Path bestPath;

for (mySet::iterator i(aSet.begin()), e(
                    aSet.end()); i != e; ++i) {  
         Path path = someRecursiveFunction(*i);
         if(criteria(bestPath,path))
              bestPath = path;
         return bestPath;
}

and someRecursiveFunction must probably be the same, but looping on the rest of the values, I dont want to create a multiset in each node and put the rest on it, since the number of nodes is factorial the size of the multiset, I can't find a good way to do this ...

Upvotes: 1

Views: 683

Answers (1)

Steephen
Steephen

Reputation: 15824

Create a std::vector as follows std::vector<char> set ={A,B,C} and call std::next_permutation on top of vector to get all permutations 

std::next_permutation( std::begin(set), std::end(set));

do {
    //your code for algorithm
    for( auto & x : set)
      std::cout<<x<<" ";
    std::cout<<"\n";
  } while( std::next_permutation( std::begin(set), std::end(set));

Upvotes: 3

Related Questions