He estado luchando con este problema bastante complicado durante la semana pasada :( Tengo que encontrar todas las combinaciones de números que suman un número natural dado usando la recursividad. No tengo permitido usar LINQ ni nada más que "usar el sistema "
Por ejemplo, si la entrada es 7, la salida debería verse así:
1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 1 + 1 + 1 + 1 + 1 2 + 2 + 1 + 1 + 1 2 + 2 + 2 + 1 3 + 1 + 1 + 1 + 1 3 + 2 + 1 + 1 3 + 2 + 2 3 + 3 + 1 4 + 1 + 1 + 1 4 + 2 + 1 4 + 3 5 + 1 + 1 5 + 2 6 + 1Los números de la combinación deben enumerarse exactamente en ese orden, por lo que para una entrada de 3, por ejemplo, la salida debe ser exactamente como sigue:
1 + 1 + 1 2 + 1Para una entrada de 4, la salida debería verse así:
1 + 1 + 1 + 1 2 + 1 + 1 2 + 2 3 + 1Para cada nueva lista de combinaciones incrementamos el primer número de la lista y luego continuamos con la parte restante de la lista anterior hasta que la suma sea igual a la entrada.
Solo se permiten números positivos entre 1 (1 incluido) y la entrada - 1.
Mi código hasta ahora me da el siguiente resultado para la misma entrada dada de 7:
+ 1 + 1 + 1 + 2 + 1 + 1 + 1 + 2 + 2 + 3 + 1 + 1 + 1 + 1 + 1 + 2 + 2 + 1 + 1 + 1 + 2 + 2 + 2 + 1 + 3 + 3 + 4 + 1 + 1 + 1 + 1 + 1 + 2 + 1 + 1 + 1 + 2 + 2 + 3 + 2 + 1 + 1 + 1 + 2 + 1 + 1 + 1 + 2 + 2 + 3 ...¿Me pueden ayudar con algunas sugerencias?
static string GenerateCombinations(int n) { string combinationList = ""; for (int index = 1; index < n - 1; index++) { string intermediaryList = GenerateCombinations(n - index, index) + " + " + index; combinationList += intermediaryList; } return combinationList + "\n"; } static string GenerateCombinations(int n, int index) { string combinationList = ""; for (int i = 1; i < n - 1; i++) { if (i <= index) { string intermediaryList = GenerateCombinations(n) + " + " + index; combinationList += intermediaryList; } } return combinationList; } static void Main() { int n = Convert.ToInt32(Console.ReadLine()); Console.WriteLine(GenerateCombinations(n)); }Intenta lo siguiente:
class Program { static List<string> combinationList = new List<string>(); const int SUM = 7; static void Main(string[] args) { List<int> numbers = new List<int>(); GenerateCombinations(numbers, 0); combinationList.Sort(); Console.WriteLine(string.Join("\n", combinationList)); Console.ReadLine(); } static void GenerateCombinations(List<int> numbers, int sum) { int start = 1; if (numbers.Count > 0) start = numbers[0]; for (int i = start; i <= SUM; i++) { int newSum = sum + i; if (newSum > SUM) break; List<int> newList = new List<int>(numbers); newList.Insert(0,i); if (newSum == SUM) { combinationList.Add(string.Join(" + ", newList)); break; } else { GenerateCombinations(newList, newSum); } } } }Como está buscando una solución recursiva, hagámoslo recursivamente sin Linq y otros medios.
Comencemos desde lo básico: cuando se da 0 , tenemos una solución vacía:
private static int[][] Solutions(int value) { if (value <= 0) return new int[][] { new int[0] }; //TODO: other cases for 1, 2, ... } Es hora de hacer el siguiente paso: si sabemos cómo resolver para algunos n - 1 ( n - 1 >= 0 ) podemos resolver para n de la siguiente manera: todas las soluciones comienzan desde m ( m < n ) están en forma
`m + solutions for n - m which uses m .. 1 only`P.ej
6 + 1 <- starts from 6, solves for 7 - 6 = 1, uses 6..1 only 5 + 2 ... 5 + 1 + 1 4 + 3 4 + 2 + 1 4 + 1 + 1 + 1 ... 3 + 3 + 1 <- starts from 3, solves for 7 - 3 = 4, uses 3..1 only 3 + 2 + 2 <- starts from 3, solves for 7 - 3 = 4, uses 3..1 only 3 + 2 + 1 + 1 <- starts from 3, solves for 7 - 3 = 4, uses 3..1 only 3 + 1 + 1 + 1 + 1 ... 2 + 2 + 2 + 1 2 + 2 + 1 + 1 + 1 2 + 1 + 1 + 1 + 1 + 1 ... 1 + 1 + 1 + 1 + 1 + 1 + 1 <- starts from 1, solves for 7 - 1 = 6, uses 1..1 onlyEsta recursividad se puede codificar como
private static int[][] Solutions(int value, int startWith = -1) { if (value <= 0) return new int[][] { new int[0] }; if (startWith < 0) startWith = value - 1; List<int[]> solutions = new List<int[]>(); for (int i = Math.Min(value, startWith); i >= 1; --i) foreach (int[] solution in Solutions(value - i, i)) { int[] next = new int[solution.Length + 1]; Array.Copy(solution, 0, next, 1, solution.Length); next[0] = i; solutions.Add(next); } // Or just (if we are allow a bit of Linq) // return solutions.ToArray(); int[][] answer = new int[solutions.Count][]; for (int i = 0; i < solutions.Count; ++i) answer[i] = solutions[i]; return answer; }Manifestación
var result = Solutions(7); // A pinch of Linq for demonstration string report = string.Join(Environment.NewLine, result .Select(solution => string.Join(" + ", solution))); Console.Write(report);Salir:
6 + 1 5 + 2 5 + 1 + 1 4 + 3 4 + 2 + 1 4 + 1 + 1 + 1 3 + 3 + 1 3 + 2 + 2 3 + 2 + 1 + 1 3 + 1 + 1 + 1 + 1 2 + 2 + 2 + 1 2 + 2 + 1 + 1 + 1 2 + 1 + 1 + 1 + 1 + 1 1 + 1 + 1 + 1 + 1 + 1 + 1Aquí hay una solución que no usa colecciones (solo using System; ) y genera la salida en el orden requerido.
public static void PrintCombinations(int n) { PrintRest("", 0, n, n - 1); } private static void PrintRest(string listStart, int startSum, int n, int max) { for (int i = 1; i <= max; i++) { string list = listStart.Length > 0 ? listStart + " + " + i.ToString() : i.ToString(); int sum = startSum + i; if (sum == n) { Console.WriteLine(list); } else if (sum < n) { PrintRest(list, sum, n, i); } } }Lo llamarías como
PrintCombinations(7); Comienza tomando todos los sumandos iniciales posibles y llamándose a sí mismo para construir el resto de la suma. Las combinaciones hasta el punto actual se pasan como parámetro de cadena listStart . La suma que representa se pasa como int startSum . La suma objetivo es n . max es el mayor sumando permitido.