Using sort function to sort vector of tuples in a chained manner

Question

So I tried sorting my list of tuples in a manner that next value's first element equals the second element of the present tuple.(first tuple being the one with smallest first element)

(x can be anything)

unsorted

3 5 x

4 6 x

1 3 x

2 4 x

5 2 x

sorted

1 3 x

3 5 x

5 2 x

2 4 x

4 6 x

I used the following function as my third argument in the custom sort function

bool myCompare(tuplea,tupleb){
   if(get<1>(a) == get<2>(b)){
       return true;
   }
   return false;
}

But my output was unchanged. Please help me fix the function or suggest me another way.

A M · Accepted Answer

I am not sure, where the real problem is coming from.

But the background is the Cyclic Permutation Problem.

In your special case you are looking for a k-cycle where k is equal to the count of tuples. I drafted a solution for you that will show all cycles (not only the desired k-cycle).

And I use the notation described int the provided link. The other values of the tuple are irrelevant for the problem.

But how to implement?

The secret is to select the correct container types. I use 2. For a cyle, I use a std::unordered_set. This can contain only unique elements. With that, an infinite cycle will be prevented. For example: 0,1,3,0,1,3,0,1,3 . . . is not possible, because each digit can only be once in the container. That will stop our way through the permutations. As soon as we see a number that is already in a cycle, we stop.

All found cycles will be stored in the second container type: A std::set. The std::set can also contain only unique values and, the values are ordered. Because we store complex data in the std::set, we create a custom comparator for it. We need to take care that the std::set will not contain 2 double entries. And double would be in our case also 0,1,3 and 1,3,0. In our custom comparator, we will first copy the 2 sets into a std::vector and sort the std::vectors. This will make 1,3,0 to 0,1,3. Then we can easily detect doubles.

Please note:

I do always only store a value from the first permutation in the cycle. The 2nd is used as helper, to find the index of the next value to evaluate.

Please see the below code. I will produces 4 non trivial cycles- And one has the number of elements as expected: 1,3,5,2,4.

Porgram output:

Found Cycles:

(1,3,5,2,4)(3,5,2,4)(2,4)(5,2,4)

Please digest.

#include 
#include 
#include 
#include 
#include 
#include 

// Make reading easier and define some alies names
using MyType = int;
using Cycle = std::unordered_set;
using Permutation = std::vector;
using Permutations = std::vector;

// We do not want to have double results. 
// A double cyle is also a Cycle with elements in different order
// So define custom comparator functor for our resulting set
struct Comparator {
    bool operator () (const Cycle& lhs, const Cycle& rhs) const {
        // Convert the unordered_sets to vectors
        std::vector v1(lhs.begin(), lhs.end());
        std::vector v2(rhs.begin(), rhs.end());
        // Sort them 
        std::sort(v1.begin(), v1.end());
        std::sort(v2.begin(), v2.end());
        // Compare them
        return v1 < v2;
    }
};
// Resulting cycles
using Cycles = std::set;

int main() {

    // The source data
    Permutations perms2 = {
        {3,4,1,2,5},
        {5,6,3,4,2} };

    // Lamda to find the index of a given number in the first permutation
    auto findPos = [&perms2](const MyType& m) {return std::distance(perms2[0].begin(), std::find(perms2[0].begin(), perms2[0].end(), m)); };

    // Here we will store our resulting set of cycles
    Cycles resultingCycles{};

    // Go through all single elements of the first permutation
    for (size_t currentColumn = 0U; currentColumn < perms2[0].size(); ++currentColumn) {

        // This is a temporary for a cycle that we found in this loop
        Cycle trialCycle{};

        // First value to start with
        size_t startColumn = currentColumn;

        // Follow the complete path through the 2 permutations
        for (bool insertResult{ true }; insertResult; ) {

            // Insert found element from the first permutation in the current cycle
            const auto& [newElement, insertOk] = trialCycle.insert(perms2[0][startColumn]);
            // Find the index of the element under the first value (from the 2nd permutation)
            startColumn = findPos(perms2[1][startColumn]);
            // Check if we should continue (Could we inster a further element in our current cycle)
            insertResult = insertOk && startColumn < perms2[0].size();
        }

        // We will only consider cycles with a length > 1
        if (trialCycle.size() > 1) {
            // Store the current temporary cycle as an additional result.
            resultingCycles.insert(trialCycle);
        }
    }


    // Simple output
    std::cout << "

Found Cycles:

";
    // Go through all found cycles
    for (const Cycle& c : resultingCycles) {
        // Print an opening brace
        std::cout << "(";
        // Handle the comma delimiter
        std::string delimiter{};

        // Print all integer values of the cycle
        for (const MyType& m : c) {
            std::cout << delimiter << m;
            delimiter = ",";
        }
        std::cout << ")";
    }
    std::cout << "

";

    return 0;
}

Using sort function to sort vector of tuples in a chained manner

Answers (2)

Related Questions