Perform best cycle sort knowing order at the end

Question

We have list A that after sorting needs to look like list B and we have effort or "weight" of each number so when we are swapping in order effort will swap also ,they are connected.

Knowing how list should look like at the end find what is the lowest effort needed to sort list A to look like lis B

I've found answear to my question but it's in c++ code is at the bottom

6 <--- how many numbers there is
w = [2400, 2000, 1200, 2400, 1600, 4000] <----- effort 
a = [1, 4, 5, 3, 6, 2] <----- starting list
b = [5, 3, 2, 4, 6, 1] <----- how it should be sorted

so when we are moving

2 and 5 we are taking second and fifth weight and add them together so effort is 3600 and lists looks like this

a = [1, 4, 2, 3, 6, 5]

sum_effort = 3600

then we are moving 3 and 4 effort of this move is again 3600 and a looks like this

a = [1, 3, 2, 4, 6, 5]

sum_effort = 7200

and then 1 with 5 so effort of this move is 4000 and a list looks like b list

sum_effort is 11200

what I did based on c++

weight = [2400, 2000, 1200, 2400, 1600, 4000]
og = [1, 4, 5, 3, 6, 2]
position = [5, 3, 2,4, 6, 1]

result = 0
for x in range(len(og)):
    suma    = 0
    min_cycle = 0
    len_cycle = 0
    current  = x

    while(1):
    
        min_cycle = min(min_cycle, weight[current])
        
        suma = suma + weight[current]
        current = position[current]
            
        len_cycle += 1
        if current == x:
            break
        
    result += min(suma+(len_cycle-2)*min_cycle, suma+min_cycle+(len_cycle+1)*min_weight)
print(result)

#include <cstdio>
#include <algorithm>

#define REP(a,n) for (int a=0; a<(n); ++a)

using namespace std;

#define INF 1000000000

typedef long long LL;

///////////////////////////

#define MAXN 1000000

int wagi[MAXN];
int orig[MAXN]; // orgin
int perm[MAXN]; // end_pos
bool vis[MAXN]; 

int minw = INF; // minimalna waga

int main()
{
    int N;
    scanf("%d", &N);
    REP(a, N)
    {
        scanf("%d", &wagi[a]);
        minw = min(minw, wagi[a]);
    }
    REP(a, N)
    {
        scanf("%d", &orig[a]);
        --orig[a];
    }
    REP(a, N)
    {
        int nr;
        scanf("%d", &nr);
        --nr;
        perm[nr] = orig[a];
    }
    LL wynik = 0;
    REP(pocz, N)
        if (!vis[pocz])
        {
            int minc = INF; 
            LL suma = 0; 
            int cur = pocz;
            int dl = 0; 
            for (;;) 
            {
                minc = min(minc, wagi[cur]);
                suma += wagi[cur];
                cur = perm[cur];
                vis[cur] = true;
                ++dl;
                if (cur==pocz)
                    break;
            }
            wynik += min(suma+(dl-2)*(LL)minc, suma+minc+(dl+1)*(LL)minw);
        }
    printf("%Ld\n", wynik);
}

Im kinda new to python but I won't go to sleep if i don't figure this out

Answer 1

I decided to sit down a bit and try tackling this problem. If I understand correctly, we are performing swaps on list in order to get them sorted like in the destination list.

There are two types of operations we can do. Swapping two numbers to destination, which is swapping two numbers and they both land where they belong. And swapping one number to destination, which makes one of them land where it belongs and puts other in the incorrect location.

Perfect swap should always be prioritized over one-element to destination. After writing it down on paper, I also concluded that to minimize the sum when doing one-element to desination swaps, the more you move the smallest element, the smaller the sum.

So, the algorithm I came up with is: Find smallest weight element in target, find what should be in its place, switch them. Then remove all elements that are on their correct places from both target and origin lists(in order to find new smallest weight if previous one is already in destination), loop until the lists are empty.

Program will use one-to-destination swaps to move the lowest weight as long as it can, and when its done, chooses next smallest element. two-way perfect swaps will solve themselves when program picks one of those elements as the smallest weight.

I am not sure if this algorithm is perfectly correct, especially on the corner cases, but it's the best I could come up with, with the little time I have.

def remove_correct_places(org,trg,orgw):
    indexes_to_delete = []

    for index, tpl in enumerate(zip(org, trg)):
        if tpl[0] == tpl[1]:
            indexes_to_delete.append(index)

    for index in reversed(indexes_to_delete):
        org.pop(index)
        trg.pop(index)
        orgw.pop(index)

weight = [2400, 2000, 1200, 2400, 1600, 4000]
origin = [1, 4, 5, 3, 6, 2]
target = [5, 3, 2, 4, 6, 1]


weights = {nr+1:item for nr, item in enumerate(weight)}
# list of weights in order corresponding to origin
origin_weights= [weights[x] for x in origin]
sum_ = 0

#ignoring elements that are in their places already
remove_correct_places(origin,target,origin_weights)

# as long as origin isn't empty
while origin_weights:
    # find smallest weight
    min_weight = min(origin_weights)
    # find its index
    min_weight_index = origin_weights.index(min_weight)
    # find which element it corresponds to
    min_weight_element = origin[min_weight_index]

    # find what value should be in that index
    other_element = target[min_weight_index]
    # find index of this value in origin
    other_index = origin.index(other_element)
    # find its weight
    other_weight = weights[other_element]

    # swap the two (both on origin_weight and origin lists) and increase the cumulative sum
    origin[min_weight_index] = other_element
    origin_weights[min_weight_index] = other_weight

    origin[other_index] = min_weight_element
    origin_weights[other_index] = min_weight

    sum_ += other_weight + min_weight

    # removing elements that are on the correct place from the list,
    # because we don't need them anymore
    remove_correct_places(origin, target, origin_weights)

print(sum_)