[文本处理] 【已解决】BAT或VBS：如何寻找最少共有数

思想之翼

文本内有如下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

应该可以的 只是没看懂

思想之翼

回复 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

回复  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

每个字都认得，组合起来就看不懂了...

xxpinqz

相互理解是个难题啊。。。。
貌似3楼给出的45组数据就是最少组合了吧？

terse

处理10-99数字 其他情况（如同行重复数据）没考虑

@echo off&setlocal enabledelayedexpansion
for /f "delims=" %%i in (a.txt) do (
    set /a n+=1
    for %%i in (%%i) do (
        set/a _%%i+=1
        for %%j in (!_%%i!) do set $%%j=!$%%j! %%i
        set len%%i=!n! !len%%i!
   )
)

for /l %%i in (10 1 99) do (
    if defined $!_%%i! (
       for %%j in (!_%%i!) do (
           set #%%j=!$%%j!
           set "str=!str! %%j"
           set "$%%j="
       )
    )
)

for /f %%i in ('(for %%i in (!str!^) do @echo;%%i^)^|sort') do (
    set ar=%%i !ar!
)

for  %%i in (!ar!) do (
     for %%j in (!#%%i!) do (
         if defined len%%j (
            set flag=
            for %%k in (!len%%j!) do (
                if not defined f%%k (
                   set flag=1
                   set f%%k=1
                ) 
            )
            if defined flag set arr=!arr! %%j
            set len%%j=
        )
    )
)
echo!arr!
pause
复制代码

思想之翼

回复 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

以前好像也看到过你发的帖子，总觉得语言语文是美术老师教的，
就说一下按照理解想的步骤吧，先把所有的数列出来，然后找到一个出现的行数最多的一个，取出这个数字的同时把相关的那些行都排除，继续重复直到把所有行都排除掉

fn = "numbers.txt"

Set data = ReadNumbers(fn)

Do While data.Count > 0
    x = FetchOneNumber(data)
    WScript.Echo x
Loop


Function ReadNumbers(filespec)
    Dim objData, objFso, objFile, arrLine
    Set objData = WScript.CreateObject("Scripting.Dictionary")
    Set objFso = WScript.CreateObject("Scripting.FileSystemObject")
    Set objFile = objFso.OpenTextFile(filespec, 1)
    Do While Not objFile.AtEndOfStream
        objData.Add objFile.Line, Split(objFile.ReadLine())
    Loop
    Set ReadNumbers = objData
End Function

Function FetchOneNumber(objDictionary)
    Dim objNum, objLine, lines, l, nums, n, i, j, theOne, theFreq
    Set objNum = WScript.CreateObject("Scripting.Dictionary")
    ' 将数据转换成 key:NUMBER/value:LINE 格式
    lines = objDictionary.Keys
    For i = 0 To UBound(lines)
        l = lines(i)
        nums = objDictionary.Item(l)
        For j = 0 To UBound(nums)
            n = nums(j)
            If Not objNum.Exists(n) Then
                Set objLine = WScript.CreateObject("Scripting.Dictionary")
                objNum.Add n, objLine
            End If
            objNum.Item(n).Add l, 1
        Next
    Next
    ' 找到出现频率最高的数字
    theOne = -1
    theFreq = 0
    nums = objNum.Keys
    For i = 0 To UBound(nums)
        n = nums(i)
        Set objLine = objNum.Item(n)
        If objLine.Count > theFreq Then
            theOne = n
            theFreq = objLine.Count
        End If
    Next
    ' 剔除已使用的行
    Set objLine = objNum.Item(theOne)
    lines = objLine.Keys
    Dim strMsg
    strMsg = "数字 " & theOne & " 出现 " & objLine.Count & " 次，位于第 "
    For j = 0 To UBound(lines)
        strMsg = strMsg & " " & lines(j)
        objDictionary.Remove lines(j)
    Next
    strMsg = strMsg & " 行；"
    ' WScript.StdOut.WriteLine strMsg
    ' 设置返回值
    FetchOneNumber = theOne
End Function
复制代码

思想之翼

回复 9# Spring
感谢帮助。
您的代码运行后，输出的文本为空。

terse

回复 10# 思想之翼
应该还是算法错误
先用VBS处理了

terse

回复 10# 思想之翼
每次提一个最多行 然后排除掉
貌似还不是最优结果啊 郁闷
问题出在哪里呢？

@echo off
copy a.txt "%temp%\$"  >nul
:start
setlocal enabledelayedexpansion
for /f "usebackqdelims=" %%i in ("%temp%\$") do (
    for %%i in (%%i) do (
        set/a _%%i+=1
        if !n! lss !_%%i! (
           set n=!_%%i!
           set $!n!=%%i
        )
   )
)

if "!$%n%!" neq "" (
   for /f "tokens=1*" %%a in ("!$%n%! !arr!") do (
       endlocal
       set arr=%%a %%b
       >"%temp%\#" findstr /v "%%a" "%temp%\$"
       move "%temp%\#" "%temp%\$" >nul
       goto :start
   )
)
echo %arr%
pause
复制代码

xxpinqz

可能这题的答案不是唯一的，你给出的：

20 40 60 80 13 15 17 19 24 26 28 35 37 39 46 48 57 59 68 79
复制代码

和9楼给出的：

16 27 38 49 50 18 29 37 40 56 10 39 47 26 58 15 79 20 48 36
复制代码

都是20组数据，也都能满足满足每行数据在这组数据内，至少有1个的要求。

CrLf

想了两个思路，都不能保证得到最优解，难道一定要用暴力手段

terse

貌似提取到最少项
怎么验证呢
不知道是否还要判断子项

@echo off
copy a.txt "%temp%\$"  >nul
:start
setlocal enabledelayedexpansion
for /f "usebackqdelims=" %%i in ("%temp%\$") do (
    set /a len+=1
    for %%j in (%%i) do (
        set/a _%%j+=1
        set len%%j=!len%%j! !len!
        if !n! lss !_%%j! (
           set n=!_%%j!
           set t=%%j
           set num=%%j
        ) else if !n! equ !_%%j! set t=!t! %%j
        )
    )
)

if "!t!" neq "!num!" (
   for %%i in (!t!) do (
       for %%j in (!len%%i!) do (
           set /a $%%j+=1
           set #%%i=!#%%i!+$%%j
       )
   )
   set n=999
   for %%i in (!t!) do (
       set /am=!#%%i!
       if !n! gtr !m! (
          set n=!m!
          set num=%%i
       )
   )
)

if "!num!" neq "" (
    >"%temp%\#" findstr /v "!num!" "%temp%\$"
    move "%temp%\#" "%temp%\$" >nul
    endlocal&set arr=%arr% %num%
    goto :start
)

echo;%arr:~1%
del "%temp%\$"
pause
复制代码