Algorithmus gesucht um bestimmte Kobinationen zu erzeugen

Ich möchte eine Liste von Listen von werten generieren. Dabei gebe ich an, wie lang die innere Liste ist. Was genau da generiert werden soll kann ich nur anhand von Beispielen Zeigen, da ich es derzeit nicht in Worte packen kann.

Erstmal ein paar Beispiele für mögliche Ergebnisse (andere wären auch Möglich, siehe weiter Unten): Sagen wir ich gebe 1 als Länge an, dann soll nur eine Liste, die nur die 0 enthält herauskommen. Wenn ich 2 angebe soll [0,0] und [0,1] herauskommen. Bei 3 soll [0,0,0], [0,0,1] und [0,1,2] herauskommen. Bei 4 soll [0,0,0,0], [0,0,0,1], [0,0,1,1],[0,0,1,2],[0,1,2,3] herauskommen.

Nochmal das Beispiel mit 3. Hier gibt es den Fall, alle gleich, einer anders als die anderen oder alle drei verschieden. Für 3 wäre also als Ergebnis auch [0,0,0],[0,1,0], [0,1,2] OK. [0,0,0] => alle gleich, es ginge Theoretisch aber auch [1,1,1] oder [2,2,2] aber ich hätte gerne die kleinst mögliche Zahl größer oder gleich 0. [0,0,1] => einer anders. Es ginge also auch [0,0,2] oder [1,0,0] oder [3,9,3], aber ich hätte gerne wieder die kleinst möglichen Zahlen verwendet.

Ich hab mir das auch mal so aufgeschrieben, komme aber dennoch nicht auf einen sinnvollen Algorithmus:

1 => (1)
2 => (2), (1:1)
3 => (3), (1:2), (1:1:1)
4 => (4), (1:3), (2:2), (1:1:2), (1:1:1:1)

Irgendwie könnte man vielleicht die Zahl in alle möglichen Summen aus natürlichen Zahlen zerlegen. Das dürfte dann meine gewünschte Lösung ergeben denke ich, aber wie könnte man das effizient erledigen?

vergesst den letzten Satz. Das ist Käse.

OK, ich habs geschafft:

public static List<List<int>> GenerateNumbers(int ruleCount)
        {
            var combinations = GeneratePartitionings(5);
            var mapped = combinations.Select(x => GenerateNumbersFromPartitioning(x));
            return mapped.ToList();
        }

        private static List<int> GenerateNumbersFromPartitioning(List<int> item)
        {
            var result = new List<int>();
            for (int i = 0; i < item.Count; i++)
            {
                for (int j = 0; j < item[i]; j++)
                {
                    result.Add(i);
                }
            }
            return result;
        }

        private  static List<List<int>> GeneratePartitionings(int n)
        {
            if (n == 1)
                return new List<List<int>> { new List<int> { 1 } };

            var result = new List<List<int>> { new List<int> { n } };
            for (int i = 1; i < n; i++)
            {
                var combinations = GeneratePartitionings(i)
                    .Where(c => !c.Any(x => x > n - i));

                foreach (var item in combinations)
                {
                    var tmp = new List<int> { n - i };
                    tmp.AddRange(item);
                    result.Add(tmp);
                }
            }

            return result;
        }

cooky451

hm.. ?

void wtf(std::size_t val, std::vector<std::vector<std::size_t>>& buf)
{
  buf.clear();
  buf.resize(val);
  for (std::size_t i = 0; i < val; ++i)
  {
    buf[i].resize(val);
    for (std::size_t j = 0; j < i; ++j)
    {
      buf[i][val - j - 1] = i - j;
    }
  }
}