Hallo, allerseits,
man könnte sich fragen, wie gut die "greedy"-Folge an einer wirklich
längsten Folge von Zahlen <= n liegt, die der gestellten Bedingung
genügt.
Solche Folgen habe ich mit "sage" über ein Backtracking ermittelt,
wie zu erwarten war, ging der Rechner schon ab n=20 in die Knie :)
Da bin ich auf C umgestiegen (ja, ich habe gerade Zeit :) ), was
um einen Faktor >100 schneller ist.
Daß ich die Sache erst in sage (d.h. im wesentlichen Python um
bequeme Mengen-Operationen erweitert)implementiert habe, war dabei
Gold wert - vermutlich wäre ich ohne die Möglichkeit, die Ausgaben
zu vergleichen, beim Testen verzweifelt.
Post by Rainer RosenthalPost by Rainer RosenthalPost by Marcel Muellerich bin auf der Suche nach einer Reihe möglichst dichter ganzer
Zahlen, deren Elemente sich /nicht/ als Summen oder Differenzen von
maximal /drei/ anderen Elementen der Reihe darstellen lassen.
1, 2, 4, 8, 15, 26, 44, 64, 84, 115, 162, 209, 259, 296, 333, 428, 482,
537, 604, 710, 843, 946, 1073, 1208, 1229, 1304, 1520, 1704, 1806, 2096,
2189, 2426, 2660, 2817, 3190, 3544, 3747, 3940, 4403, 4556, 4806, 4907,
5191, 5439, 5801, 6241, 6437, 6816, 7166, 7752, 7809, 8246, 8392, 8547,
9221, 9666, 10512, 10850, 11615, 11941, 12747, 13093, 13664, 14287,
14965, 15384, 15737, 16996, 17310, 17889, 18672
Das waren gerade genug, um den Plot der Differenzen mit Vergnügen
anschauen zu können und den Sprung von 15737 auf 16996 zu bemerken.
[...]
Post by Rainer RosenthalJetzt wäre die Frage, ob der greedy-Ansatz überhaupt hilfreich ist für
die ursprüngliche Fragestellung.
Hier (nachdem mein Programm einen Tag lang gelaufen ist) die (modulo
Denk- und Programmierfehler) für gewisse Obergrenzen n (hier "lae"
genannt) längsten Folgen - aufgrund des Algorithmus wird die
lexikografisch kleinste Folge ausgegeben.
Hier schlägt das Kombinatorische Wachstum so ab n=70 zu, spätestens
ab da will man nicht mehr live zuschauen :)
Im berechneten Bereich scheint sich die "greedy"-Folge ganz gut zu
machen. Ab 44 geht es anscheinend um 1 länger, für 115 dauerte die
Rechnung 2.5 Stunden ...
Im Folgenden die Resultate, jeweils mit Obergrenze für n, der
maximalen Länge für eine "sperrige" Liste mit Zahlen <= n
und einer Beispiel-Liste.
lae: 1, max: 2, |0,1|
lae: 2, max: 2, |0,1|
lae: 3, max: 3, |0,2,3|
lae: 4, max: 3, |0,1,4|
lae: 5, max: 3, |0,1,4|
lae: 6, max: 3, |0,1,4|
lae: 7, max: 4, |0,4,5,7|
lae: 8, max: 4, |0,1,5,8|
lae: 9, max: 4, |0,1,5,8|
lae: 10, max: 4, |0,1,4,10|
lae: 11, max: 4, |0,1,4,10|
lae: 12, max: 5, |0,5,9,11,12|
lae: 13, max: 5, |0,4,10,11,13|
lae: 14, max: 5, |0,2,5,13,14|
lae: 15, max: 5, |0,2,5,13,14|
lae: 16, max: 5, |0,1,5,13,16|
lae: 17, max: 5, |0,1,4,10,17|
lae: 18, max: 5, |0,1,4,10,17|
lae: 19, max: 6, |0,7,11,16,17,19|
lae: 20, max: 6, |0,5,13,14,16,20|
lae: 21, max: 6, |0,2,12,13,18,21|
lae: 22, max: 6, |0,1,10,14,17,22|
lae: 23, max: 6, |0,1,8,13,19,23|
lae: 24, max: 6, |0,1,8,13,19,23|
lae: 25, max: 6, |0,1,5,14,17,25|
lae: 26, max: 6, |0,1,5,14,17,25|
lae: 27, max: 6, |0,1,5,14,17,25|
lae: 28, max: 6, |0,1,4,15,21,28|
lae: 29, max: 7, |0,4,10,17,26,28,29|
lae: 30, max: 7, |0,3,16,18,25,26,30|
lae: 31, max: 7, |0,3,16,18,25,26,30|
lae: 32, max: 7, |0,1,11,18,24,27,32|
lae: 33, max: 7, |0,1,9,14,26,30,33|
lae: 34, max: 7, |0,1,7,18,22,31,34|
lae: 35, max: 7, |0,1,7,18,22,31,34|
lae: 36, max: 7, |0,1,7,18,22,31,34|
lae: 37, max: 7, |0,1,5,14,26,34,37|
lae: 38, max: 7, |0,1,4,15,25,32,38|
lae: 39, max: 7, |0,1,4,15,25,32,38|
lae: 40, max: 8, |0,7,8,18,31,35,37,40|
lae: 41, max: 8, |0,1,10,16,29,34,37,41|
lae: 42, max: 8, |0,1,10,16,29,34,37,41|
lae: 43, max: 8, |0,1,10,16,29,34,37,41|
lae: 44, max: 8, |0,1,10,16,29,34,37,41|
lae: 45, max: 8, |0,1,10,16,29,34,37,41|
lae: 46, max: 8, |0,1,7,24,27,37,42,46|
lae: 47, max: 8, |0,1,7,24,27,37,42,46|
lae: 48, max: 8, |0,1,7,24,27,37,42,46|
lae: 49, max: 8, |0,1,6,22,31,35,46,49|
lae: 50, max: 8, |0,1,4,16,26,37,44,50|
lae: 51, max: 8, |0,1,4,16,26,37,44,50|
lae: 52, max: 8, |0,1,4,16,26,37,44,50|
lae: 53, max: 9, |0,8,18,25,38,47,49,52,53|
lae: 54, max: 9, |0,5,12,16,31,45,51,53,54|
lae: 55, max: 9, |0,2,14,29,36,46,49,54,55|
lae: 56, max: 9, |0,1,22,29,38,42,48,53,56|
lae: 57, max: 9, |0,1,22,29,38,42,48,53,56|
lae: 58, max: 9, |0,1,22,29,38,42,48,53,56|
lae: 59, max: 9, |0,1,15,27,34,38,51,56,59|
lae: 60, max: 9, |0,1,15,27,34,38,51,56,59|
lae: 61, max: 9, |0,1,10,26,40,43,48,55,61|
lae: 62, max: 9, |0,1,7,24,35,40,50,53,62|
lae: 63, max: 9, |0,1,6,26,35,45,48,59,63|
lae: 64, max: 9, |0,1,4,19,31,40,47,53,64|
lae: 65, max: 9, |0,1,4,17,28,40,50,59,65|
lae: 66, max: 9, |0,1,4,15,32,41,53,59,66|
lae: 67, max: 10, |0,9,15,23,34,50,60,62,63,67|
lae: 68, max: 10, |0,9,15,23,34,50,60,62,63,67|
lae: 69, max: 10, |0,4,24,37,43,54,59,66,68,69|
lae: 70, max: 10, |0,4,24,37,43,54,59,66,68,69|
lae: 71, max: 10, |0,1,21,27,38,52,56,61,68,71|
lae: 72, max: 10, |0,1,19,33,41,45,56,62,69,72|
lae: 73, max: 10, |0,1,19,33,41,45,56,62,69,72|
lae: 74, max: 10, |0,1,19,33,41,45,56,62,69,72|
lae: 75, max: 10, |0,1,19,33,41,45,56,62,69,72|
lae: 76, max: 10, |0,1,19,33,41,45,56,62,69,72|
lae: 77, max: 10, |0,1,8,28,40,53,59,63,74,77|
lae: 78, max: 10, |0,1,8,28,40,53,59,63,74,77|
lae: 79, max: 10, |0,1,7,31,42,54,57,70,75,79|
lae: 80, max: 10, |0,1,7,31,42,54,57,70,75,79|
lae: 81, max: 10, |0,1,4,15,37,46,58,64,71,81|
lae: 82, max: 10, |0,1,4,15,37,46,58,64,71,81|
lae: 83, max: 10, |0,1,4,15,37,46,58,64,71,81|
lae: 84, max: 11, |0,8,14,29,48,53,71,73,80,83,84|
lae: 85, max: 11, |0,7,20,29,32,62,66,67,77,83,85|
lae: 86, max: 11, |0,7,20,29,32,62,66,67,77,83,85|
lae: 87, max: 11, |0,4,13,28,42,48,64,75,82,85,87|
lae: 88, max: 11, |0,2,24,27,39,60,69,70,77,83,88|
lae: 89, max: 11, |0,1,11,29,34,48,65,73,80,86,89|
lae: 90, max: 11, |0,1,11,29,34,48,65,73,80,86,89|
lae: 91, max: 11, |0,1,11,29,34,48,65,73,80,86,89|
lae: 92, max: 11, |0,1,11,29,34,48,65,73,80,86,89|
lae: 93, max: 11, |0,1,9,23,48,53,59,74,86,90,93|
lae: 94, max: 11, |0,1,9,23,48,53,59,74,86,90,93|
lae: 95, max: 11, |0,1,9,23,48,53,59,74,86,90,93|
lae: 96, max: 11, |0,1,7,33,44,54,57,69,74,92,96|
lae: 97, max: 11, |0,1,7,33,44,54,57,69,74,92,96|
lae: 98, max: 11, |0,1,7,33,44,54,57,69,74,92,96|
lae: 99, max: 11, |0,1,6,22,47,56,67,82,86,96,99|
lae: 100, max: 11, |0,1,6,22,47,56,67,82,86,96,99|
lae: 101, max: 11, |0,1,6,22,47,56,67,82,86,96,99|
lae: 102, max: 11, |0,1,5,19,46,62,69,77,90,99,102|
lae: 103, max: 11, |0,1,5,19,46,62,69,77,90,99,102|
lae: 104, max: 11, |0,1,4,13,28,51,61,67,86,97,104|
lae: 105, max: 11, |0,1,4,13,28,51,61,67,86,97,104|
lae: 106, max: 11, |0,1,4,13,28,51,61,67,86,97,104|
lae: 107, max: 11, |0,1,4,13,28,51,61,67,86,97,104|
lae: 108, max: 12, |0,8,11,34,43,55,70,83,101,103,107,108|
lae: 109, max: 12, |0,7,32,52,65,74,82,93,103,105,108,109|
lae: 110, max: 12, |0,2,15,39,44,67,75,89,100,101,107,110|
lae: 111, max: 12, |0,2,15,39,44,67,75,89,100,101,107,110|
lae: 112, max: 12, |0,2,15,39,44,67,75,89,100,101,107,110|
lae: 113, max: 12, |0,2,15,39,44,67,75,89,100,101,107,110|
lae: 114, max: 12, |0,1,19,43,47,74,82,88,99,104,111,114|
lae: 115, max: 12, |0,1,19,43,47,74,82,88,99,104,111,114|
...
puh - leider etwas mageres Datenmaterial für Spekulationen,
vielleicht findet jemand noch einen pfiffigeren Algorithmus.
Z.B. wäre es interessant, inwiefern "sperrige" Listen zu n
existieren, die möglichst
Gruß,
Detlef
PS: Hier das Programm ... vermutlich nicht wirklich
durchschaubar.
In gcc kann man dankenswerterweise Arrays innerhalb einer
{...} Umgebung lokal mit einer Variablen als Dimension
deklarieren, das ist wohl kein Standard.
#include <stdio.h>
#include <stdlib.h>
// Gesucht wird eine möglichst lange Liste von ganzen, nicht
// negativen Zahlen aus {0, 1, ..., lae}, von denen sich keine
// als Summe oder Differenz von bis zu drei der übrigen Zahlen
// darstellen lässt.
// Globale Variablen (oh Grauß)
int lae=100;
// Konvention für Listen: Listenname groß, Länge klein geschrieben.
int *Lm; // bisher gefundene Liste maximaler Länge.
int lm; // deren Länge.
long found;
// Ausgabe einer Liste
void Lout(int *L, int l){
int i;
printf("|");
if(l>0) printf("%i",L[0]);
for(i=1; i<l; i++)
printf(",%i",L[i]);
printf("|\n");
fflush(stdout);
}
// comb1
// Liste der Summen und Differenzen von zwei Eingangslisten
// Eingabe: zwei sortierte Listen
// Ausgabe: sortierte Liste aller Elemente, sowie ihrer Summen
// und Differenzen im Bereich 0, ... , lae
// Hilfstabelle K1 global, um in dieser häufig aufgerufenen Routine
// nicht jedesmal neuen Speicher zu allozieren.
int *K1;
void comb1(int *L1, int l1, int *L2, int l2, int *R1, int *r1)
{
int i,j;
for(i=0; i<lae+1; i++) K1[i]=0;
for(i=0; i<l1; i++){
K1[L1[i]]=1;
for(j=0; j<l2 && L1[i]+L2[j]<=lae; j++){
K1[L1[i]+L2[j]]=1;
}
}
for(j=0; j<l2; j++){
K1[L2[j]]=1;
for(i=0; i<l1 && L1[i]<L2[j]; i++){
K1[L2[j]-L1[i]]=1;
}
for( ; i<l1; i++){
K1[L1[i]-L2[j]]=1;
}
}
j=0;
for(i=0;i<lae+1;i++){
if(K1[i]){
R1[j++]=i;
}
}
*r1=j;
}
// comb2
// Liste der Summen und Differenzen von je drei Elementen im
// betrachteten Bereich.
// Eingabe: sortierte Liste
// Ausgabe: sortierte Liste aller Elemente, sowie der Summen
// und Differenzen im Bereich 0, ... , lae
int *K2;
void comb2(int *L, int l, int *R, int *r)
{
// int *K=(int *)malloc((lae+1)*sizeof(int));
int Z[lae+1];
int z;
int i,j;
comb1(L, l,L,l,Z,&z);
for(i=0; i<lae+1; i++) K2[i]=0;
for(i=0; i<l; i++){
K2[L[i]]=1;
for(j=0; j<z && L[i]+Z[j]<=lae; j++){
K2[L[i]+Z[j]]=1;
}
}
for(i=0;i<z;i++){
for(j=0; j<l && Z[i]>L[j];j++){
K2[Z[i]-L[j]]=1;
}
for( ; j<l;j++){
K2[L[j]-Z[i]]=1;
}
}
j=0;
for(i=0;i<lae+1;i++){
if(K2[i]){
R[j++]=i;
}
}
*r = j;
}
// Test, ob die "Sperrigkeit" erfüllt ist. Wenn nicht, Gegenbeispiel
// ausgeben.
int checklist(int*L,int l)
{
int i,j,k,m;
for(i=0;i<l;i++)
for(j=0;j<l;j++)
for(k=0;k<l;k++)
for(m=0;m<l;m++)
if(m!=i && m!=j && m!=k){
if(L[i]+L[j]+L[k]==L[m]){
printf("%i+%i+%i=%i",L[i],L[j],L[k],L[m]); return(1);
}
if(L[i]+L[j]-L[k]==L[m]){
printf("%i+%i-%i=%i",L[i],L[j],L[k],L[m]); return(1);
}
if(L[i]-L[j]-L[k]==L[m]){
printf("%i-%i-%i=%i",L[i],L[j],L[k],L[m]); return(1);
}
}
return 0;
}
// Komplement der Listeneinträge zur Liste [0,...,lae] bestimmen.
void kompl(int*L,int l,int *Erg, int *erg){
int i, lauf, er;
lauf=0; er=0;
for(i=0; i<l; i++){
while(L[i]>lauf){Erg[er++]=lauf; lauf++;}
lauf++; // Vorhandenen Wert überspringen
}
// Ggf. Rest auffüllen:
while(lauf<lae+1) {Erg[er++]=lauf; lauf++;}
*erg=er;
}
// Backtrack: Sucht die längste Liste von Zahlen 0, ... , lae derart,
// daß sich keine der Zahlen als Summe oder Differenz von 1 bis 3
// der anderen Zahlen darstellen lässt.
void btr(int *L, int l)
{
int Ko[lae+1], ko; // Kombinationen
int Di[lae+1], di; // verbleibende Möglichkeiten
int i;
comb2(L,l,Ko,&ko);
if(ko==lae+1)
{ // nicht erweiterbare Liste erreicht!
found++;
if(l>lm){ // Neues Maximum gefunden!
lm=l;
for(i=0;i<l;i++) Lm[i]=L[i]; // Neue Bestliste merken.
}
}else{ // Weitere Möglichkeiten durchgehen.
kompl(Ko,ko,Di,&di); // Differenzmenge Di finden.
// Nun alle Möglichkeiten aus Di "backtracken"
// Dabei nur größere als den bisher größten Wert
// L[l] berücksichtigen!
for(i=0; Di[i]<L[l-1]; i++);
for(; i<di; i++){
L[l]=Di[i];
btr(L,l+1); // und eine Ebene tiefer gehen.
}
}
}
int main( int argc, char *argv[] ) {
// int L[lae+1], l;
lae=200;
K1=(int *)malloc((lae+1)*sizeof(int)); // für comb1
K2=(int *)malloc((lae+1)*sizeof(int)); // für comb2
Lm=(int*)malloc((lae+1)*sizeof(int));
for(lae=1; lae<116; ){
int L[lae+1], l;
l=1;
lm=0; // Maximum auf 0.
L[0]=0;
btr(L,l);
printf("lae: %2i, max: %i, ",lae, lm);
Lout(Lm,lm);
lae++;
}
free(K1); free(K2); free(Lm);
}
--
Dr. Detlef Müller,
http://www.mathe-doktor.de oder http://mathe-doktor.de