1:  /*
   2:   * KAMM
   3:   * Berechnung perfekter Lineale der Länge L mit S Segmenten.
   4:   *
   5:   * Basierend auf einem Algorithmus und dem Programm kamm.c
   6:   * von Klaus Nagel vom 2003/01/11
   7:   * Aber mit Modifikationen! Es können also sich Fehler
   8:   * eingeschlichen haben, die im ursprünglichen Algorithmus
   9:   * nicht waren!
  10:   *
  11:   * @author Peter Luschny  2003/01/12
  12:   * bearbeitet am 2005/02/2005
  13:   * 
  14:   * Hintergrundinformationen findet man auf:
  15:   * http://www.luschny.de/math/rulers/prulers.html
  16:   */
  17:   
  18:  package org.dsmath.combi.rulers;
  19:   
  20:  import java.io.PrintWriter;
  21:  import java.io.FileWriter;
  22:  import java.io.BufferedWriter;
  23:  import java.io.IOException;
  24:  import java.util.Arrays;
  25:   
  26:  public class Kamm  {
  27:   
  28:  PrintWriter report;     // Ausgabedatei
  29:  private int[][] kiste;  // Kammkiste
  30:  private int limit;      // L - B(M,2)
  31:  private int anzRekurs;  // Zähler für rekursive Aufrufe
  32:  private int anzKaemme;  // Zähler der erzeugten Kaemme
  33:  private int alleKaemme; // Zähler für alle Kämme (inkl. Spiegel)
  34:  private int L, M;       // Kammparameter
  35:   
  36:  private final int[] Seg = new int [] {
  37:        1, 1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 5, 6,
  38:        6, 6, 6, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8,
  39:        9, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10,
  40:        10, 11, 11, 11, 11, 11, 11, 11 };
  41:   
  42:  /** 
  43:   *  Die rekursive Funktion von Klaus Nagel.
  44:   *  Die Marken markPos[0] bis markPos[nextPos-1] sind gesetzt
  45:   *  markPos[nextPos] soll ermittelt werden.
  46:   */
  47:  private void Nagel(int[] markPos, int[] multiMess, int nextPos, int ueberSchuss)
  48:  {
  49:     anzRekurs++;
  50:   
  51:     boolean[] cand = new boolean[L + 1];
  52:   
  53:     // Die grösste fehlende Länge suchen
  54:     for (int miss = L - 2; miss > 1; miss--)
  55:     {
  56:        if (multiMess[miss] == 0)
  57:        {
  58:           // Im Feld cand die Kandidaten markieren
  59:           for (int i = 0; i < nextPos; i++)
  60:           {
  61:              int pos = markPos[i] + miss;
  62:              if (pos < L) { cand[pos] = true; }
  63:   
  64:              pos = markPos[i] - miss;
  65:              if (pos > 1) { cand[pos] = true; }
  66:           }
  67:   
  68:           for (int i = 2; i < L; i++)
  69:           {
  70:              if (cand[i])
  71:              {
  72:                 markPos[nextPos] = i;
  73:                 int[] nextMulti = multiMess.clone();
  74:   
  75:                 // Der Lineal-Typ: Eine Länge kann
  76:                 // mehrfach gemessen werden.
  77:                 int UeberSchuss = ueberSchuss;
  78:                 for (int j = 0; j < nextPos; j++)
  79:                 {
  80:                    // Die markPos[i] sind nicht notwendig aufsteigend
  81:                    int d = i - markPos[j];
  82:                    if (d < 0) { d = -d; }
  83:                    if (++nextMulti[d] > 1) { UeberSchuss++; }
  84:                 }
  85:   
  86:                 if (UeberSchuss <= limit)
  87:                 {
  88:                    // Hier ist der rekursive Aufruf!!
  89:                    Nagel(markPos, nextMulti, nextPos + 1, UeberSchuss);
  90:                 }
  91:              }
  92:           }
  93:           return;
  94:        }
  95:     }
  96:   
  97:     // Lösung, denn es wurde keine fehlende Länge gefunden
  98:     int[] neuKamm = new int[M - 1];
  99:   
 100:     for (int i = 0; i < M; i++) { cand[markPos[i]] = true; }
 101:   
 102:     // erzeuge Differenzendarstellung des Kamms
 103:     int j = 0, k = 0;
 104:     for (int i = 1; i <= L; i++)
 105:     {
 106:        if (cand[i])
 107:        {
 108:           neuKamm[k++] = i - j;
 109:           j = i;
 110:        }
 111:     }
 112:   
 113:     addKiste(neuKamm);
 114:  }
 115:   
 116:  private boolean addKiste(int[] neuKamm)
 117:  {
 118:        int len = neuKamm.length - 1;
 119:   
 120:        // falls es nicht der kleinere Kamm ist,
 121:        // dann spiegel ihn
 122:        for (int k = 0; k < len; k++)
 123:        {
 124:           if (neuKamm[k] < neuKamm[len - k])
 125:           {
 126:              break;
 127:           }
 128:   
 129:           if (neuKamm[k] != neuKamm[len - k])
 130:           {
 131:              // spiegeln
 132:              for (int j = (len - 1) >> 1; j >= 0; --j)
 133:              {
 134:                 int temp = neuKamm[j];
 135:                 neuKamm[j] = neuKamm[len - j];
 136:                 neuKamm[len - j] = temp;
 137:              }
 138:              break;
 139:           }
 140:        }
 141:   
 142:        for (int i = anzKaemme - 1; i >= 0; --i)
 143:        {
 144:           int[] kamm = kiste[i];
 145:           int k = len;
 146:   
 147:           // kamm[0] ist immer 1
 148:           while ((k > 0) && (neuKamm[k] == kamm[k])) { k--; }
 149:   
 150:           // neuKamm ist schon vorhanden
 151:           if (k == 0) { return false; }
 152:        }
 153:   
 154:        kiste[anzKaemme++] = neuKamm;
 155:        return true;
 156:  }
 157:   
 158:  private void speicherKaemme()
 159:  {
 160:     int n = 1;
 161:     for(int i = 0; i < anzKaemme; i++)
 162:     {
 163:        int[] a = DiffToMarken(kiste[i]);
 164:        int[] b = DiffToSpiegel(kiste[i]);
 165:   
 166:        report.print("Nr " + (n++) + ": ");
 167:        report.print(Arrays.toString(a));
 168:        report.println(Arrays.toString(b));
 169:     }
 170:   
 171:     report.print("(" + (M-1) + "," + L + ") -> " + alleKaemme);
 172:     report.println(", Rekursionen: " + anzRekurs);
 173:     report.println();
 174:     report.flush();
 175:  }
 176:   
 177:  private int[] DiffToMarken(final int[] b)
 178:  {
 179:     int[] a = new int[b.length + 1];
 180:     int s = 0;
 181:   
 182:     for(int i = 0; i < b.length; i++)
 183:     {
 184:        s = s + b[i];
 185:        a[i+1] = s;
 186:     }
 187:     return a;
 188:  }
 189:   
 190:  private int[] DiffToSpiegel(final int[] b)
 191:  {
 192:     int[] a = new int[b.length + 1];
 193:     int s = 0, j = 1;
 194:   
 195:     for(int i = b.length - 1; i >= 0; --i)
 196:     {
 197:        s = s + b[i];
 198:        a[j++] = s;
 199:     }
 200:     return a;
 201:  }
 202:   
 203:  private final int[] anz = new int[] {1,1,1,2,3};
 204:   
 205:  /*
 206:   * Der Einstiegspunkt in die Klasse Kamm.
 207:   * Es werden die perfekten Kaemme = Lineale
 208:   * der Länge Len erzeugt, gespeichert und
 209:   * ihre Anzahl zurückgegeben.
 210:   */
 211:  public int perfekteKaemme(int Len)
 212:  {
 213:     this.M = Seg[Len] + 1;
 214:     this.L = Len;
 215:   
 216:     anzKaemme = 0;
 217:   
 218:     int[] markPos = new int[Math.max(M, 3)];
 219:     markPos[0] = 0; // Die Marken 0 und L müssen
 220:     markPos[1] = 1; // für die Länge L gesetzt sein
 221:     markPos[2] = L; // obdA für die Länge L-1
 222:   
 223:     int[] multiMess = new int[L + 1];
 224:     multiMess[1] = 1;
 225:     multiMess[L] = 1;
 226:     multiMess[L-1] = 1;
 227:   
 228:     anzRekurs = 0;
 229:     limit = ((M - 1) * M) / 2 - L;
 230:   
 231:     Nagel(markPos, multiMess, 3, 0);
 232:   
 233:     alleKaemme = L < 5 ? anz[L] : 2 * anzKaemme;
 234:     speicherKaemme();
 235:   
 236:     return alleKaemme;
 237:  }
 238:   
 239:  public Kamm()
 240:  {
 241:     // Diese Kiste ist gross genug bis mindestens n=138.
 242:     kiste = new int [16000][];
 243:     try  {
 244:        report = new PrintWriter(
 245:                 new BufferedWriter(
 246:                 new FileWriter("rulers.txt", true)));
 247:     }
 248:     catch (IOException e) {
 249:        System.err.println(e.toString());
 250:        return;
 251:     }
 252:  }
 253:   
 254:  public static void main(String[] args)
 255:  {
 256:     long elapsed, start, stop;
 257:   
 258:     Kamm k = new Kamm();
 259:   
 260:     // Fuer einen grösserer Rechenbereich bedarf
 261:     // es der Erweiterung des Feldes Seg[].
 262:     for(int len = 1; len < 51; len++)
 263:     {
 264:        start = System.currentTimeMillis();
 265:   
 266:        int anzahl = k.perfekteKaemme(len);
 267:   
 268:        stop = System.currentTimeMillis();
 269:        elapsed = stop - start;
 270:        System.out.println(len + " -> " + anzahl
 271:                         + " Sek. " + elapsed / 1000.0);
 272:     }
 273:     System.out.println("E N D E");
 274:  }
 275:  }