5

I want to create a program to generate the steps of swapping elements during changing an array to another array,(eg:from {0,1,2} to {0,2,1}, the step is 1<->2, which means swap the position of element 1 and element 2),taking A={0,1,3,2} and B={2,0,3,1} as example, my original concept is as following:

  1. get the steps of swapping elements during sorting A in asending order
  2. get the steps of swapping elements during sorting B in asending order
  3. swap the elements in A, starting from following the steps to sort A, then follow the steps to sort B but in reverse order

it is the code I tried:

#include <stdlib.h>
#include <functional>
#include <vector>
int main(){
    std::function<bool(int,int)> f=[](int a,int b){
        if(a>=b)
            printf("%d<->%d\n",a,b);
        return a<b;
    };
    std::vector<int> a={0,1,3,2};
    std::sort(a.begin(),a.end(),f);
    printf("---\n");
    std::vector<int> b={2,0,3,1};
    std::sort(b.begin(),b.end(),f);
    return 0;
}

output:

1<->0 //step to sort A
3<->1
2<->1
---
3<->0 //step to sort B
3<->2
1<->0

so the step to change from 0,1,3,2 to 2,0,3,1 should be:

1<->0
3<->1
2<->1
1<->0
3<->2
3<->0

but when I follow the step:

0,1,3,2
1,0,3,2
3,0,1,2
3,0,2,1
3,1,2,0
2,1,3,0
2,1,0,3

the result is 2,1,0,3 instead of 2,0,3,1, why? Is my concept to generate the step wrong? if so, is there other way to generate the step to change an array to another array by swapping position?

Improve this question
1
  • Are the values in the array(s) guaranteed to be unique? Commented Oct 12, 2016 at 9:36

2 Answers 2

Reset to default
1

The problem is that you are printing a "swap" each time there is a comparison and the two values are not in the right order, this is probably not correct, the std::sort algorithm may do check without swapping. You can use a custom Int structure to test:

struct Int {
    Int(int v) : v_(v) { }
    Int(const Int&) = default;
    Int& operator=(const Int& o) {
        std::cout << v_ << " <- " << o.v_ << '\n'; 
        v_ = o.v_;
        return *this;
    }
    int v_;
};

bool operator<(const Int& lhs, const Int& rhs) {
    return lhs.v_ < rhs.v_; 
}

Then:

int main(){
    std::vector<Int> a{0,1,3,2};
    std::cout << "Sorting A:\n";
    std::sort(a.begin(),a.end());
    std::cout << '\n';
    std::vector<Int> b={2,0,3,1};
    std::cout << "Sorting B:\n";
    std::sort(b.begin(),b.end());
    return 0;
}

Output is:

Sorting A:    Sorting B:
1 <- 1        0 <- 2
3 <- 3        2 <- 0
2 <- 3        3 <- 3
3 <- 2        1 <- 3
              3 <- 2
              2 <- 1

Which gives you the various assignment - Note that std::sort implementation may be optimized for such small ranges, meaning that you do not have only swap (e.g. in the above, for B, you get 1, 2 and 3 swapped "together").

So what you would need to do would be (without the useless a <- a):

2 <-> 3
2 -> 1
3 -> 2
1 -> 3
0 <-> 2

And then you need to transform this in only binary swap:

2 <-> 3
2 <-> 1
1 <-> 3
0 <-> 2

If you want to get the binary swap directly, you can get a bit more ugly (hoping your computer is gentle with this UB) and:

struct Int {
    Int(int v) : v_(v) { }
    Int(const Int&) = default;
    Int& operator=(const Int& o) {
        if (v_ != o.v_) 
            std::cout << v_ << " <-> " << o.v_ << '\n'; 
        std::swap(v_, o.v_);
        return *this;
    }
    mutable int v_;
};

Output:

Sorting A:    Sorting B:
2 <-> 3       0 <-> 2
              1 <-> 3
              1 <-> 2

Combined:

2 <-> 3
1 <-> 2
1 <-> 3
0 <-> 2
Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

Hmm, wouldn’t it be more straightforward to overload swap for your type and output those, rather than outputting assignments?
@KonradRudolph I tried, but unfortunately, std::sort does not always call std::swap (from your own answer ;)). But if you know a way of "forcing" std::sort to use swap, I'll be happy to here it!
Ha, how could I forget that? :-p
0

If the values in the array(s) are guaranteed to be unique, then a better approach is the following:

  1. Detect the final position of each element by looking at the target array and store that information in a map M (not necessarily a std::map, it can also be an std::unordered_map, or a sorted std::vector of (value, target-index) pairs).

  2. For each position in the source array keep swapping the element at the current position into its target position (obtained from M) until the element that appears in the current position corresponds to its target position.

This approach minimizes the count of required swaps. For example, the array {0, 4, 3, 2, 1, 5} can be turned into {5, 4, 3, 2, 1, 0} with a single swap of the first and last elements, whereas your approach would generated a long sequence of swaps taking the source array to the destination array through an intermediate ascendingly sorted state {0, 1, 2, 3, 4, 5}.

In particular, in your example the desired permutation can be achieved with just two swaps:

       # 0,1,3,2
0<->1  # 1,0,3,2
0<->3  # 2,0,3,1

C++ implementation:

#include <stdlib.h>
#include <vector>
#include <map>

int main(){
    std::vector<int> a={0,1,3,2};
    std::vector<int> b={2,0,3,1};
    std::map<int, int> m;

    for ( int i = 0; i < b.size(); ++i )
        m[b[i]] = i;

    for ( int i = 0; i < a.size(); ++i )
    {
        for ( ; ; )
        {
            const int t = m[a[i]];
            if ( i == t )
                break;

            printf("%d<->%d\n", i, t);
            std::swap(a[i], a[t]);
        }
    }
    return 0;
}
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.