Durchzählen

Ich weiß nicht, ob es jemanden interessieren wird, zumal ich in diesem Blog selten über Programmierung schreibe und es daher vielleicht nicht ganz hineinpasst. Aber: Ich stehe oft an, wenn ich ein kombinatorisches Problem habe und alle Möglichkeiten systematisch durchprobieren will. Da habe ich anscheinend einen Knoten im Kopf, dabei geht es eigentlich ganz einfach. Hier der Code, den ich heute geschrieben habe, aus einem Programm, mit dem ich ein Beispiel aus www.brilliant.org zu lösen versucht habe:

int countup (int x)
{
  number[x]++;

  if (eval (price) > max_price)
  {
    if (x == n - 1)
      return -1;
    for (int i = 0; i <= x; i++)
      number[i] = 0;
    return countup (x + 1);
  }

  return 0;
}

Dieser Code dient dazu, den Array number systematisch hochzuzählen, wobei es hier nicht so ist, dass man genau weiß, bis zu welcher Zahl man jedes einzelne Element des Arrays hochzählen kann, sondern dass dies vom Ergebnis der Funktion eval, aufgerufen mit dem Parameter price, abhängt. Das macht das Ganze etwas komplizierter. Im Normalfall wird man anstelle von eval (price) > max_price möglicherweise mit einer anderen (einfacheren) Bedingung arbeiten können. 

Im Hauptprogramm verwende ich diese Funktion in der folgenden Schleife:

  do {
    if (sum_numbers () <= 3)
    {
      e = eval (yummy);
      if (e > max)
      {
        max = e;
        print_selection ();
      }
    }
    ptr = countup (ptr);
  } while (ptr != -1);

Hierdurch gehe ich systematisch alle möglichen Kombinationen durch und überprüfe, ob sie die gegebenen Anforderungen erfüllen, beziehungsweise stelle fest, welche die Zielfunktion (eval (yummy)) maximiert.

Ich hoffe, der Code werde manchen nützlich sein, die ähnliche Probleme zu lösen haben wie ich.