每個數字組合的遞歸函數

提供一些上下文：我正在開發一個算法問題構建器，最終用戶可以輸入變量，爲它們分配範圍和規則，在公式中使用它們並實現（x）個問題。每個數字組合的遞歸函數

我目前需要用變量名[a]，[b]，[c] ..等等的鍵來填充x數量的x個元素的字典，每個值都是唯一的，他們可能潛在的範圍的每一種可能性;即a = 1-100，b = 1-50等等。

So 1st dict would be: 
[a] = 1 
[b] = 1 
[c] = 1 

2nd dict 
[a] = 2 
[b] = 1 
[c] = 1

是否有一個簡單的遞歸函數可以比迭代函數更好地處理？

感謝您的幫助！

來源

2016-03-03 daniel-schofield93

爲什麼迭代解決方案不夠？ –

定義：「更好」 – Plutonix

你想要的是範圍的笛卡爾乘積。關於這個網站有很多問題。嘗試http://stackoverflow.com/questions/4073713/is-there-a-good-linq-way-to-do-a-cartesian-product/4073806#4073806開始。 –

如果我開始的結構，可以代表你的價值觀的範圍內，這樣的：

public struct Range 
{ 
    public int Minimum { get; set; } 
    public int Maximum { get; set; } 
}

...然後我可以代表你這樣的輸入：

var inputs = new Dictionary<string, Range>() 
{ 
    { "a", new Range() { Minimum = 1, Maximum = 3 } }, 
    { "b", new Range() { Minimum = 1, Maximum = 2 } }, 
    { "c", new Range() { Minimum = 1, Maximum = 2 } }, 
};

...然後我可以生成如下結果：

Func<IEnumerable<KeyValuePair<string, Range>>, IEnumerable<Dictionary<string, int>>> build = null; 
build = 
    kvps => 
    { 
     if (kvps.Skip(1).Any()) 
     { 
      return 
       from kvp in kvps.Take(1) 
       from n in Enumerable.Range(kvp.Value.Minimum, kvp.Value.Maximum - kvp.Value.Minimum + 1) 
       from r in build(kvps.Skip(1)) 
       select new[] { new KeyValuePair<string, int>(kvp.Key, n) }.Concat(r).ToDictionary(x => x.Key, x => x.Value); 
     } 
     else 
     { 
      return 
       from kvp in kvps 
       from n in Enumerable.Range(kvp.Value.Minimum, kvp.Value.Maximum - kvp.Value.Minimum + 1) 
       select new[] { new KeyValuePair<string, int>(kvp.Key, n) }.ToDictionary(x => x.Key, x => x.Value); 
     } 
    };

這產生下面的字典列表：

 
a=1, b=1, c=1 
a=1, b=1, c=2 
a=1, b=2, c=1 
a=1, b=2, c=2 
a=2, b=1, c=1 
a=2, b=1, c=2 
a=2, b=2, c=1 
a=2, b=2, c=2 
a=3, b=1, c=1 
a=3, b=1, c=2 
a=3, b=2, c=1 
a=3, b=2, c=2

這裏的主查詢的解釋：

from kvp in kvps.Take(1)

獲取從kvps枚舉（這是可枚舉的「頭」）的第一個元素

from n in Enumerable.Range(kvp.Value.Minimum, kvp.Value.Maximum - kvp.Value.Minimum + 1)

將n的所有值從Minimum生成爲Maximum。

from r in build(kvps.Skip(1))

遞歸調用build在列表的「尾部」產生的所有可能的尾巴字典

select new[] { new KeyValuePair<string, int>(kvp.Key, n) }.Concat(r).ToDictionary(x => x.Key, x => x.Value);

創建一個新的KeyValuePair<string, int>[]與Key和值n並連接在每個值尾部（r）創建一個新字典。

來源

2016-03-03 04:35:45 Enigmativity

非常感謝你的這個@Enigmativity！有沒有可能在迭代塊中添加一些註釋來解釋發生了什麼？再次歡呼！ –

@ daniel-schofield93 - 完成。 – Enigmativity

每個數字組合的遞歸函數

回答

相關問題