sex123 发表于 2015-2-15 19:39:25

求一个排列组合算法的问题解决方案

猜一个单词 单词中间没有空格,不区分大小写 由a-z字母组成。单词长度不固定,有可能在4到20个之间左右的一个单词。
机器人知道单词的拼写,用户只能问字母在单词中是否存在,每问一次,机器人回答,是的,存在这个字母或者字母组合,或者回答,不存在这种字母或字母组合。用户每问一次,机器人休息一分钟,不回答问题。
问题来了,怎么算法比较快捷准确?


下面是例子,
机器人存储的单词是 saloon
用户只知道这个单词是由abcd....xyz组成,可以重复使用无数次。
问机器人有没有a 机器人回答有 a 休息一分钟, 问机器人有没有b 机器人回答 没有b 再呆一分钟,问机器人,有没有on,回答 有on 呆一分钟,问有没有 xy,回答没有 ...问有没有 saloon 回答 有,注意到这没有停止,需要继续问 有没有saloona 回答没有 ,休一分种,有没有saloonz 答约没有,全部试完后,得到答案saloon。

怎么算比较好呢?

netegg 发表于 2015-2-15 21:39:00

没算法,26^n(单词字母个数)

sex123 发表于 2015-2-15 22:52:15

没算法,26^n(单词字母个数)
netegg 发表于 2015-2-15 21:39 http://www.autoitx.com/images/common/back.gif


    不对
按我这样算,先算一维有a l o s n 五个字母,现一维两两组合。 得 aaal ao as an la la ll lo ls ln ....等等,再得二维,关键二维到三维难算。。。

netegg 发表于 2015-2-16 09:39:02

本帖最后由 netegg 于 2015-2-16 09:43 编辑

那你先要给定a后面跟什么是可以存在的,然后根据前两位的组合分析后面的第三位,以此类推,也就是说当第一个字符是a的时候,你要分析第二个a-z哪个有可能是对的,然后输入第二个是a要分析aaa-aaz哪个是对的。。。。类推,说白了还是枚举,当然我知道不是26^n,那是最极端的情况,总共英语单词也就三万多个

你所说的是你已经知道结果的情况,并不是程序判断出结果的情况

sex123 发表于 2015-2-16 12:38:58

那你先要给定a后面跟什么是可以存在的,然后根据前两位的组合分析后面的第三位,以此类推,也就是说当第一个 ...
netegg 发表于 2015-2-16 09:39 http://www.autoitx.com/images/common/back.gif


    恩,这回你说的对,关键是我不会写这种算法。程序代码不会写。应该是找到一维到,推二维,再从二维中找首尾相同的一位字母,推三维,再从三维中找首尾相同的二个位母推四维,再从四维中找首尾相同的三位字母推五维。就是代码不会写。

netegg 发表于 2015-2-16 13:27:14

回复 5# sex123

这不是会不会的问题,太容易,不多判断对错就达不到了

netegg 发表于 2015-2-16 13:28:51

另外一点是比对电脑里存储的吗

netegg 发表于 2015-2-16 13:32:56

换个方式说,电脑里存的是uvwxyz,是要匹配出这个字符串还是什么

netegg 发表于 2015-2-16 13:34:05

对了这不是排列组合,纯粹枚举

sex123 发表于 2015-2-16 19:00:36

换个方式说,电脑里存的是uvwxyz,是要匹配出这个字符串还是什么
netegg 发表于 2015-2-16 13:32 http://www.autoitx.com/images/common/back.gif


    恩,可以理解为电脑里存的字符串,比如在autoit里面先设置一个变量 $x="uvwxyz" 之后,我们假设不知道这个变量的内容是什么,之后通过程序枚举来推出这个变量值。

netegg 发表于 2015-2-16 23:49:11

#AutoIt3Wrapper_au3check_Parameters=-d -w 1 -w 2 -w 3 -w 4 -w 5 -w 6
#include <GuiEdit.au3>
#include <WinAPI.au3> ; used for Lo/Hi word
#include <WindowsConstants.au3>
#include <GuiConstantsEx.au3>

Opt('MustDeclareVars', 1)

Global $Debug_Ed = False ; Check ClassName being passed to Edit functions, set to True and use a handle to another control to see it work

Global $hEdit,$iMemo, $num=1, $string='uvwxyz'

_Example1()

Func _Example1()
Local $hGUI

; 创建界面
$hGUI = GUICreate("Edit Create", 400, 532)
$hEdit = _GUICtrlEdit_Create($hGUI, "", 2, 2, 394, 268)
$iMemo = GUICtrlCreateEdit("", 2, 272, 394, 258, BitOR($WS_VSCROLL, $ES_AUTOVSCROLL, $ES_READONLY))
GUISetState()

GUIRegisterMsg($WM_COMMAND, "WM_COMMAND")


; 循环至用户退出
Do
Until GUIGetMsg() = $GUI_EVENT_CLOSE
GUIDelete()
EndFunc   ;==>_Example1

Func WM_COMMAND($hWnd, $iMsg, $iwParam, $ilParam)
#forceref $hWnd, $iMsg
Local $hWndFrom, $iCode, $hWndEdit;$iIDFrom,
If Not IsHWnd($hEdit) Then $hWndEdit = GUICtrlGetHandle($hEdit)
$hWndFrom = $ilParam
;$iIDFrom = _WinAPI_LoWord($iwParam)
$iCode = _WinAPI_HiWord($iwParam)
Switch $hWndFrom
    Case $hEdit, $hWndEdit
      Switch $iCode
      Case $EN_CHANGE ; 改变控件中的文本时发送
          If Not (StringRight(_GUICtrlEdit_GetText($hEdit), 1) = StringMid($string, $num ,1)) Then
                          memowrite('第'& $num & '个字符出错')
               EndIf
                          
                          $num += 1
          ; 无返回值
      EndSwitch
EndSwitch
Return $GUI_RUNDEFMSG
EndFunc   ;==>WM_COMMAND

Func memowrite($s_text)
GUICtrlSetData($iMemo, $s_text & @CRLF, 1)
EndFunc   ;==>memowrite

sex123 发表于 2015-2-17 01:35:45


netegg 发表于 2015-2-16 23:49 http://www.autoitx.com/images/common/back.gif


    估计是我没说明白怎么回事,但我要说的不是你写的这种。

netegg 发表于 2015-2-17 02:40:04

本帖最后由 netegg 于 2015-2-17 02:45 编辑

回复 12# sex123
你把要的东西用结果表示出来,你的文字表达实在没法恭维
就你说的那个a l o s n,最后要的结果是什么
你的结果按你说的,不应该有俩个la la

netegg 发表于 2015-2-17 03:17:06

#include <Array.au3>

Dim $aArray = ['a', 'l', 'o', 's', 'm'], $aArrayCombo

For $i = 1 To UBound($aArray)
        $aArrayCombo1 = _ArrayCombinations($aArray, $i, "")
        _ArrayDelete($aArrayCombo1,0)
        _ArrayConcatenate($aArrayCombo, $aArrayCombo1)
        ReDim$aArrayCombo
;        $aArrayCombo = $aArrayCombo1
Next
        _ArrayDelete($aArrayCombo,0)
        _ArrayDisplay($aArrayCombo, "iSet = " & $i)

难道是这样?

netegg 发表于 2015-2-17 06:40:29

本帖最后由 netegg 于 2015-2-17 06:49 编辑

#include <Array.au3>
#include <String.au3>
Global $ret = ''
Global $str = '12345'
$aA = StringSplit($str, '', 2)
$aA1 = StringSplit(StringTrimLeft($str, 1), '', 2)
$aA2 = StringSplit(StringTrimLeft($str, 2), '', 2)
$aA3 = StringSplit(StringTrimLeft($str, 3), '', 2)
$aA4 = StringSplit(StringTrimLeft($str, 4), '', 2)
For $i= 1 To 5
        $ret &= $i & ','
        For $j= $i+1 To 5
                $ret &= $i & $j & ','
                For $w = $j+1 To 5
                        $ret &= $i & $j & $w & ','
                        For $m= $w+1 To 5
                                $ret &= $i & $j & $w & $m & ','
                                For $n = $m+1 To 5
                                        $ret &= $i & $j & $w & $m & $n & ','
                                Next
                        Next
                Next
        Next
Next

$aRet = StringSplit(StringTrimRight($ret, 1), ',', 2)
$ret = ''
$ret1 = ''
$ret2 = ''
For $w In $aRet
        $w = StringFormat('%06s', $w)
        $ret &= $w & ','
next
$aRet1 = StringSplit(StringTrimRight($ret, 1), ',', 2)
_Arraysort($aRet1)
Dim $str= ['a','l','o','s','m']
Dim $aNumer
For $v In $aRet1
        $v = Number($v)
        If StringLen($v) >1 Then
          $ret2 = ''
           $aNumber = StringSplit($v, '',2)
          For $u In $aNumber
                  $ret2 &= $str[$u-1]
          next
    Else
          $ret2 = $str[$v-1]
        endif
        $ret1 &= $ret2 & ','
next
$aRet2 = StringSplit(StringTrimRight($ret1, 1), ',', 2)
_arraydisplay($aRet2)
不知道对不对,到底有没有顺序问题,这个不包含重复值,比如aa,aal。。。。之类的
页: [1] 2
查看完整版本: 求一个排列组合算法的问题解决方案