pusofalse 发表于 2010-8-21 17:47:20

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

输入任意字符串，枚举出任意字符的所有组合。例如：
输入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 发表于 2010-8-21 21:30:43

#include <Array.au3>
Dim $aArray =
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)

水木子 发表于 2010-8-21 21:40:53

本帖最后由 水木子 于 2010-8-21 21:43 编辑

回复 2# 3mile

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

3mile 发表于 2010-8-21 21:43:05

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

水木子 发表于 2010-8-21 21:52:48

本帖最后由 水木子 于 2010-8-21 21:59 编辑

回复 4# 3mile

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

xsjtxy 发表于 2010-8-21 21:53:00

我发现的问题的再大的屏幕也显示不完。{:face (356):}

3mile 发表于 2010-8-21 22:08:29

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

pusofalse 发表于 2010-8-21 22:08:52

回复 2# 3mile


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

3mile 发表于 2010-8-21 22:09:46

回复 8# pusofalse
P大过奖了。

minterz 发表于 2010-8-22 00:00:14

高明。。。

水木子 发表于 2010-8-22 09:48:53

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

非常棒！！！

rolaka 发表于 2010-8-22 11:34:43

本帖最后由 rolaka 于 2010-8-22 16:34 编辑



$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 发表于 2010-8-22 18:01:44

回复 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 发表于 2010-8-22 22:48:54

只有学习的份…

水木子 发表于 2010-8-22 23:32:41

回复 14# afan

前辈谦虚了！咱们论坛谁不知道解前辈的实力啊！
只是前辈最近在折腾别的吧？
   
早点休息，注意身体，晚安！{:1_548:}
页: [1] 2
查看完整版本: 枚举字符串中的所有字符组合