Optimal Algorithmus

Question

Ich habe einen Eingang, "N", ich muss die Nummer der Liste der Länge N finden, die mit 1 beginnt, so dass die nächste Nummer höchstens 1 mehr als die maximale Anzahl hinzugefügt wird bis jetzt. Zum Beispiel

N = 3, mögliche Listen => (111, 112, 121, 122, 123), [113, oder 131 ist nicht möglich, während beim Hinzufügen von "3" zur Liste die maximale Anzahl in die Liste wäre '1', also können wir nur 1 oder 2 hinzufügen].

N = 4, die Liste 1213 ist möglich, während beim Hinzufügen von 3 die maximale Anzahl in der Liste '2' ist, also können 3 hinzugefügt werden.

Problem ist, die Anzahl solcher Listen für einen gegebenen Eingang "N" zu zählen.

Mein Code ist: -

public static void Main(string[] args) 
     { 
      var noOfTestCases = Convert.ToInt32(Console.ReadLine()); 
      var listOfOutput = new List<long>(); 
      for (int i = 0; i < noOfTestCases; i++) 
      { 
       var requiredSize = Convert.ToInt64(Console.ReadLine()); 
       long result; 
       const long listCount = 1; 
       const long listMaxTillNow = 1; 
       if (requiredSize < 3) 
        result = requiredSize; 
       else 
       { 
        SeqCount.Add(requiredSize, 0); 
        AddElementToList(requiredSize, listCount, listMaxTillNow); 
        result = SeqCount[requiredSize]; 
       } 
       listOfOutput.Add(result); 
      } 
      foreach (var i in listOfOutput) 
      { 
       Console.WriteLine(i); 
      } 
     } 

     private static Dictionary<long, long> SeqCount = new Dictionary<long, long>(); 

     private static void AddElementToList(long requiredSize, long listCount, long listMaxTillNow) 
     { 
      if (listCount == requiredSize) 
      { 
       SeqCount[requiredSize] = SeqCount[requiredSize] + 1; 
       return; 
      } 
      var listMaxTillNowNew = listMaxTillNow + 1; 
      for(var i = listMaxTillNowNew; i > 0; i--) 
      { 
       AddElementToList(requiredSize, listCount + 1, 
        i == listMaxTillNowNew ? listMaxTillNowNew : listMaxTillNow); 
      } 
      return; 
     } 

Welches ist die Brute-Force-Methode. Ich möchte wissen, was der beste Algorithmus für das Problem sein könnte? PS: Ich möchte nur die Anzahl solcher Listen wissen, also bin ich sicher, dass die Erstellung der Liste nicht erforderlich ist. (Die Art, wie ich im Code tue) Ich bin überhaupt nicht gut in Algorithmen, also bitte Entschuldigung für die lange Frage.

Answer 1

Dieses Problem ist ein klassisches Beispiel eines dynamischen Programmierproblem:

Wenn Sie eine Funktion dp (k, m) definiert die Anzahl der Listen der Länge k sein, für die die maximale Anzahl m ist, können Sie dann haben eine Rekursion:

dp(1, 1) = 1 
dp(1, m) = 0, for m > 1 
dp(k, m) = dp(k-1, m) * m + dp(k-1, m-1) 

der Tat gibt es nur eine Liste der Länge 1 und die maximale Element 1. Wenn Sie mit max Element m eine Liste der Länge k bauen, können Sie eine der nehmen kann (k-1) -Listen mit max = m und append 1 oder 2 oder .... oder m. Oder Sie können eine (k-1) -Liste mit max Element m-1 nehmen und m anhängen. Wenn Sie eine (k-1) -Liste mit max Element kleiner als m-1 nehmen, dann können Sie nach Ihrer Regel nicht mehr als m erhalten, indem Sie nur ein Element anhängen.

Sie können dp (k, m) für alle k = 1, ..., N und m = 1, ..., N + 1 mit dynamischer Programmierung in O(N^2) berechnen und dann wäre die Antwort auf Ihre Frage

dp(N,1) + dp(N,2) + ... + dp(N,N+1) 

Also ist der Algorithmus O(N^2).

---

Siehe unten für die Umsetzung von dp Berechnung in C#:

 int[] arr = new int[N + 2]; 
     for (int m = 1; m < N + 2; m++) 
      arr[m] = 0; 
     arr[1] = 1; 

     int[] newArr = new int[N + 2]; 
     int[] tmp; 
     for (int k = 1; k < N; k++) 
     { 
      for (int m = 1; m < N + 2; m++) 
       newArr[m] = arr[m] * m + arr[m - 1]; 
      tmp = arr; 
      arr = newArr; 
      newArr = tmp; 
     } 

     int answer = 0;strong text 
     for (int m = 1; m < N + 2; m++) 
      answer += arr[m]; 

     Console.WriteLine("The answer for " + N + " is " + answer); 

Answer 2

Nun, ich durch ein Feuer an diesem Nachmittag (wirklich!) Unterbrochen wurde, aber FWIW, hier ist mein Beitrag:

/* 
    * Counts the number of possible integer list on langth N, with the 
    * property that no integer in a list(starting with one) may be more 
    * than one greater than the greatest integer preceeding it in the list. 
    * 
    * I am calling this "Semi-Factorial" since it is somewhat similar to 
    * the factorial function and its constituent integer combinations. 
    */ 
    public int SemiFactorial(int N) 
    { 
     int sumCounts = 0; 

     // get a list of the counts of all valid lists of length N, 
     //whose maximum integer is listCounts[maxInt]. 
     List<int> listCounts = SemiFactorialCounts(N); 

     for (int maxInt = 1; maxInt <= N; maxInt++) 
     { 
      // Get the number of lists, of length N-1 whose maximum integer 
      //is (maxInt): 
      int maxIntCnt = listCounts[maxInt]; 

      // just sum them up 
      sumCounts += maxIntCnt; 
     } 

     return sumCounts; 
    } 

    // Returns a list of the counts of all valid lists of length N, and 
    //whose maximum integer is [i], where [i] is also its index in this 
    //returned list. (0 is not used). 
    public List<int> SemiFactorialCounts(int N) 
    { 
     List<int> cnts; 
     if (N == 0) 
     { 
      // no valid lists, 
      cnts = new List<int>(); 
      // (zero isn't used) 
      cnts.Add(0); 
     } 
     else if (N == 1) 
      { 
       // the only valid list is {1}, 
       cnts = new List<int>(); 
       // (zero isn't used) 
       cnts.Add(0); 
       //so that's one list of length 1 
       cnts.Add(1); 
      } 
      else 
      { 
      // start with the maxInt counts of lists whose length is N-1: 
      cnts = SemiFactorialCounts(N - 1); 

      // add an entry for (N) 
      cnts.Add(0); 

      // (reverse order because we overwrite the list using values 
      // from the next lower index.) 
      for (int K = N; K > 0; K--) 
      { 
       // The number of lists of length N and maxInt K { SF(N,K) } 
       // Equals K times # of lists one shorter, but same maxInt, 
       // Plus, the number of lists one shorter with maxInt-1. 
       cnts[K] = K * cnts[K] + cnts[K - 1]; 
      } 
     } 

     return cnts; 
    } 

ziemlich ähnlich wie die anderen. Obwohl ich diese "klassische dynamische Programmierung" nicht so sehr als "klassische Rekursion" bezeichnen würde.