Integer-Array variabler Größe mit Zahlen befüllen (Schleifen)

[Dibelius]

Hallo Gemeinde,

ich grüble nun schon eine Weile an dem Problem, aber der Reihe nach.

Zielstellung: Ich möchte Integer-Arrays erzeugen, die Kombinationen widerspiegeln sollen (und diese später als Schlüssel in einem Map-Objekt ablegen; bereits implementiert).

Es gibt dabei drei Faktoren, die variieren können:

• Array-Länge, es gibt aber ein bekanntes Maximum (depth)
  
• maximale Summe aller Werte im Array (sumCap)
• Höchstgrenze für jeden einzelnen Integer-Wert (valueCap)

Beispielausgabe: depth = 3, sumCap = 4, valueCap = 2

// Für eine Zahl
[0, 0, 0]
[0, 0, 1]
[0, 0, 2] // valueCap bei [2] erreicht
[0, 1, 0]
[0, 2, 0] // valueCap bei [1] erreicht
[1, 0, 0]
[2, 0, 0] // valueCap bei [0] erreicht
// Für zwei Zahlen
[0, 1, 1]
[0, 2, 1] // valueCap bei [1] erreicht
[1, 0, 1]
[2, 0, 1] // valueCap bei [0] erreicht
// ...
// Für drei Zahlen
[1, 1, 2] // valueCap bei [2] erreicht, sumCap erreicht
// ...
[2, 0, 2] // valueCap bei [0] und [2] erreicht, sumCap erreicht
// Nicht möglich sind z.B.
[1, 0, 3] // valueCap bei [2] überschritten, sumCap erreicht
[0, 0, 4] // valueCap bei [2] überschritten, sumCap erreicht
[2, 3, 0] // valueCap bei [0] erreicht, bei [1] überschritten, sumCap überschritten
// ...

Beispielausgabe: depth = 5, sumCap = 3, valueCap = 1 (Binärkombinationen)

// Für eine Zahl
[0, 0, 0, 0, 0]
[0, 0, 0, 0, 1] // valueCap bei [4] erreicht
[0, 0, 0, 1, 0] // valueCap bei [3] erreicht
// ...
// Für zwei Zahlen
[0, 0, 1, 0, 1] // valueCap bei [2] und [4] erreicht
[0, 1, 0, 0, 1] // valueCap bei [1] und [4] erreicht
// ...
// Für drei Zahlen
[0, 0, 1, 1, 1] // valueCap bei [2], [3] und [4] erreicht, sumCap erreicht
[0, 1, 0, 1, 1] // valueCap bei [1], [3] und [4] erreicht, sumCap erreicht
// Nicht möglich sind z.B.
[0, 1, 1, 1, 1] // sumCap überschritten
[0, 1, 0, 0, 2] // valueCap bei [4] überschritten, sumCap erreicht
// ...

Meine derzeitige Holzhammermethode für die Erzeugungsmethode sieht wiefolgt aus (mit besagtem Maximum der Array-Länge von 9):

   private Hashtable<int[], Integer> createReferenceTable(int depth, int sumCap, int valueCap)
   {
       Hashtable<int[], Integer> table   = new Hashtable<int[], Integer>   (1000, 0.75F);
       //Hashtable<ArrayList<Integer>, Integer> table   = new Hashtable<ArrayList<Integer>, Integer>   (1000, 0.75F);

       int[] pattern = new int[depth];
       //ArrayList<Integer>   pattern   = new ArrayList<Integer>(depth);

       for (int a = 0; a <= valueCap; a++)
       {
           pattern = createTableEntry(depth, sumCap, valueCap, a);
           if (pattern != null) table.put(pattern, new Integer(0));
           for (int b = 0; b <= valueCap; b++)
           {
               pattern = createTableEntry(depth, sumCap, valueCap, a,b);
               if (pattern != null) table.put(pattern, new Integer(0));
               for (int c = 0; c <= valueCap; c++)
               {
                   pattern = createTableEntry(depth, sumCap, valueCap, a,b,c);
                   if (pattern != null) table.put(pattern, new Integer(0));
                   for (int d = 0; d <= valueCap; d++)
                   {
                       pattern = createTableEntry(depth, sumCap, valueCap, a,b,c,d);
                       if (pattern != null) table.put(pattern, new Integer(0));
                       for (int e = 0; e <= valueCap; e++)
                       {
                           pattern = createTableEntry(depth, sumCap, valueCap, a,b,c,d,e);
                           if (pattern != null) table.put(pattern, new Integer(0));
                           for (int f = 0; f <= valueCap; f++)
                           {
                               pattern = createTableEntry(depth, sumCap, valueCap, a,b,c,d,e,f);
                               if (pattern != null) table.put(pattern, new Integer(0));
                               for (int g = 0; g <= valueCap; g++)
                               {
                                   pattern = createTableEntry(depth, sumCap, valueCap, a,b,c,d,e,f,g);
                                   if (pattern != null) table.put(pattern, new Integer(0));
                                   for (int h = 0; h <= valueCap; h++)
                                   {
                                       pattern = createTableEntry(depth, sumCap, valueCap, a,b,c,d,e,f,g,h);
                                       if (pattern != null) table.put(pattern, new Integer(0));
                                       for (int i = 0; i <= valueCap; i++)
                                       {
                                           pattern = createTableEntry(depth, sumCap, valueCap, a,b,c,d,e,f,g,h,i);
                                           if (pattern != null) table.put(pattern, new Integer(0));
                                       }
                                   }
                               }
                           }
                       }
                   }
               }
           }
       }

       return table;
   }

Validierung des übergebenen values-Arrays und Rückgabe, wenn alle drei Faktoren erfüllt:

   private int[] createTableEntry(int depth, int sumCap, int valueCap, int...values)
   {
       if (values != null && depth == values.length)
       {
           for (int v : values)
               if (v > valueCap) return null;
         
           sum = ExpArray.sum(values);
           if ( sum <= sumCap)
               return values;
       }
       return null;
   }

Meine kleine Helferfunktion für die Summenbildung

public class ExpArray
{
    // ...
    /**Sums up items of an integer array, optionally filters values.
     * @param arr        The array to be checked.
     * @param ex        Values to be filtered. If {@code null} all values are valid.
     * @return            Sum of valid items.
     */
    public static int sum(int[] arr, int... ex)
    {
        int sum = 0;
        if (arr != null) {
            for (int n : arr)
            {
                boolean valid = true;
                if (ex != null)
                    for (int e : ex)
                        if (n == e) {
                            valid = false;
                            break;
                        }
                if (valid) sum += n;
            }
        }
        return sum;
    }
    // ...
}

Es wird sicher deutlich, worauf ich hinaus will. Der Lösungsansatz funktioniert zwar, ist aber alles andere als elegant und die Berechnungszeiten für die Schleifendurchläufe sind spürbar.

Ich denke vielleicht an eine rekursive Möglichkeit und hatte auch einen anderen Lösungsansatz für die Variable pattern vom Typ ArrayList, sodass sich die Größe variabel anpasst, je nach Iteration von depth, kam damit aber auch nicht viel weiter.

Hat jemand eine Idee dazu?

Ein Denkanstoß genügt mir an dieser Stelle, kein fertiger Code.