[新手上路]批处理新手入门导读[视频教程]批处理基础视频教程[视频教程]VBS基础视频教程[批处理精品]批处理版照片整理器
[批处理精品]纯批处理备份&还原驱动[批处理精品]CMD命令50条不能说的秘密[在线下载]第三方命令行工具[在线帮助]VBScript / JScript 在线参考
返回列表 发帖
回复 14# flashercs


    我明白了,性能差主要是函数调用次数太多,那种算法调用了7的阶乘次函数,而用循环来实现会快很多。我那个调用7次函数,所以快一些,但是应该可以只用循环实现的,就是三个嵌套循环。

TOP

本帖最后由 523066680 于 2017-4-8 13:20 编辑

C语言已忘光,代码毫无新意
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. void f(char *oldstr, char *newstr, int len, int lv)
  5. {
  6. char *ostr = (char *)malloc( len * sizeof(char) );
  7. for (int i = 0; i < len; i++)
  8. {
  9. strcpy( ostr, oldstr );
  10. newstr[lv] = ostr[i];
  11. newstr[lv+1] = '\0';
  12. if (len == 1)
  13. printf("%s \n", newstr);
  14. for (int j = i; j < (len-1); j++)
  15. ostr[j] = ostr[j+1];
  16. if ( len > 0 )
  17. f( ostr, newstr, len-1, lv+1 );
  18. }
  19. }
  20. int main(int argc, char *argv[])
  21. {
  22. char oldstr[] = "bathome";
  23. char *newstr = (char *)malloc( (strlen(oldstr)+1) * sizeof(char) );
  24. f(oldstr, newstr, strlen(oldstr), 0);
  25. return 0;
  26. }
复制代码
Perl (不借用外部模块)
  1. my @cup;
  2. my @nums;
  3. our $len;
  4. @nums = (split("", "bathome"));
  5. $len = $#nums+1;
  6. &func(\@cup, \@nums);
  7. sub func
  8. {
  9.     my ($a, $b) = (shift, shift);
  10.     my @ar;
  11.     my @br;
  12.    
  13.     print join(",", @{$a}),"\n" if ( scalar(@{$a}) == $len );
  14.     for my $i ( 0 .. $#{$b} )
  15.     {
  16.         @ar = (@{$a}, $b->[$i]);
  17.         @br = @{$b}[0..$i-1, $i+1..$#{$b}];
  18.         &func(\@ar, \@br);
  19.     }
  20. }
复制代码
以下拷贝自《High-Order Perl》
  1. sub permute
  2. {
  3. my @items = @{ $_[0] };
  4. my @perms = @{ $_[1] };
  5. unless (@items)
  6. {
  7. print join("", @perms) ,"\n";
  8. }
  9. else
  10. {
  11. my(@newitems,@newperms,$i);
  12. for $i (0 .. $#items)
  13. {
  14. @newitems = @items;
  15. @newperms = @perms;
  16. unshift(@newperms, splice(@newitems, $i, 1));
  17. permute([@newitems], [@newperms]);
  18. }
  19. }
  20. }
  21. # sample call:
  22. permute([qw(b a t h o m e)], []);
复制代码
《High-Order Perl》里面有更有趣的思路,午休,有空再更
1

评分人数

TOP

回复 16# flashercs

你的速度确实蛮快,但是那个批处理版就很慢了。

TOP

本帖最后由 523066680 于 2017-4-8 16:50 编辑

Here's a little program that generates all permutations of all the words
on each line of input. The algorithm embodied in the "permute()"
function is discussed in Volume 4 (still unpublished) of Knuth's *The
Art of Computer Programming* and will work on any list:
  1. #!/usr/bin/perl -n
  2. # Fischer-Krause ordered permutation generator
  3. sub permute (&@) {
  4.     my $code = shift;
  5.     my @idx = 0..$#_;
  6.     while ( $code->(@_[@idx]) ) {
  7.         my $p = $#idx;
  8.         --$p while $idx[$p-1] > $idx[$p];
  9.         my $q = $p or return;
  10.         push @idx, reverse splice @idx, $p;
  11.         ++$q while $idx[$p-1] > $idx[$q];
  12.         @idx[$p-1,$q]=@idx[$q,$p-1];
  13.     }
  14. }
  15. permute { print "@_\n" } split;
复制代码
来自 perldoc -q permute, 调用示例:echo a b c | permute.pl
刚开始真没看懂,蜜汁语法 ……
只看出来说是 knuth 在 计算机程序设计艺术 卷4 里面提到的算法,该书还未出版。

待会儿再更

TOP

8 楼置换算法的 JS 和 VBS 版

JS
  1. Z = "1;";
  2. for( j = 2; j <= 7; j++ ) {
  3.     t = Z;
  4.     Z = Z.replace(/;/g, j + ";")
  5.     for ( i = 1; i <= j - 1; i++ ) Z = Z + t.replace(RegExp(i, "g"), j).replace(/;/g, i + ";");
  6. }
  7. for( i = 1; i <= 7; i++ ) Z = Z.replace(RegExp(i, "g"), "bathome".substr(i - 1, 1));
  8. console.log(Z);
复制代码
VBS
  1. Z = "1;"
  2. For j = 2 To 7
  3.     t = Z
  4.     Z = Replace(Z, ";", j & ";")
  5.     For i = 1 To j - 1
  6.       Z = Z & Replace(Replace(t, i, j), ";", i & ";")
  7.     Next
  8. Next
  9. For i = 1 To 7
  10.     Z = Replace(Z, i, Mid("bathome", i, 1))
  11. Next
  12. WScript.Echo Z
复制代码
2

评分人数

    • flashercs: 批量替换速度最快,但是实用价值不佳,不是 ...技术 + 1
    • 老刘1号: 厉害,保存下慢慢学习!技术 + 1

TOP

http://www.cs.utsa.edu/~wagner/knuth/

Donald E. Knuth  
  The Art of Computer
Programming
Volume 4,
Combinatorial Algorithms
1

评分人数

TOP

本帖最后由 523066680 于 2017-4-8 20:28 编辑

解读和代码转C,主要是有一个数字调换的规律
  1. /* Translate by 523066680@163.com */
  2. #include <stdio.h>
  3. void splice_and_reverse( int *arr, int p, int ubound )
  4. {
  5. int t;
  6. for (int i = p; i <= (ubound+p)/2 ; i++ )
  7. {
  8. t = arr[i];
  9. arr[i] = arr[ubound - i + p];
  10. arr[ubound - i + p] = t;
  11. }
  12. }
  13. void exchange(int *arr, int a, int b)
  14. {
  15. int t;
  16. t = arr[a];
  17. arr[a] = arr[b];
  18. arr[b] = t;
  19. }
  20. void print_array(int *arr, int ubound)
  21. {
  22. for (int i = 0; i <= ubound; i++)
  23. printf("%d", arr[i]);
  24. printf("\n");
  25. }
  26. int main(int argc, char *argv[] )
  27. {
  28. int arr[] = {0, 1, 2, 3};
  29. int ubound = sizeof(arr) / sizeof(arr[0]) - 1;
  30. int p, q;
  31. while (1)
  32. {
  33. p = ubound;
  34. //p 递减,直到 当前元素 > 上一个元素 ,上一个元素记为 N
  35. while ( arr[p-1] > arr[p] ) p--;
  36. if ( p <= 0 ) break;
  37. q = p;
  38. //反转 从 p 至 末尾的元素
  39. splice_and_reverse( arr, p, ubound );
  40. //q 递增,直到当前元素 > N
  41. while ( arr[p-1] > arr[q] ) q++;
  42. //交换
  43. exchange(arr, p-1, q);
  44. //打印结果
  45.     print_array(arr, ubound);
  46. }
  47.     return 0;
  48. }
复制代码
有了这一个规则,我们可以 通过某个中间的排列得出下一个结果:

举一个 6 位的
arr[] = 5 3 4 2 1 0

  • init p = 5, 当 arr[p-1] > arr[p], p递减, p = 2; 记住 arr[p-1] = 3
  • 反转后面 2,3,4,5 位, arr[] = 5 3 0 1 2 4;
  • 之后的计算依据 5 3 0 1 2 4
  • init q = p = 2; 当 3 > arr[q], q递增, q = 5;
    5 3 0 1 2 4 调换 arr[1] arr[5] 得

arr[] = 5 4 0 1 2 3

TOP

  1. @echo off & setlocal enabledelayedexpansion
  2. set "str[0]= b a t h o m e"
  3. set tm1=%time%
  4. for %%a in (%str[0]%) do (
  5. set /a n+=1
  6. set /a odr[!n!]=n-1
  7. set var[!n!]=%%~a
  8. )
  9. ::FOR的嵌套递归,借鉴了http://bbs.bathome.net/viewthread.php?tid=1701&extra=&page=2中22楼CrLf的答案。
  10. for /l %%a in (1, 1, %n%) do if not "%%~a"=="%n%" (
  11. set "for=!for!for %%!var[%%~a]! in (^!str[!odr[%%~a]!]^!) do ( set "str[%%~a]=^^^!str[!odr[%%~a]!]: %%~!var[%%~a]!=^^^!" & "
  12. ) else (
  13. set "for=!for!for %%!var[%%~a]! in (^!str[!odr[%%~a]!]^!) do ( "
  14. )
  15. set "for=!for!echo;!str[0]: = %%~!"
  16. for /l %%a in (1, 1, %n%) do set "for=!for!) "
  17. %for%
  18. echo; 始于%tm1% ^
  19. 终于%time%
  20. pause
复制代码
2

评分人数

TOP

回复 10# codegay


    我可是在知乎给论坛打了广告哇 https://www.zhihu.com/question/57102581/answer/152543345

TOP

模式计算-迭代法

本帖最后由 523066680 于 2017-5-15 12:35 编辑

编辑/整理:523066680@163.com
日期:2017-05


      通过迭代方式获得排列的方案,参考自《Higher-Order Perl》

概念

      假设有4个元素: @arr = (a, b, c, d),下标为 0 1 2 3,每提取一个元素,
      数组重新定义,下标从0开始。排列和下标的提取关系:
      a b c d -> 0 0 0 0
      a b d b -> 0 0 1 0
      a c b d -> 0 1 0 0
      a c d b -> 0 1 1 0
      a d b c -> 0 2 0 0
      ...

      注意这里数字的变化和进制换算、递增非常相似,区别在于,每一位的进制是不同的:
      末位始终为0,
      倒数第二位最大为1(0,1),
      倒数第三位最大为2(0,1,2),
      倒数第四位最大为3(0,1,2,3)
      一共能产生 432*1 种模式(pattern) (刚好对应24种排列情况)

不同模式的生成和换算

      先设计一种换算函数,对于传入的任意数字,计算出对应的模式:

          my @elements = qw/a b c d/;   #元素
          my $seats = $#elements + 1;   #数量
          my @order = (0) x $seats;     #初始模板

          to_pattern(5, $seats, \@order);
          print join(",", @order);

          sub to_pattern                #转换器
          {
              my ($num, $seats, $o_ref) = @_;
              my $mod;

              for my $div ( 1 .. $seats )
              {
                  $mod = $num % $div;
                  $num = int($num / $div);
                  $o_ref->[-$div] = $mod;    #倒序填入
              }
          }

      输出: 0,2,1,0

将模式应用到排列顺序

      再写一个函数将 模式应用于顺序地提取数组元素

          my @elements = qw/a b c d/;
          my $seats = $#elements + 1;
          my @order = (0, 2, 1, 0);

          apply(\@elements, \@order);

          sub apply
          {
              my ($e_ref, $o_ref) = @_;
              my @temp = @$e_ref;
              my @final;

              for my $idx ( @$o_ref )
              {
                  push @final, splice( @temp, $idx, 1 );
              }

              print join(",", @final),"\n";
          }

      输出:a,d,c,b

      这样,不管想要哪一个序列,只要通过类似进制换算的方法算出模式,按模式提取即可

枚举所有情况的代码:

          use strict;
          my @elements = qw/a b c d e/;
          my $seats = $#elements + 1;
          my @order = (0) x $seats;

          for my $n ( 0 .. factorial($seats)-1 )
          {
              my @result;
              to_pattern($n, $seats, \@order);
              apply( \@elements, \@order, \@result );
              print join(",", @result), "\n";
          }

          sub to_pattern
          {
              my ($n, $seats, $o_ref ) = @_;
              my $mod;

              for my $div ( 1 .. $seats )
              {
                  $mod = $n % $div;
                  $n = int($n / $div);
                  $o_ref->[-$div] = $mod;    #从右边向左填入
              }
          }

          sub apply
          {
              my ($e_ref, $o_ref, $result) = @_;
              my @temp = @$e_ref;

              for my $idx ( @$o_ref )
              {
                  push @$result, splice( @temp, $idx, 1 );
              }
          }

          sub factorial
          {
              my $v = shift;
              return ($v > 1) ? $v*factorial($v-1) : 1;
          }

[Finished in 0.9s]
1

评分人数

TOP

回复 10# codegay


    何止是不错...我刷完贴只能灰溜溜逃了好吗

TOP

本帖最后由 523066680 于 2017-5-15 12:41 编辑

Perl 6 (这也太梦幻了)

      Works with: rakudo version 2014-1-24
      First, you can just use the built-in method on any list type.

          .say for <a b c>.permutations

      Output:
      a b c
      a c b
      b a c
      b c a
      c a b
      c b a


python

      Standard library function
      Works with: Python version 2.6+

          import itertools
          for values in itertools.permutations([1,2,3]):
              print (values)

Ruby (也是挺梦幻的)

          [1,2,3].permutation.to_a

[Finished in 0.2s]

TOP

填坑,汇编递归版
  1. Include masm32rt.inc
  2. .const
  3. CrLf db 0DH,0AH,0
  4. .data?
  5. Input db 20 dup (?)
  6. .code
  7. recursion Proc Uses Ebx Eax Ecx lpStr:dword
  8. Mov Ebx,lpStr
  9. .If Byte Ptr [Ebx+1] != NULL
  10. Mov Al,Byte Ptr [Ebx]
  11. Xor Ecx,Ecx
  12. .Repeat
  13. XChg Al,[Ebx+Ecx]
  14. Mov Byte Ptr [Ebx],Al
  15. Inc Ebx
  16. Invoke recursion,Ebx
  17. Dec Ebx
  18. XChg Al,[Ebx+Ecx]
  19. Mov Byte Ptr [Ebx],Al
  20. Inc Ecx
  21. .Until Byte Ptr [Ebx+Ecx] == NULL
  22. .Else
  23. Invoke StdOut,Offset Input
  24. Invoke StdOut,Offset CrLf
  25. .EndIf
  26. Ret
  27. recursion Endp
  28. Start:
  29. Invoke ArgClC,1,Offset Input
  30. Invoke recursion,Offset Input
  31. Invoke ExitProcess,NULL
  32. End Start
  33. End
复制代码
2

评分人数

    • happy886rr: 快两年了,激动。技术 + 1
    • 523066680: 每个字母都懂,组合起来就……系列技术 + 1

TOP

返回列表