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: }