Board logo

标题: [文本处理] 【已解决】BAT或VBS:如何寻找最少共有数 [打印本页]

作者: 思想之翼    时间: 2015-1-29 22:58     标题: 【已解决】BAT或VBS:如何寻找最少共有数

本帖最后由 思想之翼 于 2015-2-2 20:42 编辑

文本内有如下100行数据,如果在下列每行数据内任意抽取若干数据,组成一组数据,满足每行数据在这组数据内,至少有1个,并使这样的数据组合个数最少(即:寻找最少共有数),BAT或VBS代码可以实现吗?
12 16 26
12 17 27
12 18 28
12 19 29
12 10 20
13 16 36
13 17 37
13 18 38
13 19 39
13 10 30
14 16 46
14 17 47
14 18 48
14 19 49
14 10 40
15 16 56
15 17 57
15 18 58
15 19 59
15 10 50
16 17 67
16 18 68
16 19 69
16 10 60
17 18 78
17 19 79
17 10 70
18 19 89
18 10 80
19 10 90
23 26 36
23 27 37
23 28 38
23 29 39
23 20 30
24 26 46
24 27 47
24 28 48
24 29 49
24 20 40
25 26 56
25 27 57
25 28 58
25 29 59
25 20 50
26 27 67
26 28 68
26 29 69
26 20 60
27 28 78
27 29 79
27 20 70
28 29 89
28 20 80
29 20 90
34 36 46
34 37 47
34 38 48
34 39 49
34 30 40
35 36 56
35 37 57
35 38 58
35 39 59
35 30 50
36 37 67
36 38 68
36 39 69
36 30 60
37 38 78
37 39 79
37 30 70
38 39 89
38 30 80
39 30 90
45 46 56
45 47 57
45 48 58
45 49 59
45 40 50
46 47 67
46 48 68
46 49 69
46 40 60
47 48 78
47 49 79
47 40 70
48 49 89
48 40 80
49 40 90
56 57 67
56 58 68
56 59 69
56 50 60
57 58 78
57 59 79
57 50 70
58 59 89
58 50 80
59 50 90
作者: terse    时间: 2015-1-29 23:42

应该可以的 只是没看懂
作者: 思想之翼    时间: 2015-1-30 00:03

本帖最后由 思想之翼 于 2015-1-30 01:14 编辑

回复 2# terse
意思是:从10 12 13 14 15 16 17 18 19 20 23 24 25 26 27 28 29 30 34 35 36 37 38 39 40 45 46 47 48 49 50 56 57 58 59 60 67 68 69 70 78 79 80 89 90这45个数据中抽取若干数据,作为一个数据组合,使上述100行数据的每行数据,都能在这个数据组合里找到1个、2个或3个相同的数据,满足这样条件的数据组合有很多,现在需要找到数据量最少的那个数据组合。
比如:上述45个数据作为一个数据组合,每行数据都能在该数据组合里找到3个相同的数据。现在欲在这个数据组合里尽量删减更多数据,使上述100行数据的每行数据,在删减后的数据组合里,最少能找到1个相同数据,即满足条件。
作者: terse    时间: 2015-1-30 01:39

回复  terse
意思是:从10 12 13 14 15 16 17 18 19 20 23 24 25 26 27 28 29 30 34 35 36 37 38 39 40 4 ...
思想之翼 发表于 2015-1-30 00:03

先给个思路 出现次数最多的开始提取 一直至每行都出现过都提取 退出
作者: CrLf    时间: 2015-1-30 02:45

每个字都认得,组合起来就看不懂了...
作者: xxpinqz    时间: 2015-1-30 08:10

相互理解是个难题啊。。。。
貌似3楼给出的45组数据就是最少组合了吧?
作者: terse    时间: 2015-1-30 14:58

处理10-99数字 其他情况(如同行重复数据)没考虑
  1. @echo off&setlocal enabledelayedexpansion
  2. for /f "delims=" %%i in (a.txt) do (
  3.     set /a n+=1
  4.     for %%i in (%%i) do (
  5.         set/a _%%i+=1
  6.         for %%j in (!_%%i!) do set $%%j=!$%%j! %%i
  7.         set len%%i=!n! !len%%i!
  8.    )
  9. )
  10. for /l %%i in (10 1 99) do (
  11.     if defined $!_%%i! (
  12.        for %%j in (!_%%i!) do (
  13.            set #%%j=!$%%j!
  14.            set "str=!str! %%j"
  15.            set "$%%j="
  16.        )
  17.     )
  18. )
  19. for /f %%i in ('(for %%i in (!str!^) do @echo;%%i^)^|sort') do (
  20.     set ar=%%i !ar!
  21. )
  22. for  %%i in (!ar!) do (
  23.      for %%j in (!#%%i!) do (
  24.          if defined len%%j (
  25.             set flag=
  26.             for %%k in (!len%%j!) do (
  27.                 if not defined f%%k (
  28.                    set flag=1
  29.                    set f%%k=1
  30.                 )
  31.             )
  32.             if defined flag set arr=!arr! %%j
  33.             set len%%j=
  34.         )
  35.     )
  36. )
  37. echo!arr!
  38. pause
复制代码

作者: 思想之翼    时间: 2015-1-30 15:50

本帖最后由 思想之翼 于 2015-1-30 16:49 编辑

回复 7# terse

感谢帮助。
运行您的代码,提取到如下数据组合:
16 17 18 19 10 26 27 28 29 20 36 37 38 39 30 46 47 48 49 40 56 57 58 59(24个)
这还不是最少共有数。
我手工处理了一下,暂时得到如下满足题意的数据组合:
20 40 60 80 13 15 17 19 24 26 28 35 37 39 46 48 57 59 68 79(20个)
还有没其他的数据组合,既满足题意,数据个数又更少?
作者: Spring    时间: 2015-1-30 15:51

以前好像也看到过你发的帖子,总觉得语言语文是美术老师教的,
就说一下按照理解想的步骤吧,先把所有的数列出来,然后找到一个出现的行数最多的一个,取出这个数字的同时把相关的那些行都排除,继续重复直到把所有行都排除掉
  1. fn = "numbers.txt"
  2. Set data = ReadNumbers(fn)
  3. Do While data.Count > 0
  4.     x = FetchOneNumber(data)
  5.     WScript.Echo x
  6. Loop
  7. Function ReadNumbers(filespec)
  8.     Dim objData, objFso, objFile, arrLine
  9.     Set objData = WScript.CreateObject("Scripting.Dictionary")
  10.     Set objFso = WScript.CreateObject("Scripting.FileSystemObject")
  11.     Set objFile = objFso.OpenTextFile(filespec, 1)
  12.     Do While Not objFile.AtEndOfStream
  13.         objData.Add objFile.Line, Split(objFile.ReadLine())
  14.     Loop
  15.     Set ReadNumbers = objData
  16. End Function
  17. Function FetchOneNumber(objDictionary)
  18.     Dim objNum, objLine, lines, l, nums, n, i, j, theOne, theFreq
  19.     Set objNum = WScript.CreateObject("Scripting.Dictionary")
  20.     ' 将数据转换成 key:NUMBER/value:LINE 格式
  21.     lines = objDictionary.Keys
  22.     For i = 0 To UBound(lines)
  23.         l = lines(i)
  24.         nums = objDictionary.Item(l)
  25.         For j = 0 To UBound(nums)
  26.             n = nums(j)
  27.             If Not objNum.Exists(n) Then
  28.                 Set objLine = WScript.CreateObject("Scripting.Dictionary")
  29.                 objNum.Add n, objLine
  30.             End If
  31.             objNum.Item(n).Add l, 1
  32.         Next
  33.     Next
  34.     ' 找到出现频率最高的数字
  35.     theOne = -1
  36.     theFreq = 0
  37.     nums = objNum.Keys
  38.     For i = 0 To UBound(nums)
  39.         n = nums(i)
  40.         Set objLine = objNum.Item(n)
  41.         If objLine.Count > theFreq Then
  42.             theOne = n
  43.             theFreq = objLine.Count
  44.         End If
  45.     Next
  46.     ' 剔除已使用的行
  47.     Set objLine = objNum.Item(theOne)
  48.     lines = objLine.Keys
  49.     Dim strMsg
  50.     strMsg = "数字 " & theOne & " 出现 " & objLine.Count & " 次,位于第 "
  51.     For j = 0 To UBound(lines)
  52.         strMsg = strMsg & " " & lines(j)
  53.         objDictionary.Remove lines(j)
  54.     Next
  55.     strMsg = strMsg & " 行;"
  56.     ' WScript.StdOut.WriteLine strMsg
  57.     ' 设置返回值
  58.     FetchOneNumber = theOne
  59. End Function
复制代码

作者: 思想之翼    时间: 2015-1-30 16:01

回复 9# Spring
感谢帮助。
您的代码运行后,输出的文本为空。
作者: terse    时间: 2015-1-30 19:15

回复 10# 思想之翼
应该还是算法错误
先用VBS处理了
作者: terse    时间: 2015-1-31 11:25

回复 10# 思想之翼
每次提一个最多行 然后排除掉
貌似还不是最优结果啊 郁闷
问题出在哪里呢?
  1. @echo off
  2. copy a.txt "%temp%\$"  >nul
  3. :start
  4. setlocal enabledelayedexpansion
  5. for /f "usebackqdelims=" %%i in ("%temp%\$") do (
  6.     for %%i in (%%i) do (
  7.         set/a _%%i+=1
  8.         if !n! lss !_%%i! (
  9.            set n=!_%%i!
  10.            set $!n!=%%i
  11.         )
  12.    )
  13. )
  14. if "!$%n%!" neq "" (
  15.    for /f "tokens=1*" %%a in ("!$%n%! !arr!") do (
  16.        endlocal
  17.        set arr=%%a %%b
  18.        >"%temp%\#" findstr /v "%%a" "%temp%\$"
  19.        move "%temp%\#" "%temp%\$" >nul
  20.        goto :start
  21.    )
  22. )
  23. echo %arr%
  24. pause
复制代码

作者: xxpinqz    时间: 2015-1-31 12:54

可能这题的答案不是唯一的,你给出的:
  1. 20 40 60 80 13 15 17 19 24 26 28 35 37 39 46 48 57 59 68 79
复制代码
和9楼给出的:
  1. 16 27 38 49 50 18 29 37 40 56 10 39 47 26 58 15 79 20 48 36
复制代码
都是20组数据,也都能满足满足每行数据在这组数据内,至少有1个的要求。
作者: CrLf    时间: 2015-1-31 13:10

想了两个思路,都不能保证得到最优解,难道一定要用暴力手段
作者: terse    时间: 2015-2-1 12:45

貌似提取到最少项
怎么验证呢
不知道是否还要判断子项
  1. @echo off
  2. copy a.txt "%temp%\$"  >nul
  3. :start
  4. setlocal enabledelayedexpansion
  5. for /f "usebackqdelims=" %%i in ("%temp%\$") do (
  6.     set /a len+=1
  7.     for %%j in (%%i) do (
  8.         set/a _%%j+=1
  9.         set len%%j=!len%%j! !len!
  10.         if !n! lss !_%%j! (
  11.            set n=!_%%j!
  12.            set t=%%j
  13.            set num=%%j
  14.         ) else if !n! equ !_%%j! set t=!t! %%j
  15.         )
  16.     )
  17. )
  18. if "!t!" neq "!num!" (
  19.    for %%i in (!t!) do (
  20.        for %%j in (!len%%i!) do (
  21.            set /a $%%j+=1
  22.            set #%%i=!#%%i!+$%%j
  23.        )
  24.    )
  25.    set n=999
  26.    for %%i in (!t!) do (
  27.        set /am=!#%%i!
  28.        if !n! gtr !m! (
  29.           set n=!m!
  30.           set num=%%i
  31.        )
  32.    )
  33. )
  34. if "!num!" neq "" (
  35.     >"%temp%\#" findstr /v "!num!" "%temp%\$"
  36.     move "%temp%\#" "%temp%\$" >nul
  37.     endlocal&set arr=%arr% %num%
  38.     goto :start
  39. )
  40. echo;%arr:~1%
  41. del "%temp%\$"
  42. pause
复制代码

作者: 思想之翼    时间: 2015-2-2 00:12

回复 15# terse

感谢!




欢迎光临 批处理之家 (http://www.bathome.net/) Powered by Discuz! 7.2