【星火问题2】数列调换元素位置的问题

ggggwhw

给大家出一个简单的问题:
有两个不同的数列brr和crr,均由3000以内的整数随机排列而成,每次调换brr中的两个数字的位置,需要多少次可以将brr掉换成和crr完全相同的数列?
下面的代码用来生成原始数列brr和crr.

1. (*下面代码生成一个三千以内的整数通过随机排列而成的数列brr*)
   
2. zongshu = 3000;
   
3. SeedRandom[1];
   
4. arr = Range[zongshu];
   
5. brr = {};
   
6. For[i = 1, i <= zongshu, i++,
   
7.           n = Random[Integer, Length[arr] - 1] + 1;
   
8.           AppendTo[brr, arr[[n]]];
   
9.           arr = Delete[arr, n];
   
10.   ];
    
11. brr;
    
12. (*下面代码生成一个三千以内的整数通过随机排列而成的数列crr*)
    
13. SeedRandom[11];
    
14. arr = Range[zongshu];
    
15. crr = {};
    
16. For[i = 1, i <= zongshu, i++,
    
17.           n = Random[Integer, Length[arr] - 1] + 1;
    
18.           AppendTo[crr, arr[[n]]];
    
19.           arr = Delete[arr, n];
    
20.   ];
    
21. crr;
    
22. (*每一次可以掉换数列brr中的任意两个数字的位置,那么至少需要调换多少次才能使得brr与crr完全相同?*)

复制代码

guocong89

抛砖引玉一下
感觉这是个算法题，也是个群代数的题。

把brr看作基准，每个数的order是1：3000，那么crr中的数的order是3000的一个排列，这相当于得到一个置换群。
问题就是要求把这个置换群拆分成对换的次数。

因为不是学数学的，对群的知识知道的不是太多，这只是我的一个思路。

marveloustau

我觉得这个和群关系不大. 通过简单的算法分析就可以知道, 这个数组里的元素存在偏序关系, 因为它们只能进行交换. 所以给定任意一个目标数组, 总存在一个原始数组的最坏情况, 就是要交换n(n-1)/2次. 它其实等价于给数组进行排序, 你只要把目标数组对应到一个Range[3000]的升序数列, 然后再把源数组中的项按照目标数组的对应关系进行替换, 它就变成一个排序问题了. 统计一下排序时需要交换的次数就行.