求抽取k个数字能组成的最大数字（已结贴）

shaowu459

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

shaowu459

递归公式，定义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)

复制代码

cinlo

语文不好，举例说明！

shaowu459

本帖问题相关的公式，还有其他一些思路和知识点，下面陆续总结一下。


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


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


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


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





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


第二次循环，2小于x底端的9，因此直接入栈。


第三次循环，1小于x底端的2，因此也直接入栈。


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




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


最后一次循环，3小于x底端的8，直接入栈即可。


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

shaowu459

第二个是按位提取的思路，啊一、象山海鲜及后面很多公式大体都沿用这个思路。

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



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


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


简单总结一下上述运算过程，假设原字符串中有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楼附件分别阅读，体会公式差异之处。

shaowu459

第三个是REDUCE函数x使用技巧的说明，以楼上数据和冬的公式为例说明。




先把格式化后的公式贴一下，方便后续阅读时参考。


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


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



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


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


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



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





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


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

shaowu459

楼上提到的公式简要说明如下：


=@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底端需要剔除的行数为上次需要剔除的行数+本次需要剔除的行数
        )
    )
)

misterZ

希望对你有用

冬不暖

misterZ 发表于 2023-11-21 00:11
希望对你有用

保持相对顺序不变啊 你这是做啥子

jivy1212

想了会，感觉上老版应该走不通的，都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)

复制代码

高个子

misterZ 发表于 2023-11-21 00:11
希望对你有用

第四行就不对了

cxywz

主公式：清洗数据剔除逗号，将递归的结果去除前导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. )

复制代码

wdx223

先扔块砖

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))

复制代码

xfbanxian

=TEXTJOIN(,,LARGE(SORT(TEXTSPLIT(A1,,"，")*1,1,-1),ROW(INDIRECT("1:"&B1))))

shaowu459

xfbanxian 发表于 2023-11-21 11:22
=TEXTJOIN(,,LARGE(SORT(TEXTSPLIT(A1,,"，")*1,1,-1),ROW(INDIRECT("1:"&B1))))

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

sucx007

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