C＃查找數字的所有可能組合

-2

我在製作算法時遇到了困難，這些算法以一種從「0」開始的升序排序的方式「洗牌」一組數字，下一個數字不得超過前一個數字+ 1，它們的長度也必須爲15，並且必須包含該組數字中的每一個數字。例如，如果我們有數字：C＃查找數字的所有可能組合

0,1

期望的輸出是：

0,0,0,0,0,0,0,0， 0,0,0,0,0,0,1（是的是14個零）

0,0,0,0,0,0,0,0,0,0,0,0,0,0， 1,1

..

0,1,1,1,1,1,1,1,1,1,1,1,1,1,1

同樣如此，如果數字是

0，1，2

0,0,0,0,0,0,0,0,0,0,0,0,0,1,2（必須包含每數）

我嘗試了以下，我失敗了：

版本1個

private static List<List<int>> GetNumbers(int lastNumber) 
    { 
     if (lastNumber == 0) 
     { 
      return new List<List<int>> { new List<int> { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } }; 
     } 
     int[] setOfNumbers = new int[lastNumber + 1]; 
     List<List<int>> possibleRoutes = new List<List<int>>().ToList(); 
     for (int i = 0; i <= lastNumber; i++) 
     { 
      setOfNumbers[i] = i; 
     } 
     var temp = new List<int>(); 
     int[] possibleRoute = new int[15]; 
     for (int j = 0; j < size - lastNumber; j++) 
     { 
      possibleRoute[j] = 0; 
     } 
     for (int j = lastNumber; j < possibleRoute.Length; j++) 
     { 
      for (int k = j; k > 0; k--) 
      { 
       possibleRoute[k] = lastNumber - 1; 
      } 
      for (int i = size - 1; i >= j; i--) 
      { 
       possibleRoute[i] = lastNumber; 
      } 
      possibleRoutes.Add(possibleRoute.ToList()); 
      generalCounter++; 
     } 
     return possibleRoutes; 
    }

2版

private static List<List<int>> GetNumbers(int lastNumber) 
    { 
     if (lastNumber == 0) 
     { 
      return new List<List<int>> {new List<int> {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}}; 
     } 
     int[] setOfNumbers = new int[lastNumber + 1]; 
     List<List<int>> possibleRoutes = new List<List<int>>().ToList(); 
     for (int i = 0; i <= lastNumber; i++) 
     { 
      setOfNumbers[i] = i; 
     } 
     var temp = new List<int>(); 
     int[] possibleRoute = new int[15]; 
     for (int j = 0; j < size - lastNumber; j++) 
     { 
      possibleRoute[j] = 0; 
     } 
     for (int i = 1 ; i <= lastNumber ; i++) 
     { 
      int newNumber = lastNumber - i; 
      for (int k1 = i + 1; k1 <= size; k1++) 
      { 
       for (int j = possibleRoute.Length - 1; j > k1 - i - 1; j--) 
       { 
        possibleRoute[j] = lastNumber; 
       } 
       for (int k = i; k <= k1 - 1; k++) 
       { 
        possibleRoute[k] = newNumber; 
       } 
       possibleRoutes.Add(possibleRoute.ToList()); 
       generalCounter++; 
      } 
     } 
     return possibleRoutes; 
    }

來源

2016-04-05 KOPEUE

你能證明你到目前爲止已經嘗試過嗎？ –

現在可以請你解釋一下你有什麼特別的問題嗎？什麼不起作用？請記住，這個網站上的人是真實的人，如果沒有你告訴我們，你就會無法猜測你的想法。我們不會只看一眼你的代碼，並能看到它的問題，我們也不會把它「回到我們的桌子上」，花幾個小時試圖弄清楚如何使它工作。這個網站是關於*特定的*問題。 –

那麼代碼被徹底打破了，那裏有1個以上的問題，我真的期待着一個不同的方法，然後我的人我真的不需要人工處理我的代碼，因爲它太糟糕了，我仍然是初學者，而我張貼它只是爲了告訴你，我盡我所能，但無法使其工作。 – KOPEUE

我誤解的問題。開始這個答案。

讓我們以另一種方式說明問題。

我們有一些項目，十五。

我們有一些數字，比如說0，1，2

我們要知道什麼是X零，Y者和z三三兩兩的組合，使得X + Y + Z = 15和X ，y和z都至少有一個。

因此，將其降低到一個更容易的問題。假設有一個零。 現在你能解決更容易的問題嗎？問題現在變小了：現在的問題是「生成所有具有至少一個1和2的長度爲14的序列」。你看到如何解決更容易的問題？

如果不是，將其分解成更簡單的問題。假設有一個1.你現在能解決問題嗎？現在的問題是要找到其中有13個2的序列，並且只有其中的一個。

現在假設有兩個1。你能解決那裏的問題嗎？

您是否看到了如何使用解決方案解決較爲簡單的問題以解決較難的問題？

來源

2016-04-05 19:45:56

據我瞭解，你建議我創建一個列表，包含所有當前已知的解決方案的特定長度，並遞歸添加更多內容。我可能是完全錯誤的，但即使我不是，我不知道我該如何執行它.. – KOPEUE

@KOPEUE：不要擔心此時的列表的實現細節。您需要能夠在紙上解決小問題。例如，寫下從數字0,1,2中得出的長度爲3的所有解。其中並不是很多。現在，給出解決方案列表，描述如何將其轉換爲長度爲四的解決方案列表。通過手工解決問題，瞭解如何通過計算機解決問題。 –

@KOPEUE：在這裏，我會爲你做一個例子。 –

這樣一個簡單的策略與各種各樣的問題一起工作，就是按照字典順序列出可能性。在僞代碼中，您可以這樣做：

將V設置爲第一個可能的序列，按字典順序排列。
重複下列：
- 輸出V
- 如果可能，設置V到在詞典編纂順序的下一個序列。
- 如果這是不可能的，退出循環。

對於許多情況下，可以解決第二個子問題（「設置V至下一序列」）由V代表最右邊的「遞增的」價值向後搜索;也就是說，可以遞增的最右邊的值導致序列的可能前綴。一旦該值增加（按最小量），您可以找到以該前綴開頭的最小序列。（這是第一個子問題的簡單概括：「找到最小序列」）。

在這種情況下，這兩個子問題都很簡單。

如果值不是集合中的最大數字並且與前一個值相同，則該值是可遞增的。它只能增加到集合中下一個較大的值。
要找到以k結尾的前綴開頭的最小序列，請首先找到該集合中大於k的所有值，然後在序列的末尾放置它們。然後用k填充前綴（如果有）後的其餘值。

要將此方法應用於不同的枚舉問題，請參閱https://stackoverflow.com/a/30898130/1566221。這也是next_permutation標準實施的精髓所在。

來源

2016-04-05 20:47:40 rici

C＃查找數字的所有可能組合

回答

相關問題