枚举字符串中的所有字符组合

pusofalse

输入任意字符串，枚举出任意字符的所有组合。例如：
输入123，输出

1
2
3
1 2
2 3 
1 3
1 2 3

输入abcd，输出

a 
b 
a b 
c 
a c 
b c 
a b c 
d 
a d 
b d 
a b d 
c d 
a c d 
b c d 
a b c d 

不必注意输出的顺序，只要能将所有组合正确输出就可以了。

效率：
对于10位长度以内的数据，效率<=100ms。
对于15位长度以内的数据，效率<=5s。

3mile

#include <Array.au3>
Dim $aArray[10] = [1, 2, 3, 4, 5,6,7,8,9,0]
Local $str
Local $time=TimerInit()
For $i = 1 To UBound($aArray)
        $aArrayCombo = _ArrayCombinations($aArray, $i, ",")
        ;_ArrayDisplay($aArrayCombo, "iSet = " & $i)
        For $n=1 To UBound($aArrayCombo)-1
                ConsoleWrite($aArrayCombo[$n]&@CRLF)
                $str&=$aArrayCombo[$n]&@CRLF
        Next
Next
MsgBox(0,TimerDiff($time),$str)

水木子

回复 2# 3mile

测试过吗？我这里运行数组超出界限。

3mile

回复 3# 水木子
我这里没有问题啊。

水木子

回复 4# 3mile

我直接复制你的代码测试，结果还是数组超出界限，难道是我的AU3有问题？

xsjtxy

我发现的问题的再大的屏幕也显示不完。

3mile

回复 6# xsjtxy
呵呵，所以加了个ConsoleWrite($aArrayCombo[$n]&@CRLF)这句。
到控制台查看结果吧。

pusofalse

回复 2# 3mile


    高，学习了！~ 没注意到_ArrayCombinations函数，现在看下算法是怎样的~

3mile

回复 8# pusofalse
P大过奖了。

minterz

高明。。。

水木子

回复 4# 3mile
经证实，确实是我的Au3出问题了，你代码运行一切正常。

非常棒！！！

rolaka

$input = InputBox("枚举", "输入元素")

$time = TimerInit()

$array = StringSplit($input, "", 2)

For $i = 1 To (2^UBound($array))-1
        $out = ""
        For $n = 0 To UBound($array)-1
                If BitAND(BitShift($i, $n), 1) == 1 Then
                        $out &= $array[$n]
                EndIf
        Next
        ConsoleWrite("out: " & $out & @CRLF)
Next

MsgBox(0, "End", TimerDiff($time))

我想得起来的最快方法...与非门的内容还没忘记...
好像比_ArrayCombinations要慢几ms...不知道是不是StringSplit的原因

15位元素
2785ms 其中拼合字符串花了600ms左右...


版本2:

好像是这样的...是节省一半的时间...但实际花的时间...orz

$input = InputBox("枚举", "输入元素")

$time = TimerInit()

$array = StringSplit($input, "", 2)

$i = 0

For $i = 1 To ((2 ^ UBound($array)) / 2) - 1
        $out = ""
        $out2 = ""
        For $n = 0 To UBound($array) - 1
                If BitAND(BitShift($i, $n), 1) == 1 Then
                        $out &= $array[$n]
                Else
                        $out2 &= $array[$n]
                EndIf
        Next
        ConsoleWrite("" & $out & @CRLF)
        ConsoleWrite("" & $out2 & @CRLF)
Next

$out = ""

For $n = 0 To UBound($array) - 1
        $out &= $array[$n]
Next

ConsoleWrite("" & $out & @CRLF)

MsgBox(0, "End", TimerDiff($time))

15个元素
平均1600ms朝上...


好像是str和int的问题...orz

pusofalse

回复 12# rolaka


我们的代码如此相似，简直一模一样，同是用了位运算。
rolaka兄的第2种方法高明至极，只有学习了~
以下是我的代码：

#include <array.au3>

Local $sVar = "1234567890", $aVar = StringSplit($sVar, "", 2)
Local $sRow, $sResult, $iUBound, $iTimer = TimerInit()

$iUBound = UBound($aVar)
For $i = 1 To BitShift(1, -$iUBound) - 1
        $sRow = ""
        For $j = 0 To $iUBound - 1
                If BitAnd($i, BitShift(1, -$j)) Then
                        $sRow &= $aVar[$j]
                EndIf
        Next
        $sResult &= $sRow & @CR
Next
$sResult = StringSplit(StringTrimRight($sResult, 1), @CR)
_Arraydisplay($sResult, TimerDiff($iTimer)) 

afan

只有学习的份…

水木子

回复 14# afan

前辈谦虚了！咱们论坛谁不知道解前辈的实力啊！
只是前辈最近在折腾别的吧？
   
早点休息，注意身体，晚安！