标题: [问题求助] 请教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
- 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}}}}
- $str="123abc".TocharArray()
- $n=6
- 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 编辑
- function f($str,$n)
- {
- [System.Collections.ArrayList]$a=@()
- [System.Collections.ArrayList]$b=@()
- if($n -eq 1)
- {
- foreach($i in $str)
- {
- $c=$a.Add($i)
- }
- $c=$b.Add($a)
- return $b
- }
- else
- {
- $c=$b.Add($str)
- for($m=0;$m -lt $n-1;$m++)
- {
- foreach($j in $b[$m])
- {
- foreach($k in $str)
- {
- $c=$a.Add($j+$k)
- }
- }
- $c=$b.Add($a)
- $a=@()
- }
- return $b
- }
- }
- $str="abc123".TocharArray()
- $n=1
- (f -str $str -n $n)>result.txt
复制代码
作者: wanghan519 时间: 2023-9-9 10:26
- $a = [System.Collections.Stack]::new()
- 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}}
- 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秒多。。。- function combr(n, s, i) {
- if (length(s)==n) {
- print s
- return
- }
- for (i=1;i<=length($0);i++) {
- s = s substr($0, i, 1)
- combr(n, s)
- s = substr(s, 1, length(s) - 1)
- }
- }
复制代码
作者: wanghan519 时间: 2023-9-11 07:56
试了一下官方的测试,powershell里调用函数的开销似乎格外大,所以暂时认为powershell不适合写递归吧。。。
要么4楼那样优化算法,要么用别的语言写递归- $ranGen = New-Object System.Random
- $RepeatCount = 10000
-
- 'Wrapped in a function = {0}ms' -f (Measure-Command -Expression {
- function Get-RandNum_Core {
- param ($ranGen)
- $ranGen.Next()
- }
-
- for ($i = 0; $i -lt $RepeatCount; $i++) {
- $Null = Get-RandNum_Core $ranGen
- }
- }).TotalMilliseconds
-
- 'For-loop in a function = {0}ms' -f (Measure-Command -Expression {
- function Get-RandNum_All {
- param ($ranGen)
- for ($i = 0; $i -lt $RepeatCount; $i++) {
- $Null = $ranGen.Next()
- }
- }
-
- Get-RandNum_All $ranGen
- }).TotalMilliseconds
复制代码
欢迎光临 批处理之家 (http://bbs.bathome.net/) |
Powered by Discuz! 7.2 |