ExcelHome技术论坛

 找回密码
 免费注册

QQ登录

只需一步,快速开始

快捷登录

搜索
EH技术汇-专业的职场技能充电站 妙哉!函数段子手趣味讲函数 Excel服务器-会Excel,做管理系统 Excel Home精品图文教程库
数据管理利器Foxtable2022下载 Excel 2019函数公式学习大典 不用妈妈陪默写神器 打造核心竞争力的职场宝典
300集Office 2010微视频教程 数据工作者的案头书 免费直播课集锦 ExcelHome出品 - VBA代码宝免费下载
你的Excel 2010实战技巧学习锦囊 WPS表格从入门到精通 Excel VBA经典代码实践指南
查看: 1765|回复: 46

[讨论] 求抽取k个数字能组成的最大数字(已结贴)

[复制链接]

TA的精华主题

TA的得分主题

发表于 2023-11-20 20:43 | 显示全部楼层 |阅读模式
本帖最后由 shaowu459 于 2023-12-2 08:43 编辑

提示:
如果能不用穷举尽量不要用穷举,穷举筛选的方法字符串长度和k值增大后会卡顿或返回错误值。题目设置n≤20是为了能获得尽可能多的解决方案。


图片.jpg

求抽取k个数字能组成的最大数字-题目.rar

11.14 KB, 下载次数: 155

求抽取k个数字能组成的最大数字-公式汇总.rar

28.89 KB, 下载次数: 12

评分

参与人数 13鲜花 +30 技术 +1 收起 理由
象山海鲜 + 1 好题~~~
zpy2 + 3 优秀作品
solextrade + 3 太强大了
cinlo + 3 太强大了
江山社稷 + 2

查看全部评分

TA的精华主题

TA的得分主题

 楼主| 发表于 2023-11-24 09:43 | 显示全部楼层
[广告] VBA代码宝 - VBA编程加强工具 · VBA代码随查随用  · 内置多项VBA编程加强工具       ★ 免费下载 ★      ★使用手册
递归公式,定义fx:
  1. =LAMBDA(x,y,z,IF(z,LET(s,MAX(DROP(y,1-z)),fx(IF(-x,x,)&s,DROP(y,MATCH(s,y,)),z-1)),x))
复制代码
单元格中输入公式:
  1. =fx(0,--TEXTSPLIT(A2,,","),B2)
复制代码




评分

参与人数 4鲜花 +12 收起 理由
高个子 + 3
橒♂蝣 + 3
cinlo + 3 太强大了
wdx223 + 3 优秀作品

查看全部评分

TA的精华主题

TA的得分主题

发表于 2023-12-1 09:17 | 显示全部楼层
[广告] Excel易用宝 - 提升Excel的操作效率 · Excel / WPS表格插件       ★免费下载 ★       ★ 使用帮助
语文不好,举例说明!
企业微信截图_17013934123361.png
企业微信截图_17013934466867.png

求抽取k个数字能组成的最大数字-题目.zip

14.05 KB, 下载次数: 3

评分

参与人数 3鲜花 +5 技术 +1 收起 理由
sucx007 + 3 太强大了
luoheping76 + 2
shaowu459 + 1 辛苦总结

查看全部评分

TA的精华主题

TA的得分主题

 楼主| 发表于 2023-12-1 09:58 | 显示全部楼层
本帖问题相关的公式,还有其他一些思路和知识点,下面陆续总结一下。


一是单调栈思路。这个思路的基础思想是:提取k个数字,就等于从原n个数字中剔除n-k个数字。如果当前数字比右侧数字小,那么就剔除当前数字,让右侧数字保留,这样保留的数字会越来越大。当剔除的数字达到n-k后,后面所有数字就不能再剔除了,都要追加到结果字符串中。


关于模拟栈操作的基本介绍可以参考我之前的帖子求右括号位置。单调栈可以简单理解为一个单行或单列数组,数组中的元素都是逐个递增或抵减的。本例模拟单调递增栈(不是纯单调递增,后面说明),大体思路是:当新元素要加入栈的时候,如果当前元素不大于栈顶元素,直接添加该元素到栈顶;如果当前元素大于栈顶元素时,就要将栈顶小于当前元素的值弹出栈顶,直到当前元素小于栈内元素或者栈为空。这种方式能保证越大的数字,位置尽量靠前,也就是结果数字越大。


下面以“9,2,1,5,8,3”,取2个数字为例来说明。


“9,2,1,5,8,3”字符串一共6个数字,要取2个,因此最终能剔除(出栈)的数字数量为4个。为了保证第一个数字能入栈,我们选择一个空文本作为初始元素。为了方便取数,我们保留4和空文本为REDUCE函数的初始值。


图片.png


第一次循环时,9小于x底端的空文本,因此直接入栈。


第二次循环,2小于x底端的9,因此直接入栈。
图片.png

第三次循环,1小于x底端的2,因此也直接入栈。
图片.png

第四次循环,因为5大于栈底的2,所以底端元素要出栈。观察底端的2个数字,1和2都小于5,并且栈顶记录的可剔除数字总量是4,因此,栈底的2个数字都出栈,然后5入栈。顶端记录可剔除的数字由4减少到2。


图片.png

第五次循环,8大于x底端的5,还可以剔除的数字是2个,所以5可以出栈,8入栈。x顶端记录可剔除数字的数量从2变成1。
图片.png

最后一次循环,3小于x底端的8,直接入栈即可。
图片.png

循环结束后,x顶端记录还可以剔除的数字数量是1,没有关系,当前数字已经是最大的了。循环完毕后,原字符串能保留的最大数字是983(剔除循环结束后x的前2个中间元素),因为最后要提取2个数字,所以再提取983的前两位98即可。上述公式参考13楼。



图片.png

评分

参与人数 4鲜花 +9 收起 理由
micch + 2 太强大了
luoheping76 + 2 太强大了
cinlo + 3 太强大了
alan57 + 2 太强大了

查看全部评分

TA的精华主题

TA的得分主题

 楼主| 发表于 2023-12-1 10:20 | 显示全部楼层
[广告] VBA代码宝 - VBA编程加强工具 · VBA代码随查随用  · 内置多项VBA编程加强工具       ★ 免费下载 ★      ★使用手册
第二个是按位提取的思路,啊一、象山海鲜及后面很多公式大体都沿用这个思路。

仍然以上面的数据为例,从字符串中提取3个数字。

图片.png

原字符串中一共有6个数字,因为要提取3个数字,所以结果是一个3位的数字。根据题目要求,可以分析出,最高位的百位数字,必然在所有数字中的前4位中产生。可以这样分析:假设最高的百位数字在前3个数字中产生,后面还有3个数字,如果第4个数字大于前3个数字中的最大值,还是要用第4个数字替换掉前3个数字中的最大值的,因为后面还有5、6两位数,可以保证结果是3位数,并且数字更大。
图片.png

上面的例子中前4位中最大的是9,那么就把9记录下来,作为结果字符串的第一个字符。然后把这个9和之前的数字从数组中剔除。在剩余的数组中扣除最后一个数字的部分中取最大值作为十位的数字,也就是8,然后将8连接在9后面,生成98这个字符串。然后把数字8和之前的元素从x中剔除,在剩余数组中取最大值3,合并在98后面生成983即为所求。
图片.png

简单总结一下上述运算过程,假设原字符串中有n个数字,要提取k个数字:
1)从n个数字末尾剔除k-1个数字,剩余数字中提取最大值a;
2)从x中将a和a之前的数字去除,将a保留下来作为结果字符串第一个字符;
3)从新的x末尾剔除k-2个数字,剩余数字中提取最大值b;
4)从x中将b和b之前的数字去掉,将b保留下来连接在a后面,更新结果字符串为ab;
5)循环k次结束。


上面是大体思路,公式实现方式细节有所不同,大部分公式核心都是此思路,有兴趣的可以下载1楼附件分别阅读,体会公式差异之处。


评分

参与人数 2鲜花 +6 收起 理由
sucx007 + 3 太强大了
cinlo + 3 太强大了

查看全部评分

TA的精华主题

TA的得分主题

 楼主| 发表于 2023-12-1 11:11 | 显示全部楼层
[广告] VBA代码宝 - VBA编程加强工具 · VBA代码随查随用  · 内置多项VBA编程加强工具       ★ 免费下载 ★      ★使用手册
第三个是REDUCE函数x使用技巧的说明,以楼上数据和冬的公式为例说明。

图片.png


先把格式化后的公式贴一下,方便后续阅读时参考。
图片.png

在这个公式中,使用REDUCE函数的x存储两个值,一个是结果字符串,一个是每步要剔除数字的位置,x初始值设定为0,一共循环3次。


第一次循环,MIN函数获得x中的最小值0,从数组中剔除0行,从尾部剔除3-1=2行,在剩余的数组中取得最大值9和9第一次出现的位置1。
图片.png


第一次循环结束时,将数字9和x顶端的结果字符串连接。当x顶端是0的时候就返回空否则返回x顶端的数字(去除前导0的方法),然后连接9。然后在结果字符串下方堆积9在数组中第一次出现的位置1,下次这个9和其之前的数字就都不能再使用了,因为已经使用过一次。
图片.png

循环结束后,x由初始值0变成了两行一列的数组,x顶端的9是字符串,下面的元素是数字,所以用MAX、MIN、SUM等函数都可以提取出1这个数字:
图片.png

第二次循环时,在原数字数组中去掉第一行(当前x底端的1,代表上一次提取的9在数组中的位置),剔除底端的3-2行。在剩余数组中提取最大值9和第一次出现的位置1。

图片.png

将本次提取的数字9和x顶端的结果字符串连接,更新结果字符串为99。因为本次最大值9所在位置1是原数组已经剔除了当前x底端记录的剔除行数1后的结果,所以下次应该从原数组中剔除1+1=2行,也就是上次剔除的行数和本次应剔除的行数之和。


图片.png


第二次循环完毕,x结果变成以下数据,顶端结果字符串变为99,底端记录的剔除行数变成了2,下次循环先在原数组中剔除前2行后再进行后续操作。
图片.png

后面以此类推,循环完毕,使用@提取x顶端的结果字符串即可。


TA的精华主题

TA的得分主题

 楼主| 发表于 2023-12-1 11:15 | 显示全部楼层
[广告] Excel易用宝 - 提升Excel的操作效率 · Excel / WPS表格插件       ★免费下载 ★       ★ 使用帮助
楼上提到的公式简要说明如下:


=@REDUCE(
    0,      x初始值设定为0,从原数组中剔除0行
    SEQUENCE(B2),    循环次数为要提取数字的个数,运算量很小
    LAMBDA(x, y,
        LET(
            a, MIN(x),    因为x共有2个元素,一个字符串一个是要提取的行数数字,所以用MIN可以直接提取x第二个元素数字
            b, DROP(
                DROP(--TEXTSPLIT(A2, , ","), a),    首先剔除掉x底端记录的需要剔除的行数,再从数字末尾剔除行数
                y - B2
            ),
            c, MAX(b),    求数组b中的最大值
            VSTACK(IF(-@x, @x, ) & c, MATCH(c, b, ) + a)   将最大值b连接在x顶端的结果字符串右侧,同时更新x底端需要剔除的行数为上次需要剔除的行数+本次需要剔除的行数
        )
    )
)



评分

参与人数 1鲜花 +2 收起 理由
luoheping76 + 2

查看全部评分

TA的精华主题

TA的得分主题

发表于 2023-11-21 00:11 | 显示全部楼层
[广告] Excel易用宝 - 提升Excel的操作效率 · Excel / WPS表格插件       ★免费下载 ★       ★ 使用帮助
希望对你有用

最大数字

最大数字

评分

参与人数 1鲜花 +1 收起 理由
世界客都 + 1 要看清楚题目来

查看全部评分

TA的精华主题

TA的得分主题

发表于 2023-11-21 08:16 | 显示全部楼层

TA的精华主题

TA的得分主题

发表于 2023-11-21 08:37 | 显示全部楼层
本帖最后由 jivy1212 于 2023-11-21 11:08 编辑

想了会,感觉上老版应该走不通的,都18位了。老思路参与一下了没法适应后面二条那么长位数的。
  1. =MAX(--(0&LEFT(SUBSTITUTE(MID(CONCAT(IF(MOD(INT(-ROW(OFFSET($A$1,,,2^((LEN(A2)+1)/2)-1))/2^COLUMN(OFFSET($A$1,,,,(LEN(A2)+1)/2))*2),2),MID(A2,COLUMN(OFFSET($A$1,,,,(LEN(A2)+1)/2))*2-1,1)," ")),ROW($1:$66)*(LEN(A2)+1)/2-(LEN(A2)-1)/2,(LEN(A2)+1)/2)," ",),B2)))
复制代码


不怕卡硬算法,一样适应不了长数
  1. =LOOKUP(,-SEARCH(TEXT(ROW(INDIRECT("1:"&10^B2))-1,REPT("!*0",B2)),A2),ROW(INDIRECT("1:"&10^B2))-1)
复制代码

评分

参与人数 9财富 +50 鲜花 +20 收起 理由
shaowu459 + 50 值得肯定
华尔街操盘手 + 2 太强大了
剑指E + 3 优秀作品
海马爸爸 + 2 值得肯定
cinlo + 3

查看全部评分

TA的精华主题

TA的得分主题

发表于 2023-11-21 09:24 | 显示全部楼层

TA的精华主题

TA的得分主题

发表于 2023-11-21 10:54 | 显示全部楼层
本帖最后由 cxywz 于 2023-11-21 15:25 编辑

主公式:清洗数据剔除逗号,将递归的结果去除前导0(超人大佬提供的方法):
递归公式(思路:删除右边k-1个字符后的字符,取最大值,找到这个最大值位置,取这个位置右边字符串递归,并合并结果):(本方法用字符串方法,用数组方法方便点)
  1. =LET(
  2.     r, dg(SUBSTITUTE(A2, ",", ""), B2),
  3.     mh, MATCH(TRUE, MID(r, SEQUENCE(LEN(r)), 1) > "0", ),
  4.     IFNA(MID(r, mh, 999), "0")
  5. )
复制代码
  1. dg = LAMBDA(str, k,
  2.     IF(
  3.         k = 1, //递归退出条件,剩下的字符取最大的
  4.         MAX(--RIGHT(LEFT(str, SEQUENCE(LEN(str))))),
  5.         LET(
  6.             leftlen, LEN(str) - (k - 1), //截取右边k-1后的字符找最大数值
  7.             maxc, MAX(--RIGHT(LEFT(str, SEQUENCE(leftlen)))),
  8.             n, FIND(maxc, str), //这个字符的首位置
  9.             maxc & dg(MID(str, n + 1, 999), k - 1) //最大字符后的数据进行递归合并
  10.         )
  11.     )
  12. )
复制代码
根据上面的思路,改写为循环公式,仅需要循环K次:
  1. =LET(
  2.     data, --TEXTSPLIT(A2, , ","),
  3.     k, B2,
  4.     r, TAKE(
  5.         REDUCE(
  6.             data,
  7.             SEQUENCE(k),
  8.             LAMBDA(x, y,
  9.                 LET(
  10.                     maxn, MAX(DROP(x, -k + 1)),
  11.                     mh, MATCH(maxn, x, ),
  12.                     VSTACK(DROP(x, mh), maxn)
  13.                 )
  14.             )
  15.         ),
  16.         -k
  17.     ),
  18.     IF(
  19.         k = 1,
  20.         MAX(data),
  21.         IFNA(CONCAT(DROP(r, MATCH(TRUE, r > 0, ) - 1)), 0)
  22.     ) & ""
  23. )
复制代码




评分

参与人数 3财富 +50 鲜花 +4 收起 理由
shaowu459 + 50 值得肯定
高个子 + 3
世界客都 + 1 优秀作品

查看全部评分

TA的精华主题

TA的得分主题

发表于 2023-11-21 11:01 | 显示全部楼层
先扔块砖
  1. =LET(a,REDUCE("",TEXTSPLIT(A2,","),LAMBDA(x,y,LET(b,FILTER(x,LEFT(x)<>"0"),VSTACK(b,FILTER(b,LEN(b)<B2)&y)))),@SORTBY(a,LEN(a),-1,a,-1))
复制代码

评分

参与人数 10财富 +12 鲜花 +22 收起 理由
世界客都 + 2 优秀作品
象山海鲜 + 12 优秀公式
cinlo + 3 太强大了
江山社稷 + 2 太强大了
高个子 + 3

查看全部评分

TA的精华主题

TA的得分主题

发表于 2023-11-21 11:22 | 显示全部楼层
=TEXTJOIN(,,LARGE(SORT(TEXTSPLIT(A1,,",")*1,1,-1),ROW(INDIRECT("1:"&B1))))

TA的精华主题

TA的得分主题

 楼主| 发表于 2023-11-21 11:32 | 显示全部楼层
xfbanxian 发表于 2023-11-21 11:22
=TEXTJOIN(,,LARGE(SORT(TEXTSPLIT(A1,,",")*1,1,-1),ROW(INDIRECT("1:"&B1))))

请在我1楼的文件中测试公式,并和示例结果核对。

TA的精华主题

TA的得分主题

发表于 2023-11-21 13:06 | 显示全部楼层
  1. =LET(m,LEN(A2&0)/2,t,TEXTSPLIT(A2,,","),r,REDUCE(0,BASE(SEQUENCE(2^m-1),2,m),LAMBDA(x,y,IF(LEN(SUBSTITUTE(y,0,))=B2,VSTACK(x,CONCAT(FILTER(t,-MID(y,SEQUENCE(m),1)))),x))),@SORTBY(r,-r))
复制代码
文本数字,没有去除首位0

评分

参与人数 3财富 +50 鲜花 +5 收起 理由
shaowu459 + 50 优秀作品
cinlo + 3 太强大了
世界客都 + 2 优秀作品

查看全部评分

您需要登录后才可以回帖 登录 | 免费注册

本版积分规则

手机版|关于我们|联系我们|ExcelHome

GMT+8, 2023-12-8 23:16 , Processed in 0.093434 second(s), 18 queries , Gzip On, MemCache On.

Powered by Discuz! X3.4

© 1999-2023 Wooffice Inc.

   

沪公网安备 31011702000001号 沪ICP备11019229号-2

本论坛言论纯属发表者个人意见,任何违反国家相关法律的言论,本站将协助国家相关部门追究发言者责任!     本站特聘法律顾问:李志群律师

快速回复 返回顶部 返回列表