Board logo

标题: [问题求助] 请教PowerShell如何排列全部字符串组合(包括重复组合)? [打印本页]

作者: bylove    时间: 2023-9-8 19:37     标题: 请教PowerShell如何排列全部字符串组合(包括重复组合)?

我这里有一个数据需要对接,代码写到一半就差这个功能需要实现了

想把一串字符串排列成N组,速度要快,因为量非常大,字符串的长度每次都不一样

比如指定一个字符串是123456789,限定条件是6位数
那么组合是:
1
2
3
4
5
6
12
21
13
31
123
321
122
133
211
233
221
331
112
113
1234
4321
...
...
123456
..
..
其实就是排列他们全部的组合,包括重复的组合比如字符串是123456
最后6位数的时候可能还会出现一次
111111
222222
333333
...
...
666666
这种情况
指定的字符串希望可以由我自己决定,以及指定排列的位数

比如可能指定一个字符串: abcdef123456 然后位数是6
再或者字符串: abc,位数是3
如果指定的字符串长度低于指定的位数比如字符串为abc,位数为6
那么组合为
a
b
c
ab
bc
ac
abca
abcb
abcc
aaabbb
aaaccc
abcabc
aaaaaa
bbbbbb
cccccc
bacbac
cabcab
对于字符串低于指定的6位数,那么就在右侧继续填充,直到6位数全部组合跑完,就算处理完成

再此非常感谢,感谢感谢!
作者: pd1    时间: 2023-9-9 00:40

  1. function f($str,$n){if($n -eq 1){foreach($i in $str){$i}}else{foreach($j in (f -str $str -n ($n-1))){foreach($k in $str){$j+$k}}}}
  2. $str="123abc".TocharArray()
  3. $n=6
  4. 1..$n|%{f -str $str -n $_}>111.txt
复制代码

作者: pd1    时间: 2023-9-9 00:44

效率应该不高,就用了一个递归,你可以在这个基础上优化速度
作者: pd1    时间: 2023-9-9 01:46

本帖最后由 pd1 于 2023-9-9 02:02 编辑
  1. function f($str,$n)
  2. {
  3. [System.Collections.ArrayList]$a=@()
  4. [System.Collections.ArrayList]$b=@()
  5. if($n -eq 1)
  6. {
  7. foreach($i in $str)
  8. {
  9. $c=$a.Add($i)
  10. }
  11. $c=$b.Add($a)
  12. return $b
  13. }
  14. else
  15. {
  16. $c=$b.Add($str)
  17. for($m=0;$m -lt $n-1;$m++)
  18. {
  19. foreach($j in $b[$m])
  20. {
  21. foreach($k in $str)
  22. {
  23. $c=$a.Add($j+$k)
  24. }
  25. }
  26. $c=$b.Add($a)
  27. $a=@()
  28. }
  29. return $b
  30. }
  31. }
  32. $str="abc123".TocharArray()
  33. $n=1
  34. (f -str $str -n $n)>result.txt
复制代码

作者: wanghan519    时间: 2023-9-9 10:26

  1. $a = [System.Collections.Stack]::new()
  2. function cr($n, $s, $a) {if($a.count -eq $n){return $a.toarray() -join ''}for($i=0;$i -lt $s.length;$i++){$a.push($s[$i]);cr $n $s $a;$a.pop()|out-null}}
  3. 1..3 | %{$a.clear();cr $_ "asdfg" $a}
复制代码

作者: bylove    时间: 2023-9-10 20:59

回复 5# wanghan519


    谢谢,现在没时间测试,有个紧迫的新问题
作者: bylove    时间: 2023-9-10 21:11

回复 2# pd1


    牛逼,经过测试,你的代码速度最快
作者: bylove    时间: 2023-9-10 21:12

回复 5# wanghan519


    经过测试,你和2L代码都速度很快,谢谢,2L的要更快一些
作者: bylove    时间: 2023-9-10 21:16

本帖最后由 bylove 于 2023-9-10 21:22 编辑

经过测试2L与5L代码速度都很快,谢谢

实验了一下数据:
字符串:1234567890
位数为:3

2L速度:0.83s
5L速度1.05s

这还是只是简单的测试,实际字符串和位数会很复杂.量很多,谢谢了

如果能讲解一下原理和思路就好了,这个递归看不懂
作者: pd1    时间: 2023-9-11 01:36

回复 9# bylove


    生成3位数量太少了,比较难比较速度,把位数改多点试试
比如 1234567890生成5位   分别耗时  2.674s   1.062s    11.57s
比如 1234567890生成6位   分别耗时  25.77s    9.59s      120.19s

所以还是4楼的应该是快一点。
递归这个你可以百度一下看看原理,就是重复调用函数自己吧
4楼的是一个优化,叫动态规划。
都是网上搜来的,具体的我也没啥研究
作者: wanghan519    时间: 2023-9-11 05:59

本帖最后由 wanghan519 于 2023-9-11 06:21 编辑

又试了一下,5楼因为递归次数较多就很慢,动态规划是算法上空间换时间的优化,确实快!
试了栈改成字符串操作并不改变速度,倒是因为把递归里的一层for循环展开导致递归次数变多,浪费的时间更多,结合官方文档说调用函数的成本高昂,调用函数是直接for循环耗时的20倍以上,所以暂时结论是powershell不适合写递归。。。
5楼的算法,用awk运行需要4秒(0-9选6个以内),而python里用itertools.product(s, repeat=n)只需要1秒多。。。
  1. function combr(n, s, i) {
  2.     if (length(s)==n) {
  3.         print s
  4.         return
  5.     }
  6.     for (i=1;i<=length($0);i++) {
  7.         s = s substr($0, i, 1)
  8.         combr(n, s)
  9.         s = substr(s, 1, length(s) - 1)
  10.     }
  11. }
复制代码

作者: wanghan519    时间: 2023-9-11 07:56

试了一下官方的测试,powershell里调用函数的开销似乎格外大,所以暂时认为powershell不适合写递归吧。。。
要么4楼那样优化算法,要么用别的语言写递归
  1. $ranGen = New-Object System.Random
  2. $RepeatCount = 10000
  3. 'Wrapped in a function = {0}ms' -f (Measure-Command -Expression {
  4.     function Get-RandNum_Core {
  5.         param ($ranGen)
  6.         $ranGen.Next()
  7.     }
  8.     for ($i = 0; $i -lt $RepeatCount; $i++) {
  9.         $Null = Get-RandNum_Core $ranGen
  10.     }
  11. }).TotalMilliseconds
  12. 'For-loop in a function = {0}ms' -f (Measure-Command -Expression {
  13.     function Get-RandNum_All {
  14.         param ($ranGen)
  15.         for ($i = 0; $i -lt $RepeatCount; $i++) {
  16.             $Null = $ranGen.Next()
  17.         }
  18.     }
  19.     Get-RandNum_All $ranGen
  20. }).TotalMilliseconds
复制代码





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