最開始問(wèn)題：給定一個(gè)n個(gè)元素的數(shù)組/序列，找出所有m個(gè)元素組合成的集合（m<=n）

很明顯，這是一個(gè)經(jīng)典的組合數(shù)學(xué)問(wèn)題，我們知道組合的數(shù)量為C(m,n)=n!/(m!(n-m)!)，但現(xiàn)在我們需要的是所有可能的組合集合，于是我去問(wèn)ChatGPT如何在kotlin上實(shí)現(xiàn)，它給出了以下代碼：

第一眼，這個(gè)算法給的有模有樣的，但細(xì)看的話似乎有個(gè)很明顯的問(wèn)題：算法通過(guò)kotlin協(xié)程的yield函數(shù)提交sequence生成的元素，而算法中提交的是目標(biāo)序列的索引列表作為一個(gè)組合，那么理應(yīng)在每次列表發(fā)生修改后就做一次提交，但這里的提交只發(fā)生在while循環(huán)開頭，這似乎不太對(duì)？

我于是詢問(wèn)這個(gè)算法的來(lái)頭，chatgpt是這么解釋的：

問(wèn)：你給出的combination算法比較復(fù)雜且難以理解，是否有相關(guān)的算法參考？

答：是的，有一種常用的算法叫做 "Lexicographic Order" 或者 "Lexicographical Order"，它可以用來(lái)生成組合、排列和子集等。該算法比較簡(jiǎn)單，容易理解和實(shí)現(xiàn)。

該算法的基本思想是，將組合中元素的索引按字典序排序，從最小的組合開始，每次生成下一個(gè)組合，直到生成最大的組合為止。

具體實(shí)現(xiàn)過(guò)程如下：

1. 初始化組合中的索引數(shù)組 indices，使得 indices[i] 表示第 i 個(gè)元素在序列中的索引。

2. 生成第一個(gè)組合，即 indices 數(shù)組中前 size 個(gè)元素組成的序列。

3. 不斷生成下一個(gè)組合，直到生成最后一個(gè)組合。下一個(gè)組合的生成過(guò)程如下：

• 從右向左遍歷 indices 數(shù)組，找到第一個(gè)滿足 indices[i] < i + n - size 的元素，將其索引加一，并將其右側(cè)元素的索引設(shè)為該元素的索引加一，以確保組合中元素的索引按字典序遞增。

• 如果無(wú)法找到符合條件的元素，則已經(jīng)生成了最后一個(gè)組合，退出循環(huán)。

emm這次chatgpt確實(shí)沒有瞎編了，網(wǎng)上一搜真有這么一個(gè)知識(shí)，也就是”字典序“。但從維基上看字典序是個(gè)數(shù)學(xué)知識(shí)而且還是沒學(xué)過(guò)的那種……于是我去問(wèn)第一個(gè)提出該算法的文章/作者，以下是Chat GPT的回答：

該算法最早由 D. E. Knuth 在其經(jīng)典著作《The Art of Computer Programming》中提出，具體來(lái)說(shuō)是第四卷中的 7.2.1.3 節(jié) "Generating All Combinations" 中描述的。

好的再去搜，居然還對(duì)上了，確實(shí)有這本書，也確實(shí)有”Generating All Combination“這一章，也真的是7.2.1.3小節(jié)，看來(lái)在經(jīng)典文獻(xiàn)檢索方面ChatGPT表現(xiàn)還是相當(dāng)不錯(cuò)的。

然后就沒有然后了，原文表述比這還要復(fù)雜，涉及到了一堆更奇怪的表示方式，比如二進(jìn)制表示法表示選取的元素。

最后我終于理清這東西是個(gè)什么思路，其實(shí)有點(diǎn)像時(shí)鐘的運(yùn)轉(zhuǎn)方式，假設(shè)在有八個(gè)元素的序列中找出所有四個(gè)元素的組合，那么算法先初始化一個(gè)數(shù)組為[0,1,2,3]，其中每個(gè)元素表示的是到序列的索引值，接著末位自增到[0,1,2,7]，由于再自增下去要超出序列允許索引范圍，所以改成末位的前一位自增1，且末位比重置為比前一位大1，也就是[0,1,3,4]，然后末位繼續(xù)自增到7。按照這種”變形的時(shí)鐘規(guī)則“逐步遍歷的過(guò)程便是遍歷了所有可能索引組合。因此開頭的算法是正確的，while循環(huán)所作的就是進(jìn)行一次”時(shí)鐘運(yùn)轉(zhuǎn)“，yield函數(shù)也秩序在while開頭提交調(diào)用一次。

最后放ChatGPT對(duì)我所描述的”變形的時(shí)鐘規(guī)則“的回應(yīng)（雖然總覺得有種gpt在拍馬屁的意味==||：

是的，您的理解很接近。這個(gè)算法的實(shí)現(xiàn)基于一個(gè)“時(shí)鐘規(guī)則”的思想，其中數(shù)組的元素類似于時(shí)鐘的刻度。首先，我們將最高位的刻度（即c[m]）初始化為m，然后考慮生成其他刻度的可能性。

對(duì)于i < m的每個(gè)i，我們可以在當(dāng)前的刻度c[i]和下一個(gè)刻度c[i+1]之間進(jìn)行選擇。我們從上一個(gè)刻度c[i+1]開始，向前推進(jìn)到c[i]，并記錄生成的每個(gè)中間值。然后，我們按照該順序遍歷中間值，并使用它們來(lái)生成下一個(gè)刻度c[i]。由于我們從上一個(gè)刻度向前推進(jìn)，因此我們保證不會(huì)生成重復(fù)的組合。

最后，我們按照刻度的順序遍歷生成的組合，并將其作為函數(shù)的輸出。因?yàn)槲覀兪褂脃ield關(guān)鍵字在生成組合時(shí)暫停執(zhí)行，所以我們可以實(shí)現(xiàn)延遲計(jì)算并避免在不必要的情況下生成所有組合。