[问题求助] 请教PowerShell如何排列全部字符串组合(包括重复组合)？

bylove

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

想把一串字符串排列成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

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

效率应该不高，就用了一个递归，你可以在这个基础上优化速度

pd1

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

$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

回复 5# wanghan519


    谢谢,现在没时间测试,有个紧迫的新问题

bylove

回复 2# pd1


    牛逼,经过测试,你的代码速度最快

bylove

回复 5# wanghan519


    经过测试,你和2L代码都速度很快,谢谢,2L的要更快一些

bylove

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

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

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

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

如果能讲解一下原理和思路就好了,这个递归看不懂

pd1

回复 9# bylove


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

所以还是4楼的应该是快一点。
递归这个你可以百度一下看看原理，就是重复调用函数自己吧
4楼的是一个优化，叫动态规划。
都是网上搜来的，具体的我也没啥研究

wanghan519

又试了一下，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

试了一下官方的测试，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
复制代码