找到所有組合之和爲數字

Question

給定一個正整數n發現，所有組正整數的那筆到n

so 4 would be 
1 1 1 1 
2 1 1 
3 1 
2 2 

我認爲這是產生正確的數字，但我無法弄清楚如何打包結果。

public static IEnumerable<List<int>> BreakMeDown(int n) 
{ 
    for (int i = 1, j = n - 1; i <= j; i++, j--) 
    { 
     List<int> breakMeDown = new List<int>(); 
     breakMeDown.Add(i); 
     breakMeDown.Add(j); 
     yield return breakMeDown; 
     //Debug.WriteLine($"{i} {j}"); 
     foreach (List<int> li in BreakMeDown(i)) 
      yield return li; 
     foreach (List<int> li in BreakMeDown(j)) 
      yield return li;        
    } 
} 

// test 
foreach (List<int> li in BreakMeDown(7)) 
    Debug.WriteLine(string.Join(", ", li)); 

Answer 1

這裏，我們去：

static void Main(string[] args) 
{ 
    foreach (var li in BreakMeDown(7)) 
     Console.WriteLine(string.Join(", ", li)); 
} 

public static IEnumerable<IReadOnlyCollection<int>> BreakMeDown(int n) 
{ 
    for (int i = 1, j = n - 1; i <= j; i++, j--) 
    { 
     foreach (var li in BreakMeDown(j).Select(bd => bd.Concat(new[] {i}).ToList())) 
      yield return li; 
     foreach (var li in BreakMeDown(i).Select(bd => bd.Concat(new[] {j}).ToList())) 
      yield return li; 
     yield return new[] {i, j}; 
    } 
} 

編輯：

好了，根據你想刪除重複產生的序列的註釋。在這種情況下，要使用的正確數據結構是一個字典映射整數與出現次數。例如。 { 1: 5 }表示5的可能分解，其中數字1重複5次。

下面是代碼（我承擔了MoreLinq和Json.NET的依賴，因爲我不想要實現DistinctBy和對的IEqualityComparer詞典，但如果你願意，你可以做這些你自己）：

static void Main(string[] args) 
    { 
     foreach (var li in BreakMeDown(5).DistinctBy(JsonConvert.SerializeObject)) 
      Console.WriteLine(string.Join(", ", li)); 
    } 

    static IImmutableDictionary<int, int> Increment(this IImmutableDictionary<int, int> dict, int i) 
    { 
     return dict.SetItem(i, dict.TryGetValue(i, out int iCount) ? iCount + 1 : 1); 
    } 

    public static IEnumerable<IImmutableDictionary<int, int>> BreakMeDown(int n) 
    { 
     for (int i = 1, j = n - 1; i <= j; i++, j--) 
     { 
      var iAndJ = ImmutableSortedDictionary.Create<int, int>().Increment(i).Increment(j); 
      var bdJ = BreakMeDown(j).Select(bd => bd.Increment(i)); 
      var bdI = BreakMeDown(i).Select(bd => bd.Increment(j)); 

      var list = bdI.Concat(bdJ).Concat(new[] { iAndJ }); 
      foreach (var li in list) 
      { 
       yield return li; 
      } 
     } 
    } 

Answer 2

我認爲你正在尋找這個（不能測試它，所以我現在不是100％的正預期它會工作）：

public static IEnumerable<List<int>> BreakMeDown(int n) 
{ 
    for (int i = 1, j = n - 1; i <= j; i++, j--) 
    { 
     List<int> breakMeDown = new List<int>(); 
     breakMeDown.Add(i); 
     breakMeDown.Add(j); 
     yield return breakMeDown; 

     foreach (List<int> li in BreakMeDown(i)) 
      yield return breakMeDown.Skip(1) 
            .Concat(li) 
            .ToList(); 

     if (i != j) 
     { 
      foreach (List<int> li in BreakMeDown(j)) 
       yield return breakMeDown.Take(1) 
             .Concat(li) 
             .ToList(); 
     } 
    } 
} 

當你創建遞歸故障，您需要連接的結果到已經建成的2個因素分解中，忽略了你被破壞的因素進一步下跌。