python - 执行最佳循环排序知道最后的顺序

Question

我们有列表 A，排序后需要看起来像列表 B，并且我们有每个数字的努力或“权重”，所以当我们交换顺序时，努力也会交换，它们是连接的。
知道列表最后应该是什么样子，找出排序列表 A 使其看起来像 lis B 所需的最低努力
我找到了对我的问题的回答，但它在 C++ 代码中位于底部

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

所以当我们搬家的时候
2 和 5 我们取第二个和第五个权重并将它们加在一起 ​​努力是3600 和列表看起来像这样

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

总和努力 = 3600
然后我们移动 3 和 4 这一招的功夫又是3600看起来像这样

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

总和努力 = 7200
然后是 1 和 5 所以 这一招的努力是4000 一个列表看起来像 b 列表
sum_effort 是 11200
我所做的基于 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);
}

我对 python 有点陌生，但如果我不明白这一点，我就不会 sleep

Answer 1

我决定坐下来尝试解决这个问题。如果我理解正确，我们正在对列表执行交换，以便像在目标列表中一样对它们进行排序。
我们可以执行两种类型的操作。将两个号码交换到目的地，也就是交换两个号码，它们都到达它们所属的地方。并将一个号码交换到目的地，这会使其中一个到达它所属的地方，而将另一个放在不正确的位置。
完美交换应该始终优先于一个元素到目的地。在写在纸上之后，我还得出结论，在进行单元素到目标交换时，要最小化总和，移动最小元素的次数越多，总和就越小。
所以，我想出的算法是:在目标中找到最小的权重元素，找到应该在它的位置上的元素，然后切换它们。然后从目标列表和源列表中删除位于正确位置的所有元素(为了找到新的最小权重，如果前一个已经在目标中)，循环直到列表为空。
程序将使用一对一的交换来尽可能长时间地移动最小的权重，并在完成后选择下一个最小的元素。当程序选择这些元素之一作为最小权重时，双向完美交换将自行解决。
我不确定这个算法是否完全正确，尤其是在极端情况下，但这是我能想到的最好的方法，我只有很少的时间。

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_)