Board logo

标题: 一个有限制的排序算法题 [打印本页]

作者: 老刘1号    时间: 2019-1-22 12:17     标题: 一个有限制的排序算法题

昨天群里看到的,
【吐槽】Tiger<haotian.fan@qq.com> 下午 2:09:55
网上看见一道题目,问下大家,
如果一个List只能移动第一项,请问如何排序?
【中华】zhonghua(1138520994) 下午 3:02:33
@Tiger Tiger 只能移动第一项是啥意思,栈之类的结构么
【吐槽】Tiger<haotian.fan@qq.com> 下午 3:02:56
就比如说 5 1 3 2 4只能移动5,不能移动其他元素
【吐槽】Tiger<haotian.fan@qq.com> 下午 3:03:11
stack overflow看到的,有点解不开
【中华】zhonghua(1138520994) 下午 3:04:28
这个移动是啥意思
pop(0)?
【吐槽】Tiger<haotian.fan@qq.com> 下午 3:04:54
比如说移到3后面就编程1 3 5 2 4

我的解法(伪插入排序,效率底下,各位大佬见笑):
  1. @echo off
  2. Setlocal enabledelayedexpansion
  3. ::CODER BY 老刘 POWERD BY iBAT
  4. Set /p List=
  5. Call :GetList !List!
  6. Set /A Count=1
  7. :Loop 首项逆向比较
  8. Set /A Flag1=0
  9. For /l %%a in (!prt! -1 1) Do (
  10. If !.1! Gtr !.%%a! (
  11. Call :MoveTo %%a
  12. Set /A Flag1=1
  13. Goto :JmpOut
  14. )
  15. )
  16. :JmpOut
  17. If !Flag1! Equ 1 Goto Loop
  18. Set /A Count+=1
  19. If !Count! Leq !prt! (
  20. Call :MoveTo !Count!
  21. Goto :Loop
  22. )
  23. For /l %%a in (1 1 !prt!) Do Set .%%a
  24. pause&"%~0"
  25. :GetList
  26. Set /A Prt=0
  27. Set list=%*
  28. For %%a In (%*) Do (
  29. Set /A Prt+=1
  30. Set .!Prt!=%%a
  31. )
  32. Goto :Eof
  33. :MoveTo 移动到原先第%1项的后面
  34. Set /A #=.1
  35. For /l %%a in (1 1 %1) Do (
  36. Set /A PlusOne=%%a+1
  37. Set /A .%%a=.!PlusOne!
  38. )
  39. Set /A .%1=#
  40. Goto :Eof
复制代码

作者: 523066680    时间: 2019-1-22 12:34

本帖最后由 523066680 于 2019-1-22 12:44 编辑

回复 1# 老刘1号

问题1,只有首个元素可以移动,他可以移动到任意位置吗
若按C数组操作,如果你可以移动到中间位置,那不是还等于其他元素也可以移动了
问题2,想看stackoverflow原帖,也许是leetcode上面的题目?
作者: 老刘1号    时间: 2019-1-22 12:52

本帖最后由 老刘1号 于 2019-1-24 13:06 编辑

回复 2# 523066680


    刚去拷问了一波问主,原话
每次移动完以后,只能移动第一个,插入以后,列表开头就是新的可移动元素

作者: 523066680    时间: 2019-1-22 12:57

本帖最后由 523066680 于 2019-1-22 13:13 编辑

int a[5] = {a,b,c,d,e} 把数组变成 {b,c,a,d,e}
b和c 不是从 1,2的位置变成了 0,1的位置吗。(这种允许的话,感觉跟打牌手法的插入排序差不多。)

除非说这是一个定制的数据结构,每个数之间有足够的间隙,开头的数字可以插入任意数字中间而其他数字不需要移动。
比如 a,,,,b,,,,c,,,,d,,,,e,,,,

回复 5# 老刘1号
    不纠结数据结构,纠结的是描述。觉得你现在的描述就比较合理了,其他数字被动移动。
作者: 老刘1号    时间: 2019-1-22 13:10

回复 4# 523066680


    总觉得不需要纠结结构……
我觉得问主的意思就是,第一个随意移动,其余的被动移动,顺便改变位置
作者: 老刘1号    时间: 2019-1-22 13:29

补一个优化版
  1. @echo off
  2. Setlocal enabledelayedexpansion
  3. ::CODER BY 老刘 POWERD BY iBAT
  4. Set /p List=
  5. Call :GetList !List!
  6. Set /A Count=1
  7. :Loop
  8. Rem 首项逆向比较
  9. Set /A Flag1=0
  10. For /l %%a in (!prt! -1 1) Do (
  11. If !.1! Gtr !.%%a! (
  12. Call :MoveTo %%a
  13. set/p=移动到%%a后:<nul
  14. For /l %%a in (1 1 !prt!) Do Set/p=!.%%a!-<nul
  15. Echo.
  16. Set /A Flag1=1
  17. Goto :JmpOut
  18. )
  19. )
  20. :JmpOut
  21. If !Flag1! Equ 1 Goto Loop
  22. Rem 判断是否排序完成。
  23. Set /A Flag2=0
  24. For /l %%a in (1 1 !prt!) Do (
  25. Set /A PlusOne=%%a+1
  26. Set /A "#=.!PlusOne!"
  27. If !#! Lss !.%%a! (
  28. Set Flag2=1
  29. If %%a equ !prt! Set Flag2=0
  30. Goto :JmpOut2
  31. )
  32. )
  33. :JmpOut2
  34. If !Flag2! Equ 0 Goto End
  35. Rem 继续排序
  36. Set /A Count+=1
  37. If !Count! Leq !prt! (
  38. Call :MoveTo !Count!
  39. Set/p=移动到!Count!后:<nul
  40. For /l %%a in (1 1 !prt!) Do Set/p=!.%%a!-<nul
  41. Echo.
  42. Goto :Loop
  43. )
  44. :End
  45. For /l %%a in (1 1 !prt!) Do Set/p=!.%%a!-<nul
  46. Echo.&pause&"%~0"
  47. :GetList
  48. Set /A Prt=0
  49. Set list=%*
  50. For %%a In (%*) Do (
  51. Set /A Prt+=1
  52. Set .!Prt!=%%a
  53. )
  54. Goto :Eof
  55. :MoveTo 移动到原先第%1项的后面
  56. Set /A #=.1
  57. For /l %%a in (1 1 %1) Do (
  58. Set /A PlusOne=%%a+1
  59. Set /A .%%a=.!PlusOne!
  60. )
  61. Set /A .%1=#
  62. Goto :Eof
复制代码
  1. 5 1 3 2 4
  2. 移动到5后:1-3-2-4-5-
  3. 移动到2后:3-1-2-4-5-
  4. 移动到3后:1-2-3-4-5-
  5. 1-2-3-4-5-
  6. 请按任意键继续. . .
  7. 3 2 1
  8. 移动到3后:2-1-3-
  9. 移动到2后:1-2-3-
  10. 1-2-3-
  11. 请按任意键继续. . .
  12. 7 3 4 1 10 9 8 11 24
  13. 移动到4后:3-4-1-7-10-9-8-11-24-
  14. 移动到3后:4-1-3-7-10-9-8-11-24-
  15. 移动到3后:1-3-4-7-10-9-8-11-24-
  16. 移动到2后:3-1-4-7-10-9-8-11-24-
  17. 移动到2后:1-3-4-7-10-9-8-11-24-
  18. 移动到3后:3-4-1-7-10-9-8-11-24-
  19. 移动到3后:4-1-3-7-10-9-8-11-24-
  20. 移动到3后:1-3-4-7-10-9-8-11-24-
  21. 移动到4后:3-4-7-1-10-9-8-11-24-
  22. 移动到4后:4-7-1-3-10-9-8-11-24-
  23. 移动到4后:7-1-3-4-10-9-8-11-24-
  24. 移动到4后:1-3-4-7-10-9-8-11-24-
  25. 移动到5后:3-4-7-10-1-9-8-11-24-
  26. 移动到5后:4-7-10-1-3-9-8-11-24-
  27. 移动到5后:7-10-1-3-4-9-8-11-24-
  28. 移动到5后:10-1-3-4-7-9-8-11-24-
  29. 移动到7后:1-3-4-7-9-8-10-11-24-
  30. 移动到6后:3-4-7-9-8-1-10-11-24-
  31. 移动到6后:4-7-9-8-1-3-10-11-24-
  32. 移动到6后:7-9-8-1-3-4-10-11-24-
  33. 移动到6后:9-8-1-3-4-7-10-11-24-
  34. 移动到6后:8-1-3-4-7-9-10-11-24-
  35. 移动到5后:1-3-4-7-8-9-10-11-24-
  36. 1-3-4-7-8-9-10-11-24-
  37. 请按任意键继续. . .
  38. 1 2 3 5 4
  39. 移动到2后:2-1-3-5-4-
  40. 移动到2后:1-2-3-5-4-
  41. 移动到3后:2-3-1-5-4-
  42. 移动到3后:3-1-2-5-4-
  43. 移动到3后:1-2-3-5-4-
  44. 移动到4后:2-3-5-1-4-
  45. 移动到4后:3-5-1-2-4-
  46. 移动到4后:5-1-2-3-4-
  47. 移动到5后:1-2-3-4-5-
  48. 1-2-3-4-5-
  49. 请按任意键继续. . .
复制代码

作者: 523066680    时间: 2019-1-22 13:49

本帖最后由 523066680 于 2019-1-22 15:13 编辑

有缺陷/未完成,大概方向,unshift 取出首个数字,和剩下的各个元素做减法,找出相差距离最近的数字(分为L和R)的对应坐标,插入。可能做足判断会好一些,待完善。
  1. my @arr = qw/5 1 9 3 2 4 6/;
  2. my ($first, $L,$R,$r_id, $l_id, $dt);
  3. my $max = 100000;
  4. for (1..5)
  5. {
  6.     $first = shift @arr;
  7.     $L = -$max;
  8.     $R = $max;
  9.     $r_id = 0;
  10.     $l_id = 0;
  11.     for $i ( 0 .. $#arr ) {
  12.         $dt = $arr[$i] - $first;
  13.         if ( $dt > 0 && $dt <= $R) { $r_id = $i, $R = $dt; }
  14.         if ( $dt < 0 && $dt >= $L) { $l_id = $i, $L = $dt; }
  15.     }
  16.     if ( $R == $max ) {
  17.         push @arr, $first;
  18.     } else {
  19.         splice( @arr, $r_id, 0, $first );
  20.     }
  21.     #printf "%d - %d: %d, %d: %d\n", $first, $l_id, $L, $r_id, $R;
  22.     print join(",", @arr), "\n";
  23. }
  24. #print join("", @arr);
复制代码
1,9,3,2,4,5,6
9,3,1,2,4,5,6
3,1,2,4,5,6,9
1,2,3,4,5,6,9

特地找一副扑克牌玩了一下,为啥人玩起来就这么自然…… 转成代码总是有纰漏,
纠正了某些情况下不能完全处理的问题,也未经过严格验证,暂时这样。
  1. my @arr = qw/7 3 4 1 10 9 8 11 24/;
  2. my ($first, $L,$R,$r_id, $l_id, $dt);
  3. my $max = 100000;
  4. my $ok = 0;
  5. while (1)
  6. {
  7.     $first = shift @arr;
  8.     $L = -$max;
  9.     $R = $max;
  10.     $r_id = 0;
  11.     $l_id = 0;
  12.     for $i ( 0 .. $#arr ) {
  13.         $dt = $arr[$i] - $first;
  14.         if ( $dt > 0 && $dt <= $R) { $r_id = $i, $R = $dt; }
  15.         if ( $dt < 0 && $dt >= $L) { $l_id = $i, $L = $dt; }
  16.     }
  17.     if ( $L != -$max )
  18.     {
  19.         # 如果有相对较小的数字,优先移至最邻近者
  20.         splice( @arr, $l_id+1, 0, $first );
  21.     } else {
  22.         if ( $R == $max ) {
  23.             # 如果未找到更大的数字,直接堆到最后
  24.             push @arr, $first;
  25.         } else {
  26.             # 判断数组中是否还有 左边大于右边的情况
  27.             $ok = 1;
  28.             for my $i ( 0 .. $#arr-1 ) {
  29.                 if ( $arr[$i] > $arr[$i+1] ) {
  30.                     splice( @arr, $i+1, 0, $first );
  31.                     $ok = 0;
  32.                     last;
  33.                 }
  34.             }
  35.             last if $ok;
  36.         }
  37.     }
  38.     #printf "%d -- [%d]: %d, [%d]: %d\n", $first, $l_id, $L, $r_id, $R;
  39.     print join(",", @arr), "\n";
  40. }
复制代码
  1. 3,4,7,1,10,9,8,11,24
  2. 4,7,1,3,10,9,8,11,24
  3. 7,1,3,4,10,9,8,11,24
  4. 1,3,4,7,10,9,8,11,24
  5. 3,4,7,10,1,9,8,11,24
  6. 4,7,10,1,3,9,8,11,24
  7. 7,10,1,3,4,9,8,11,24
  8. 10,1,3,4,7,9,8,11,24
  9. 1,3,4,7,9,10,8,11,24
  10. 3,4,7,9,10,1,8,11,24
  11. 4,7,9,10,1,3,8,11,24
  12. 7,9,10,1,3,4,8,11,24
  13. 9,10,1,3,4,7,8,11,24
  14. 10,1,3,4,7,8,9,11,24
  15. 1,3,4,7,8,9,10,11,24
复制代码
  1. 2,3,5,1,4
  2. 3,5,1,2,4
  3. 5,1,2,3,4
  4. 1,2,3,4,5
复制代码

作者: 老刘1号    时间: 2019-1-22 13:57

本帖最后由 老刘1号 于 2019-1-22 14:28 编辑

回复 7# 523066680


    好思路,若完成效率应该比我那个高
250技术不忍破坏
作者: 523066680    时间: 2019-1-22 15:37

回复 8# 老刘1号

    已更新
作者: 老刘1号    时间: 2019-1-22 16:54

本帖最后由 老刘1号 于 2019-1-22 16:55 编辑

回复 9# 523066680


    若不考虑效率的话,感觉可以把只移动首个元素这个限制用一个算法去除掉,直接完成任意两元素交换。
a b c d e f
b <-- --> e
b c d e f a
c d e b f a
d e b f a c
e b f a c d
b f a e c d
f a e c d b
a e c d b f

a b c d e f
a <-- --> c
b c a d e f
c a d e f b
a d e f c b
d e f c b a
e f c b a d
f c b a d e
c b a d e f

a b c
a <-- --> c
b c a
c a b
a c b
c b a

脑补算法中
作者: 523066680    时间: 2019-1-22 17:09

本帖最后由 523066680 于 2019-1-22 17:32 编辑

试试粗暴一点,递归求不同解、最优解。(逻辑不够完整,怕卡太久,限制了层数 lv <= 5),
  1. my @arr = qw/8 9 1 2 5/;
  2. my @order = ();
  3. our @ways;
  4. solver(0, \@order, @arr);
  5. my $first;
  6. for my $w ( @ways )
  7. {
  8.     printf "Solution: %s\n", join(",", @$w);
  9.     my @brr = @arr;
  10.     for my $mov ( @$w )
  11.     {
  12.         $first = shift @brr;
  13.         splice( @brr, $mov, 0, $first );
  14.         printf "%s\n", join(",", @brr);
  15.     }
  16.     printf "\n";
  17. }
  18. sub solver
  19. {
  20.     my ($lv, $order) = (shift, shift);
  21.     my @arr = @_;
  22.     my @brr;
  23.     my $first;
  24.     my $res;
  25.     return if $lv == 5;
  26.     if (check(\@arr) == -1) {
  27.         #printf "[%d] %s %s\n", $lv, join(",", @arr), join(",", @brr);
  28.         for my $i ( 1 .. $#arr ) {
  29.             @brr = @arr[1..$#arr];
  30.             splice(@brr, $i, 0, $arr[0] );
  31.             $order[$lv] = $i;
  32.             $res = solver( $lv+1, $order, @brr );
  33.             #if ( $res == 1 ) {last;}
  34.         }
  35.         return 1 if $res == 1;
  36.     } else {
  37.         #printf "%s\n", join(",", @arr);
  38.         push @ways, [@{$order}[0..$lv-1] ];
  39.         return 1;
  40.     }
  41. }
  42. sub check
  43. {
  44.     my $ar = shift;
  45.     grep { return -1 if ( $ar->[$_] > $ar->[$_+1] ) } ( 0 .. $#$ar-1);
  46.     return 1;
  47. }
复制代码
  1. Solution: 1,1,4,4
  2. 9,8,1,2,5
  3. 8,9,1,2,5
  4. 9,1,2,5,8
  5. 1,2,5,8,9
  6. Solution: 1,4,3
  7. 9,8,1,2,5
  8. 8,1,2,5,9
  9. 1,2,5,8,9
  10. Solution: 2,4,1,3
  11. 9,1,8,2,5
  12. 1,8,2,5,9
  13. 8,1,2,5,9
  14. 1,2,5,8,9
  15. Solution: 4,1,1,4
  16. 9,1,2,5,8
  17. 1,9,2,5,8
  18. 9,1,2,5,8
  19. 1,2,5,8,9
  20. Solution: 4,4
  21. 9,1,2,5,8
  22. 1,2,5,8,9
  23. [Finished in 0.1s]
复制代码
粗暴中发现那个数组的处理过程可以更短,6次解决:
  1. Move Steps: 5,5,5,2,6,5
  2. 3,4,7,1,10,9,8,11,24 <- Original
  3. 4,7,1,10,9,3,8,11,24
  4. 7,1,10,9,3,4,8,11,24
  5. 1,10,9,3,4,7,8,11,24
  6. 10,9,1,3,4,7,8,11,24
  7. 9,1,3,4,7,8,10,11,24
  8. 1,3,4,7,8,9,10,11,24
复制代码

作者: 523066680    时间: 2019-1-22 17:43

本帖最后由 523066680 于 2019-1-22 17:51 编辑

回复 1# 老刘1号

    Tiger就是那个初中一年级,做MIT英文原版数学试卷、精通C++、Python、JAVA,熟练 PyTorch、 Tensorflow、会写CNN DNN RNN KNN,的神奇少年吗。
看到那个群里这么多大神,吓得我退群点了个外卖。
作者: 老刘1号    时间: 2019-1-22 17:51

回复 12# 523066680


    哈哈哈,人是那个人,群不是那个群
作者: 老刘1号    时间: 2019-1-22 18:44

本帖最后由 老刘1号 于 2019-1-22 19:11 编辑

回复 12# 523066680


    伪元素交换的算法摸清了……
找个位置真费脑……杀了一大片脑细胞
  1. @echo off
  2. Setlocal enabledelayedexpansion
  3. ::CODER BY 老刘 POWERD BY iBAT
  4. ::Set /p List=
  5. Call :GetList 1 2 3 4 5
  6. Call :Xchg 1 4
  7. Call :Echo
  8. Call :Xchg 2 3
  9. Call :Echo
  10. Call :Xchg 2 5
  11. Call :Echo
  12. Call :Xchg 3 4
  13. Call :Echo
  14. Pause
  15. Exit
  16. :GetList
  17. Set /A Prt=0
  18. Set list=%*
  19. For %%a In (%*) Do (
  20. Set /A Prt+=1
  21. Set .!Prt!=%%a
  22. )
  23. Goto :Eof
  24. :XChg 两元素互换
  25. Rem 将需要互换的第一个元素换到第一位
  26. Set /A SubOne=%1-1
  27. For /l %%a in (1 1 !SubOne!) Do Call :MoveTo !Prt!
  28. Set /a Steps+=SubOne
  29. Rem 将需要互换的第一个元素塞到第二个元素后面
  30. Rem 计算新list中第二个元素的位置
  31. Set /A Arg2Index=%2-SubOne
  32. Rem 挪
  33. Call :MoveTo !Arg2Index!
  34. Set /a Steps+=1
  35. Rem 将需要互换的第二个元素换到第一位
  36. Set /a Arg2SubArg1SubOne=%2-%1-1
  37. For /l %%a in (1 1 !Arg2SubArg1SubOne!) Do Call :MoveTo !Prt!
  38. Set /a Steps+=Arg2SubArg1SubOne
  39. Rem 将第二个元素塞到原先第一个元素的位置
  40. Rem 计算新list中第一个元素之前元素的位置
  41. Set /a 第一个元素之前元素的位置=(%1+1)-(SubOne+1+Arg2SubArg1SubOne)+prt-1
  42. Rem 挪
  43. Call :MoveTo !第一个元素之前元素的位置!
  44. Set /a Steps+=1
  45. Rem 还原其余各元素位置
  46. Set /A Reserve=prt-((SubOne+1+Arg2SubArg1SubOne)-1)-1
  47. For /l %%a in (1 1 !Reserve!) Do Call :MoveTo !Prt!
  48. Set /a Steps+=Reserve
  49. Goto :Eof
  50. :MoveTo 移动到原先第%1个元素的后面
  51. Set /A #=.1
  52. For /l %%a in (1 1 %1) Do (
  53. Set /A PlusOne=%%a+1
  54. Set /A .%%a=.!PlusOne!
  55. )
  56. Set /A .%1=#
  57. Goto :Eof
  58. :Echo
  59. For /l %%a in (1 1 !prt!) Do Set/p=!.%%a!-<nul
  60. Echo.
  61. Goto :Eof
复制代码
4-2-3-1-5-
4-3-2-1-5-
4-5-2-1-3-
4-5-1-2-3-
请按任意键继续. . .

作者: 523066680    时间: 2019-1-22 18:51

本帖最后由 523066680 于 2019-1-22 19:01 编辑

回复 14# 老刘1号

你用批处理,在解决问题的时候还要为批处理伤脑筋,很不容易~
要是换成其他脚本,各种骚操作、语法糖用了再说,舒服。

但仔细想想确实很蛋疼的感觉,不想写
作者: 老刘1号    时间: 2019-1-22 18:56

回复 15# 523066680


    哈哈,这和批处理倒是关系不大, 主要是用“只移动第一个元素”来模拟“交换任意两个元素”比较蛋疼
作者: 523066680    时间: 2019-1-22 19:04

本帖最后由 523066680 于 2019-1-22 21:36 编辑

回复 16# 老刘1号

移动两个元素的同时还要保持其他元素的原有顺序,感觉好蛋疼

犯了一个数组坐标偏移计算错误,花了很多时间去矫正(就是临时数组消减后下标减小了,失算)
  1. my @idx = qw/0 1 2 3 4/;
  2. my ($a, $b) = (3,4);
  3. my $apos = $a;
  4. my $bpos = $b;
  5. my $exchange = 0;
  6. printf "%d %d, %s\n", $apos, $bpos, join(",", @idx);
  7. # 首位数插入idx[$b]的前方
  8. $first = shift @idx;
  9. splice( @idx, $b-1, 0, $first );
  10. $apos-=1;
  11. printf "%d %d, %s\n", $apos, $bpos, join(",", @idx);
  12. while (1)
  13. {
  14.     $first = shift @idx;
  15.     if ( $first == $a ) {
  16.         splice( @idx, $bpos, 0, $first );
  17.         $apos = $bpos;
  18.         $bpos -= 1;
  19.         $exchange = 1;
  20.     } else {
  21.         if ( $bpos ne $a ) {
  22.             if ($exchange) {
  23.                 splice( @idx, $apos-1, 0, $first );
  24.                 $bpos -= 1;
  25.             } else {
  26.                 splice( @idx, $bpos-1, 0, $first );
  27.                 $apos -= 1;
  28.             }
  29.         } else {
  30.             last;
  31.         }
  32.     }
  33.     printf "%d %d, %s\n", $apos, $bpos, join(",", @idx);
  34. }
复制代码
前面两个数是位置变化
  1. 3 4, 0,1,2,3,4
  2. 2 4, 1,2,3,0,4
  3. 1 4, 2,3,0,1,4
  4. 0 4, 3,0,1,2,4
  5. 4 3, 0,1,2,4,3
复制代码

作者: 老刘1号    时间: 2019-1-22 19:05

本帖最后由 老刘1号 于 2019-1-22 19:23 编辑

补一个冒泡排序
  1. @echo off
  2. Setlocal enabledelayedexpansion
  3. ::CODER BY 老刘 POWERD BY iBAT
  4. Set /p List=
  5. Set /A Steps=0
  6. Call :冒泡排序算法 !List!
  7. Call :Echo
  8. Echo 第一个元素被移动的次数:!Steps!
  9. Pause
  10. :冒泡排序算法
  11. Call :GetList %*
  12. :Loop
  13. Set Flag=0
  14. For /l %%a in (2 1 !prt!) Do (
  15. Set /A SubOne=%%a-1
  16. Set /A #=.!SubOne!
  17. If !#! Gtr !.%%a! (
  18. Call :XChg !SubOne! %%a
  19. Set /A Flag=1
  20. )
  21. )
  22. If !Flag! Equ 1 Goto :Loop
  23. Goto :Eof
  24. :GetList
  25. Set /A Prt=0
  26. Set list=%*
  27. For %%a In (%*) Do (
  28. Set /A Prt+=1
  29. Set .!Prt!=%%a
  30. )
  31. Goto :Eof
  32. :XChg 两元素互换
  33. Rem 将需要互换的第一个元素换到第一位
  34. Set /A SubOne=%1-1
  35. For /l %%a in (1 1 !SubOne!) Do Call :MoveTo !Prt!
  36. Set /a Steps+=SubOne
  37. Rem 将需要互换的第一个元素塞到第二个元素后面
  38. Rem 计算新list中第二个元素的位置
  39. Set /A Arg2Index=%2-SubOne
  40. Rem 挪
  41. Call :MoveTo !Arg2Index!
  42. Set /a Steps+=1
  43. Rem 将需要互换的第二个元素换到第一位
  44. Set /a Arg2SubArg1SubOne=%2-%1-1
  45. For /l %%a in (1 1 !Arg2SubArg1SubOne!) Do Call :MoveTo !Prt!
  46. Set /a Steps+=Arg2SubArg1SubOne
  47. Rem 将第二个元素塞到原先第一个元素的位置
  48. Rem 计算新list中第一个元素之前元素的位置
  49. Set /a 第一个元素之前元素的位置=(%1+1)-(SubOne+1+Arg2SubArg1SubOne)+prt-1
  50. Rem 挪
  51. Call :MoveTo !第一个元素之前元素的位置!
  52. Set /a Steps+=1
  53. Rem 还原其余各元素位置
  54. Set /A Reserve=prt-((SubOne+1+Arg2SubArg1SubOne)-1)-1
  55. For /l %%a in (1 1 !Reserve!) Do Call :MoveTo !Prt!
  56. Set /a Steps+=Reserve
  57. Goto :Eof
  58. :MoveTo 移动到原先第%1个元素的后面
  59. Set /A #=.1
  60. For /l %%a in (1 1 %1) Do (
  61. Set /A PlusOne=%%a+1
  62. Set /A .%%a=.!PlusOne!
  63. )
  64. Set /A .%1=#
  65. Goto :Eof
  66. :Echo
  67. For /l %%a in (1 1 !prt!) Do Set/p=!.%%a!-<nul
  68. Echo.
  69. Goto :Eof
复制代码
7 3 4 1 10 9 8 11 24
1-3-4-7-8-9-10-11-24-
第一个元素被移动的次数:80
请按任意键继续. . .

作者: 老刘1号    时间: 2019-1-22 19:32

本帖最后由 老刘1号 于 2019-1-22 23:51 编辑

选择排序
  1. @echo off
  2. Setlocal enabledelayedexpansion
  3. ::CODER BY 老刘 POWERD BY iBAT
  4. Set /p List=
  5. Set /A Steps=0
  6. Call :选择排序算法 !List!
  7. Call :Echo
  8. Echo 第一个元素被移动的次数:!Steps!
  9. Pause
  10. :选择排序算法
  11. Call :GetList %*
  12. Set /A Count=0
  13. :Loop
  14. Set /A Count+=1
  15. Set /A #=.!Count!
  16. For /l %%a in (!Count! 1 !prt!) Do (
  17. If !.%%a! Leq !#! (
  18. Set /A #=.%%a
  19. Set /A Index=%%a
  20. )
  21. )
  22. If !Count! Neq !Index! Call :XChg !Count! !Index!
  23. If !Count! Lss !prt! Goto :Loop
  24. Goto :Eof
  25. :GetList
  26. Set /A Prt=0
  27. Set list=%*
  28. For %%a In (%*) Do (
  29. Set /A Prt+=1
  30. Set .!Prt!=%%a
  31. )
  32. Goto :Eof
  33. :XChg 两元素互换
  34. Rem 将需要互换的第一个元素换到第一位
  35. Set /A SubOne=%1-1
  36. For /l %%a in (1 1 !SubOne!) Do Call :MoveTo !Prt!
  37. Set /a Steps+=SubOne
  38. Rem 将需要互换的第一个元素塞到第二个元素后面
  39. Rem 计算新list中第二个元素的位置
  40. Set /A Arg2Index=%2-SubOne
  41. Rem 挪
  42. Call :MoveTo !Arg2Index!
  43. Set /a Steps+=1
  44. Rem 将需要互换的第二个元素换到第一位
  45. Set /a Arg2SubArg1SubOne=%2-%1-1
  46. For /l %%a in (1 1 !Arg2SubArg1SubOne!) Do Call :MoveTo !Prt!
  47. Set /a Steps+=Arg2SubArg1SubOne
  48. Rem 将第二个元素塞到原先第一个元素的位置
  49. Rem 计算新list中第一个元素之前元素的位置
  50. Set /a 第一个元素之前元素的位置=(%1+1)-(SubOne+1+Arg2SubArg1SubOne)+prt-1
  51. Rem 挪
  52. Call :MoveTo !第一个元素之前元素的位置!
  53. Set /a Steps+=1
  54. Rem 还原其余各元素位置
  55. Set /A Reserve=prt-((SubOne+1+Arg2SubArg1SubOne)-1)-1
  56. For /l %%a in (1 1 !Reserve!) Do Call :MoveTo !Prt!
  57. Set /a Steps+=Reserve
  58. Goto :Eof
  59. :MoveTo 移动到原先第%1个元素的后面
  60. Set /A #=.1
  61. For /l %%a in (1 1 %1) Do (
  62. Set /A PlusOne=%%a+1
  63. Set /A .%%a=.!PlusOne!
  64. )
  65. Set /A .%1=#
  66. Goto :Eof
  67. :Echo
  68. For /l %%a in (1 1 !prt!) Do Set/p=!.%%a!-<nul
  69. Echo.
  70. Goto :Eof
复制代码
7 3 4 1 10 9 8 11 24
1-3-4-7-8-9-10-11-24-
第一个元素被移动的次数:20
请按任意键继续. . .

作者: search_Sudoku    时间: 2019-1-22 21:47

1 3 5 2 4
3 5 2 1 4
5 2 1 3 4
2 1 3 4 5
1 2 3 4 5


第 1 次 对 首元素 在 表后部 长度为 1 的子表中 检索(二分法) 找到 应插入的位置
第 2 次 对 首元素 在 表后部 长度为 2 的子表中 检索(二分法) 找到 应插入的位置
第 3 次 对 首元素 在 表后部 长度为 3 的子表中 检索(二分法) 找到 应插入的位置
第 4 次 对 首元素 在 表后部 长度为 4 的子表中 检索(二分法) 找到 应插入的位置
第 5 次 对 首元素 在 表后部 长度为 5 的子表中 检索(二分法) 找到 应插入的位置
...     对
第 i 次 对 首元素 在 表后部 长度为 i 的子表中 检索(二分法) 找到 应插入的位置


要排序的表元素为 n 个, 移动插入的总次数在最差情况下为 n

优化算法在于最优化检索算法, 比如用二分检索
作者: 523066680    时间: 2019-1-22 21:54

本帖最后由 523066680 于 2019-1-22 22:25 编辑

回复 20# search_Sudoku

惊醒梦中人,我竟然没意识到到这个过程同样可以构建一个逐步扩大的有序列表, why didn't I think of that!
这样完全可以获得[步数]在[元素个数]以内的解,无论效率还是实现,应该都是最佳方案。

本来我在想那个递归跑出来的最短步骤解,但是想想就像通常情况下的的排序,某些解同样有更快的步骤,这些步骤的缩减有时只能是针对性的,即使实现了,也会改变效率的“天枰”。
作者: search_Sudoku    时间: 2019-1-22 22:12

本帖最后由 search_Sudoku 于 2019-1-23 10:09 编辑

回复 21# 523066680


子表 的起始长度 可以不从 1 开始, 而是找出当前表后部的最长有序子表, 这样可以减少插入的次数,

对 m 个元素的表 T 排序, 找出表尾的最大有序子表 Ts, 此子表长度为 n, 那么只需要且至少需要 m-n 次移动完成排序

将原表表示如下, 括号内为下标序号
E(1), E(2), E(3), ...., X, E(m-n+1), E(m-n+2), E(m-n+3),..., E(m)

X 的序号是 m-n, X 和 E(m-n+1) 是逆序的

E(m-n+1), E(m-n+2), E(m-n+3),..., E(m) 是一个已经达成目标序的最大有序子表

每一次移动操作如果是把首位置元素移动插入到 Ts, 将使 Ts 的长度增 1, 将只需要 m-n 次移动插入即完成排序

如果有任何一次插入目标位置是在 X 的位置之前, 将不可能减少1次插入次数, 因为 X 必须在前面所有元素都移动之后才能移动, 而且 X 也必须移动才能使全表有序(因为 X 在移动之前至少有一个后面位置的元素与其形成逆序关系).

如果有任何一次把元素 Y 插入到目标位置是在 X 相邻的后一位置, 但没有和后面的 Ts 构成一个更大的有序子表, 换言之, 即 Y 与 相邻的后一位置的元素仍是逆序关系, 也一样不能减少 1 次插入次数, 设 Y 移动之前 Ts 的长度已经增长到 L, 那么还至少需要 m-L 次移动插入才能完成排序, 而 Y 的移动并没有增长 Ts 的长度, 那么其移动插入之后, 就一样至少需要 m-L 次移动插入才能完成排序.

综上, 结论: 对 m 个元素的表 T 排序, 找出表尾的最大有序子表 Ts, 此子表长度为 n, 那么只需要且至少需要 m-n 次移动完成排序

算法在开始从表尾向前面逐次对相邻2元素比较, 直到出现逆序, 以此确定表尾的最大长度有序子表, 之后再进行 m-n 次检索移动插入的操作完成全表排序
作者: search_Sudoku    时间: 2019-1-22 22:31

回复 21# 523066680

不同的排序算法自然不能以最好情况下的效率做比较, 而是要以平均效率做比较

我思考这个算法的过程是逆推的:

假设原表T (长度为 L)已是完全有序的, 需要插入的次数是 0

如果不是完全有序的, 就至少要做一次插入操作

在最后一次插入时, 表后部的 长度为 L-1 的子表必然已经是一个完全有序的表(设这个表为T1)

如果 T1 也是由插入操作之后得到的, 那么 去除 那个 插入进来(插入位置包括最前部和最尾部)的元素, 长度为 L-2 的子表 T2 必然也是一个完全有序表,

...

逆推到第一次插入之前, 必然在全表后部存在一个完全有序表, 这个完全有序子表最大长度为 L (也就是全表本来就是完全有序的), 最小长度是 1(表尾后部的两个元素是逆序的)
作者: 老刘1号    时间: 2019-1-23 00:09

回复 17# 523066680


    学习了,又秒杀我那个无脑挪法……(固定挪表长+1次)
不知有没有最佳方案,明天再想想
论坛真是藏龙卧虎,不发点题都不肯出来
作者: 523066680    时间: 2019-1-23 08:53

本帖最后由 523066680 于 2019-1-23 12:47 编辑

回复 24# 老刘1号

我先用递归跑出来一些结果,然后去强行找规律、强行解释一波,发现没什么大的漏洞就拿来用了

有明确的调换方法,假设要调换列标3和7

012345678  -  将7和3位置调换,可以预见的是3和7调换后,012在7的前面(成为7的前缀);456同理;
012345601278  -
将排头的012依次插入7的前方。
0003456012738 -
0127已经达成,现在开头的是数字3,将它放在数字7后面
00004560127
45638 - 然后将前缀456插入数字3的前面。


有了这个规则,就可以来一波语法糖
  1. my @index = qw/0 1 2 3 4 5 6 7 8/;
  2. my ($a, $b) = (3,7);
  3. my ($apos, $bpos) = ($a, $b);
  4. my $show = sub {printf "[%d,%d] %s\n", $apos, $bpos, join(",", @index)};
  5. $show->();
  6. # $a 的前缀转移到 $b 前面
  7. grep { splice( @index, $bpos-1, 0, shift @index ); $apos--; $show->() } (1..$a);
  8. # $a 移到 $b 后面
  9. splice( @index, $bpos, 0, shift @index );
  10. $apos = $bpos, $bpos--;
  11. $show->();
  12. # $b 的前缀转移到 $a 前面
  13. grep { splice( @index, $apos-1, 0, shift @index ); $bpos--; $show->() } ($a+1..$b-1);
  14. exit;
复制代码
  1. [3,7] 0,1,2,3,4,5,6,7,8
  2. [2,7] 1,2,3,4,5,6,0,7,8
  3. [1,7] 2,3,4,5,6,0,1,7,8
  4. [0,7] 3,4,5,6,0,1,2,7,8
  5. [7,6] 4,5,6,0,1,2,7,3,8
  6. [7,5] 5,6,0,1,2,7,4,3,8
  7. [7,4] 6,0,1,2,7,4,5,3,8
  8. [7,3] 0,1,2,7,4,5,6,3,8
复制代码
.
回复 26# search_Sudoku

     针对 3,4,7,1,10,9,8,11,24(24暂时用K替代) 昨晚拿着扑克牌手动排了几次,处理方式和你的描述接近但有差异,
差不多7次。晚点儿再实践实践
    又想了想,递归也可以优化优化(暴力解虽然费时,但是省心 )。
作者: search_Sudoku    时间: 2019-1-23 10:11

回复 21# 523066680

http://www.bathome.net/redirect. ... 1910&pid=217050

22楼, 我做了一个不太严谨的证明
作者: 老刘1号    时间: 2019-1-23 11:19

回复 22# search_Sudoku


    看懂了,谢大佬
作者: 老刘1号    时间: 2019-1-23 12:00

本帖最后由 老刘1号 于 2019-1-23 12:09 编辑

回复 25# 523066680


    简单明了、高效,学习了。
我的思路(调换3与7)
12345678 - 不想太多,操作3与7就等到能操作的时候再操作,其他按顺序塞到后面
1234567812 - 此时所用步数记作step1
  345673812 - 3与7互换,∴先将3放到7后面
   45673812#456 - 继续无脑挪到7可操作,步数记为step2
      738127456 - 将7放到原先3的位置(4之前)
       3812745638 - 恢复原顺序,步数记为step3

由于一波操作下来除了3其它数字都移动一次,而3移动2次,∴总步数为表长+1
下面默认数组下标从1开始,
step1=%第一个数下标(3)%-1
step2=(%第二个数下标(7)%-%第一个数下标(3)%)-1
#一直固定在最开始第一个数(3)后面一个数(4)的前面
∴要计算第二个数(7)需要移动到的位置,就计算"最开始第一个数后面的一个数(4)“的位置。
由于前面每次移动都必然会移动到4的后面,∴4的新下标=4的原下标-步数+表长=(3的原下标+1)-(step1+1+step2)+表长
∴第二个数(7)需要移动到”4的新下标-1“这个下标代表的数的后面,即"(3的原下标+1)-(step1+1+step2)+表长-1"
step3=总步数-已走步数=(表长+1)-(step1+1+step2+1)

真蛋疼
作者: 523066680    时间: 2019-1-23 15:12

本帖最后由 523066680 于 2019-1-23 16:33 编辑

回复 22# search_Sudoku

      按这个方式实现了(二分搜索没做进去),很利落
  1. =info
  2.     Ref:
  3.     http://www.bathome.net/redirect.php?goto=findpost&ptid=51910&pid=217048
  4. =cut
  5. my @arr = qw/25 23 4 9 8 2 1 12 15/;
  6. my $offset;
  7. my $first;
  8. printf "%s <- Original\n", join(",", @arr);
  9. # 查找末尾有序数组的起点
  10. $offset = $#arr+1 - seqsizes( \@arr );
  11. while ( $offset > 0 || $arr[0] > $arr[1] )
  12. {
  13.     $first = shift @arr;
  14.     insert( \@arr, $offset, $first );
  15.     $offset--;
  16.     printf "%s\n", join(",", @arr);
  17. }
  18. sub insert
  19. {
  20.     my ($arr, $begin, $ele) = @_;
  21.     for my $i ( $begin .. $#$arr ) {
  22.         if ($arr->[$i] > $ele ) { splice( @$arr, $i, 0, $ele ); return; }
  23.     }
  24.     splice( @$arr, $#$arr+1, 0, $ele );
  25. }
  26. sub seqsizes
  27. {
  28.     my ($r, $size) = (shift, 1);
  29.     for my $i (1..$#$r) {
  30.         $r->[-$i] > $r->[-$i-1] ? $size++ : last;
  31.     }
  32.     return $size;
  33. }
复制代码
  1. 3,4,7,1,10,9,8,11,24 <- Original
  2. 4,7,1,10,9,3,8,11,24
  3. 7,1,10,9,3,4,8,11,24
  4. 1,10,9,3,4,7,8,11,24
  5. 10,9,1,3,4,7,8,11,24
  6. 9,1,3,4,7,8,10,11,24
  7. 1,3,4,7,8,9,10,11,24
复制代码
  1. 25,23,4,9,8,2,1,12,15 <- Original
  2. 23,4,9,8,2,1,12,15,25
  3. 4,9,8,2,1,12,15,23,25
  4. 9,8,2,1,4,12,15,23,25
  5. 8,2,1,4,9,12,15,23,25
  6. 2,1,4,8,9,12,15,23,25
  7. 1,2,4,8,9,12,15,23,25
复制代码

作者: 老刘1号    时间: 2019-1-23 19:03

本帖最后由 老刘1号 于 2019-1-23 19:26 编辑

回复 22# search_Sudoku


    用批实现一个,带二分的之后补上,
在表尾构建有序数列(非二分检索,倒序检索).BAT
  1. @echo off
  2. Setlocal enabledelayedexpansion
  3. ::CODER BY 老刘 POWERD BY iBAT
  4. Set /p List=
  5. Call :GetList !List!
  6. Set /A 判断次数=0,挪移次数=0
  7. Rem 确定末尾有序数组的起始位置
  8. Set /A point=prt-1
  9. For /l %%a in (!prt! -1 2) Do (
  10. Set /A SubOne=%%a-1
  11. Set /A #=.!SubOne!
  12. Set /A 判断次数+=1
  13. If !#! Gtr !.%%a! (
  14. Set /A Point=SubOne
  15. Goto :JmpOut1
  16. )
  17. )
  18. :JmpOut1
  19. Rem 挪
  20. For /l %%a in (!Point! -1 1) Do Call :挪 %%a
  21. Goto :Next
  22. :挪
  23. For /l %%b in (!prt! -1 %1) Do (
  24. Set /A 判断次数+=1
  25. If !.1! Gtr !.%%b! (
  26. Call :MoveTo %%b
  27. Set /a 挪移次数+=1
  28. Set/p=移到%%b后:<nul
  29. Call :Echo
  30. Goto :JmpOut2
  31. )
  32. )
  33. :JmpOut2
  34. Rem 处理首个元素比末尾有序数组全小的情况
  35. Set /A 判断次数+=1
  36. If !.1! Lss !.%1! (
  37. Call :MoveTo %1
  38. Set /a 挪移次数+=1
  39. Set/p=移到%1后:<nul
  40. Call :Echo
  41. )
  42. Goto :Eof
  43. :Next
  44. Set 判断次数
  45. Set 挪移次数
  46. pause&"%~0"
  47. :GetList
  48. Set /A Prt=0
  49. Set list=%*
  50. For %%a In (%*) Do (
  51. Set /A Prt+=1
  52. Set .!Prt!=%%a
  53. )
  54. Goto :Eof
  55. :MoveTo 移动到原先第%1项的后面
  56. Set /A #=.1
  57. For /l %%a in (1 1 %1) Do (
  58. Set /A PlusOne=%%a+1
  59. Set /A .%%a=.!PlusOne!
  60. )
  61. Set /A .%1=#
  62. Goto :Eof
  63. :Echo
  64. For /l %%a in (1 1 !prt!) Do Set/p=!.%%a!-<nul
  65. Echo.
  66. Goto :Eof
复制代码
1 3 5 2 4
移到3后:3-5-1-2-4-
移到4后:5-1-2-3-4-
移到5后:1-2-3-4-5-
判断次数=11
挪移次数=3
请按任意键继续. . .
7 3 4 1 10 9 8 11 24
移到6后:3-4-1-10-9-7-8-11-24-
移到5后:4-1-10-9-3-7-8-11-24-
移到5后:1-10-9-3-4-7-8-11-24-
移到4后:10-9-3-1-4-7-8-11-24-
移到7后:9-3-1-4-7-8-10-11-24-
移到6后:3-1-4-7-8-9-10-11-24-
移到2后:1-3-4-7-8-9-10-11-24-
判断次数=38
挪移次数=7
请按任意键继续. . .
25 23 4 9 8 2 1 12 15
移到9后:23-4-9-8-2-1-12-15-25-
移到8后:4-9-8-2-1-12-15-23-25-
移到5后:9-8-2-1-4-12-15-23-25-
移到5后:8-2-1-4-9-12-15-23-25-
移到4后:2-1-4-8-9-12-15-23-25-
移到2后:1-2-4-8-9-12-15-23-25-
判断次数=36
挪移次数=6
请按任意键继续. . .





欢迎光临 批处理之家 (http://bathome.net./) Powered by Discuz! 7.2