最少交换次数题目（奖励发放完毕）

shaowu459

详情请下载附件，预设139。和以前一样，大家公开跟帖回复公式，直到题目截止日。
为方便大家查看，将目前测试没有问题的公式都予以置顶。

alan57

1. =LET(m,REDUCE(A2,ROW($1:$88),LAMBDA(x,y,LET(a,MID(B2,y,1),i,@TAKE(x,-1),b,MID(i,y,1),_c,TEXTSPLIT(i,HSTACK(b,a),,1),c,CONCAT(_c),e,FIND(a,i),g,REPLACE(REPLACE(c,y,,a),e,,b),IF(AND(ISERR(_c),A2<>B2),x,IF(OR(a=b,i=B2),x,VSTACK(x,g)))))),n,IF(A2=B2,0,IF(ROWS(m)=1,1,ROWS(DROP(m,1)))),n)

复制代码

陆离Lowry

参与下
132：

1. =ROWS(REDUCE(A2,MID(B2,ROW($1:30),1),LAMBDA(x,y,LET(A,@LEFT(x),S,MID(SUBSTITUTE(x,y,A),2,39),IF(A="",x,IF(A=y,S,VSTACK(@S,x)))))))-1

复制代码

144：

1. =ROWS(REDUCE(A2,ROW($1:30),LAMBDA(x,y,LET(A,MID(x,y,1),B,MID(B2,y,1),IF(OR(x=B2,A=B),x,VSTACK(@REPLACE(REPLACE(x,y,1,B),FIND(B,x),1,A),x))))))-1

复制代码

132基础上再砍个112的

1. =SUM(REDUCE(A2,MID(B2,ROW($1:30),1),LAMBDA(x,y,LET(A,LEFT(@x),VSTACK(MID(SUBSTITUTE(@x,y,A),2,39),N(A<>y),x)))))

复制代码

shaowu459

1. =LEN(A2)-ROWS(REDUCE(0,MID(A2,ROW($1:99),1),LAMBDA(x,y,IF(OR(y=x),x,IFNA(VSTACK(x,SCAN(y,A1:M1,LAMBDA(m,n,MID(B2,FIND(m,A2),1)))),"")))))+1

复制代码

139字符

lws

1. =ROWS(REDUCE(A2,SEQUENCE(LEN(B2)),LAMBDA(X,Y,LET(F,MID(@X,Y,1),G,MID(B2,Y,1),M,HSTACK(G,F),IF(F=G,X,VSTACK(TEXTJOIN(M,0,TEXTSPLIT(@X,M)),X))))))-1

复制代码

1. =ROWS(REDUCE(A2,MID(B2,SEQUENCE(LEN(B2)),1),LAMBDA(X,Y,LET(S,@TAKE(X,-1),F,FIND(Y,S),G,FIND(Y,B2),IF(F=G,X,VSTACK(X,REPLACE(REPLACE(S,G,1,Y),F,1,MID(S,G,1))))))))-1

复制代码

静听溪流

交个答案参与下

1. =LET(A,UNIQUE(SCAN(A2,ROW($1:99),LAMBDA(X,Y,LET(B,MID(B2,Y,1),SUBSTITUTE(REPLACE(X,Y,1,B),B,MID(X,Y,1),2))))),ROWS(A)-OR(A=A2))

复制代码

1. =LET(A,UNIQUE(SCAN(A2,ROW($1:99),LAMBDA(X,Y,SUBSTITUTE(X,MID(B2,Y,1),MID(X,Y,1))))),ROWS(A)-(@A=A2))

复制代码

1. =ROWS(UNIQUE(SCAN(A2,99-ROW($1:99),LAMBDA(X,Y,SUBSTITUTE(X,MID(B2,Y,1),MID(X,Y,1))))))-2

复制代码

捡回一个小僵尸

1. =@REDUCE(VSTACK(0,B2),99-ROW($1:$98),LAMBDA(X,Y,LET(a,TAKE(X,-1),b,MID(A2,Y,1),c,MID(a,Y,1),IF(b=c,X,VSTACK(@X+1,SUBSTITUTE(a,b,c))))))

复制代码

135字符，凑个热闹，不知道为啥这里take前面不加@也能正常取值

cinlo

知道怎么处理VSTACK了：

1. =ROWS(UNIQUE(SCAN(1&A2,ROW($1:12),LAMBDA(x,y,SUBSTITUTE(x,MID(1&B2,y,1),MID(x,y,1))))))-1
   

复制代码

xlllw203

shaowu459 发表于 2024-3-26 10:33
两个字符串分别为文本型的“1”时公式返回结果不对，公式需调整

1. =COUNTA(TEXTSPLIT(REDUCE(A2,SEQUENCE(LEN(A2)),LAMBDA(x,y,LET(a,MID(x,y,1),b,MID(B2,y,1),IF(a<>b,SUBSTITUTE(x,b,a)&";"&y,x)))),";"))-1

复制代码

这样调整了一下。其实这个是一开始写出来的，后来为了省的写-1，所以改成了之前的那个。
COUNT判断情况下，当源字符为数字时，就会把源字符本身也算上，导致多计数1

realdoraemon

写了一个不知道有没有和别人重复

=LEN(REDUCE(A2,SEQUENCE(LEN(A2),,LEN(A2),-1),LAMBDA(s,n,LET(a,MID(s,n,1),b,MID(B2,n,1),LEFT(SUBSTITUTE(s,b,a),LEN(s)-(a=b))))))

静听溪流

shaowu459

除了替换的方法，还有一种利用判断“环”个数的方法解决这个问题，具体公式的一种写法参考我在16楼的公式。下面具体说明一下用环判断最少交换次数的原理。在具体介绍之前，先说明一个基础点：假如BA想交换成AB，BA这两个字母只最少需要交换一次；假如CAB想变成ABC，最少只需要交换两次，也就是n个位置不同的字母最少需要n-1次交换就可以将位置换到位。有了这个基础，下面来做具体说明：

如下图，源字符第一个字母是C，在结果字符串中是第三个；回到源字符串，第三个字符是A，A在第二个字符串中是第一个；再回到源字符串，第一个是C。如果继续按上述方法查找，会发现就循环起来了，循环中只有字母A和C，不会影响其他字母，我们可以把两个字符串中的A和C看做一个环（环之间不交叉），只需要在源字符串中将他们两个互相交换位置，这两个字母就会到正确的位置上了。因为有AC两个字母，所以只需要交换一次。





同理，如下的字符串中CAF三个字母组成了一个环，源字符串中的这3个字母交换两次，这三个字母位置就都会正确，并且交换过程中不影响其他的字母。




根据上面的方法，继续找环，B字母的位置正确，不需要交换，自成一个环，交换次数是环里字母的数字个数1减去1，等于0次，也就是不需要交换。剩余ED组成一个环，需要交换一次。所以，最少的交换次数=CAF的两次+B的0次+ED的一次=3次。


单看每个环，将字母归到正确位置的最少交换次数就是字母数量-1。每个环的字母互相独立，如果在各个环直接交换字母，会导致交换次数增多。因此，按上述分环计算的方法能得到将字母位置全部交换正确的最少交换次数。



简单总结一下：
1）从字符串第一个字母开始，按位置查找环，位置正确的字母独立成环，每个环之间不交叉；
2）每个环的最少交换次数是环的字母个数n-1；
3）有一个环，最少交换次数就是字母个数-1，因此整个字符串的最少交换次数就是：字符串长度-环的个数。

edwin11891

开启烧脑模式！

jivy1212

思路好简单，但是老版怎么判断环呢...

shaowu459

jivy1212 发表于 2024-3-22 11:03
思路好简单，但是老版怎么判断环呢...

是的。不过为啥不用365

痛痛痛痛

类似于最小路径问题啊

jivy1212

shaowu459 发表于 2024-3-22 11:04
是的。不过为啥不用365

单位授权问题用不了，回到家里时间没有。21版写个大思路公式吧，错了好多。细节还需要再处理

1. =LEN(A2)-MAX(1,INT(COUNT(FILTER(SEQUENCE(2^LEN(A2)-1),MMULT(MMULT(MID(BASE(SEQUENCE(2^LEN(A2)-1),2,LEN(A2)),SEQUENCE(,LEN(A2)),1)*1,10^CHOOSE({1,2},SEQUENCE(LEN(A2)),FIND(MID(B2,SEQUENCE(LEN(A2)),1),A2))),{-1;1})=0))/2))

复制代码

worm1

反正我的CPU已经烧了~~~

cnmlgb9998

用PQ解决！！！！！！！！！！！！！！！！！！

cnmlgb9998

先去同位同值数，再冒泡排序。

q490525427

积极回帖交作业