查找長度爲k的所有遞減序列的列表？

我想弄清楚如何編寫一個函數，它需要兩個整數，n和k，並且找到所有嚴格遞減的從0到n的整數長度k的序列。查找長度爲k的所有遞減序列的列表？

例如，allDecreasing（5,3）返回

[[4,3,2]，[4,3,1]，[4,3,0]，[4,2， 1]，[4,2,0]，[4,1,0]，[3,2,1]，[3,2,0]，[3,1,0]，[2,1,0] ]

到目前爲止，我只有：

function all-decreasing(n, k) { 
    if (n > k-1) { 
     all-decreasing(n-1, k); 
    } 
}

它的並不多，因爲我不太知道如何處理迭代的一部分。置換和子集算法一直困擾着我。如果有人可以給我一個關於如何開始的想法，那將不勝感激！謝謝。

來源

2014-11-05 gsteves

從範圍中選擇n個整數，排序。要選擇每個這樣的集合一次，有許多實現，請參見[這裏]（http://stackoverflow.com/questions/4504974/how-to-iteratively-generate-k-elements-subsets-from-a-set-例如java中的size-n-in-size）。 – 2014-11-05 11:02:20

Delphi版本。我希望你能看到邏輯

procedure alldecreasing(n, k: Integer; s: string); 
var 
    i: Integer; 
begin 
    if k = 0 then 
    Output(s) 
    else 
    for i := n - 1 downto k - 1 do 
     alldecreasing(i, k - 1, s + IntToStr(i)); 
end; 

a call: 
    alldecreasing(5, 3, ''); 
gives: 
432 
431 
430 
421 
420 
410 
321 
320 
310 
210

來源

2014-11-05 10:56:41 MBo

你應該考慮一下像

問題（3/5）的問題 - 5個號碼，3真，2個假

4 3 2 1 0 
--------- 
1 1 1 0 0 = 4 3 2 (flip) 
1 1 0 1 0 = 4 3 1 (flip) 
1 1 0 0 1 = 4 3 0 (flip)(reset 1) 
1 0 1 1 0 = 4 2 1 (flip) 
1 0 1 0 1 = 4 2 0 (flip) 
1 0 0 1 1 = 4 1 0 (flip)(reset 2) 
0 1 1 1 0 = 3 2 1 (flip) 
0 1 1 0 1 = 3 2 0 (flip) 
0 1 0 1 1 = 3 1 0 (flip) 
0 0 1 1 1 = 2 1 0 (flip)

基本操作你需要能夠做的是：

找到最右邊（10），翻蓋（10）又名（翻轉）
如果不是最右邊的1，復位1周的後又名（復位N）

這將非常有效地開展工作可笑的大集。

來源

2014-11-05 11:51:07 Margus

查找長度爲k的所有遞減序列的列表？

回答

相關問題