Einfacher Algorithmus möglich?

[Quixy (Gast)]

Aloha,
gerade wollte ich einen vermeintlich einfachen Algorithmus runterhacken, 
musste aber feststellen dass meine Lösung nichts taugt ;-) Auch nach 
langem Grübeln habe ich noch keine optimale Lösung gefunden. Daher wende 
ich mich mal an die Superhirne hier im Forum :-)

Gegeben: n Einsen und m Nullen.
Gesucht: Die Ziffern sollen so in ein Array der Länge n+m verteilt 
werden, dass die Anzahl aufeinanderfolgender gleicher Ziffern möglichst 
klein ist.

Beispiel:
n=3 und m=3

-> [0,0,0,1,1,1] ist die schlechtest mögliche Lösung  (max. Länge 3)
-> [0,1,0,1,0,1] ist die optimale Lösung  (max. Länge 1)

Noch ein Beispiel:
n=1 und m=3
-> [0,0,1,0] wäre eine optimale Lösung (max. Länge 3)

Noch ein Beispiel:
n=9 und m=6
-> [1,1,0,1,1,0,1,1,0,1,1,0,1,0,0] wäre eine optimale Lösung  (max. 
Länge 2)

Ich hoffe die Aufgabe ist einigermaßen klar geworden?
Wenn jemand eine Zündende Idee hat, darf es mich gerne wissen lassen :-)


PS: Worum geht es hier eigentlich? Es sollen aus Blöcken von 
Video-Frames einige Frames entfernt werden. Diese sollen aber möglichst 
gleichmäßig verteilt sein, so dass das Ergebnis nachher so flüssig wie 
möglich erscheint.

[Volker (Gast)]

Bresenham-Algorithmus müste gehen.

[Niklas G. (erlkoenig)]

#include <stdio.h>
#include <stdlib.h>

void generate (unsigned int n, unsigned int m) {
  unsigned int cn = 0, cm = 0;
  
  while (cn < n || cm < m) {
    if (cn < n && (cn * m <= n * cm)) {
      fputs ("0, ", stdout);
      ++cn;
    } else {
      fputs ("1, ", stdout);
      ++cm;
    }
  }
  puts ("");
}

int main (int argc, char* argv []) {
  if (argc != 3) {
    fprintf (stderr, "Usage: %s Zeroes Ones\n", argv [0]);
    return 1;
  }
  generate (atoi (argv [1]), atoi (argv [2]));
}

So?

[Johann L. (gjlayde)]

Bresenham-Algorithmus zum Zeichnen einer Linie: Die Bilder entsprechen 
den Pixeln einer zu zeichnenden Linie mit rationaler Steigung y/x. Z.B. 
entspricht ein Schritt in x dem Darstellen eines Bildes und Schritt in y 
dem Auslassen bei ursprünglich x+y Bildern.

[Peter M. (r2d3)]

Hallo Quixy,

Du lässt einfach alle (n+m)/n Frames einen Frame fallen.

Mit ein bisschen Optimierung kannst Du anstelle der Rundung auf ganze 
Frame-Nr. die Löschungen so verteilen, dass die ersten Frames alle

abgerundet[(n+m)/n] eine Löschung bekommen, und dahinter alle Frames mit

aufgerundet[(n+m)/n]

Dann ändert sich der Abstand der gelöschten Frames im gesamten Video nur 
an einer Stelle.
Bei der Berechnung der Standardabweichung des Löschungsabstandes macht 
das jedoch keinen Unterschied.

P.S.:
Haftungsausschluss: Bin kein Superhirn.

[Quixy (Gast)]

Niklas G. schrieb:
> So?

Gute Lösung!

[zitter_ned_aso (Gast)]

Niklas G. schrieb:
> #include <stdio.h>
> #include <stdlib.h>
>
> void generate (unsigned int n, unsigned int m).......

wenn ich dein Programm mit Parametern 3 4 aufrufe, dann bekomme ich als 
Lösung:

0, 1, 1, 0, 1, 0, 1,

Hier stehen zwei Einsen direkt nebeneinander. Man kann aber die 
Kombination

1010101

erzeugen.

[zitter_ned_aso (Gast)]

Mein "Algorithmus":

n = Anzahl Einsen
m = Anzahl Nullen

p = min(m,n) = Anzahl der Paare
s = abs(n-m) = Anzahl der restlichen "single digits"

Annahme: n>m

1) Erzeuge p Pärchen "01"
2) An die ersten s Pärchen vorne eine "1" anhängen

[Jemand (Gast)]

zitter_ned_aso schrieb:
> Mein "Algorithmus":
>
> n = Anzahl Einsen
> m = Anzahl Nullen
>
> p = min(m,n) = Anzahl der Paare
> s = abs(n-m) = Anzahl der restlichen "single digits"
>
> Annahme: n>m
>
> 1) Erzeuge p Pärchen "01"
> 2) An die ersten s Pärchen vorne eine "1" anhängen

n = 7
m = 1
-> p = 1
-> s = 6
--> 101

Naja.

[Niklas G. (erlkoenig)]

zitter_ned_aso schrieb:
> Hier stehen zwei Einsen direkt nebeneinander.

Oh, stimmt. Das liegt an dem "<=" - bei der ersten Ziffer wird der 0 die 
Vorzug gegeben. Bei "<" hätte man das umgekehrte Problem. Der erste Teil 
der Bedingung ist wohl auch überflüssig. Außerdem kann man die 
wiederholte Multiplikation vermeiden, indem man direkt um n bzw. m 
inkrementiert. So geht es:

void generate (unsigned int n, unsigned int m) {
  unsigned int cn = 0, cm = 0;
  
  while (cn < n*m || cm < n*m) {
    if (cn < cm || (cn == cm && n >= m)) {
      fputs ("0, ", stdout);
      cn += m;
    } else {
      fputs ("1, ", stdout);
      cm += n;
    }
  }
  assert (cm == n*m);
  assert (cn == n*m);
  puts ("");
}

int main (int argc, char* argv []) {
  if (argc != 3) {
    fprintf (stderr, "Usage: %s Zeroes Ones\n", argv [0]);
    return 1;
  }
  generate (atoi (argv [1]), atoi (argv [2]));
}

Die Folge wird also bei ausgeglichenem Verhältnis (u.a. am Anfang) mit 
der Ziffer fortgesetzt, von der es mehr geben soll, wobei 0 Vorzug hat 
wenn n=m.

Mit dem Algorithmus könnte man auch einen Takt durch einen gebrochenen 
Faktor teilen - wenn man die Funktion im Takt der Eingabefrequenz 
aufruft, man bei "1" einen Puls ausgibt und bei "0" nicht, ist der 
Teilungsfaktor (n+m)/m. Jittert natürlich ziemlich, der Duty-Cycle ist 
komisch, aber alle n+m Takte stimmt das Teiler-Verhältnis wieder, d.h. 
der Fehler ist nicht kumulativ.

[zitter_ned_aso (Gast)]

Jemand schrieb:
> n = 7
> m = 1
> -> p = 1
> -> s = 6
> --> 101
>
> Naja.



zitter_ned_aso schrieb:
> 1) Erzeuge p Pärchen "01"
> 2) An die ersten s Pärchen vorne eine "1" anhängen

3) keine Pärchen mehr vorhanden an das letze Pärchen die restlichen 
(s-p) Einsen anhängen ;-)

Hier in C:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(void){
    
    int num_1=7;
    int num_0=1;

    int x1, x2;

    if(num_1>num_0){
        x1=1;
        x2=0;
    }
    else{
        x1=0;
        x2=1; 
    }
    
    //zusammengesetztes Array deklarieren   
    int arr_len=num_1+num_0; 
    int* arr=malloc(sizeof(int)*arr_len);

    //zusammengestztes Array initialisieren
    int i=0;
    int j=0;
    int k=0;
    int num_of_pairs=(num_1>num_0)?num_0:num_1;
    int num_of_single_digits=abs(num_1-num_0);
    while(i<arr_len){
        //"single digits" vor dem Paerchen
        if(j++<num_of_single_digits)
            *(arr+i++)=x1;
        //die Paerchen 
        if(k++<num_of_pairs){
            *(arr+i++)=x2;
            *(arr+i++)=x1;
        }
    }
   
    //Array ausgeben
    for(int i=0; i<arr_len; i++){
        printf("%d", *(arr+i)); 
    }
    puts("");

    free(arr);

    return 0;
}

[zitter_ned_aso (Gast)]

zitter_ned_aso schrieb:
> 3) keine Pärchen mehr vorhanden an das letze Pärchen die restlichen
> (s-p) Einsen anhängen ;-)

Und das würde nicht reichen!

Denn es kommt dann  10111111 raus. Und 11101111 is besser.

Also muss man dann diese (s-p) Einsen immer abwechselnd anhängen: vorne, 
hinten, vorne hinten.... Und das bei "jedem" Pärchen :-( Und auch das 
würde nicht gehen.

Denn n=6, m=2 würde 10111011 liefern. Und 11011011 wäre besser!  Meine 
Güte, das ist vielleicht eine Aufgabe....

[zitter_ned_aso (Gast)]

Niklas G. schrieb:
> Mit dem Algorithmus

und für die Parameter 2 6 kriegst du auch "1, 0, 1, 1, 1, 0, 1, 1"

Dabei wäre 11011011 besser.

Quixy schrieb:
> Auch nach
> langem Grübeln habe ich noch keine optimale Lösung gefunden.

Ich kann dich verstehen ;-)

[Niklas G. (erlkoenig)]

zitter_ned_aso schrieb:
> Dabei wäre 11011011 besser.

Aber nicht wenn sich die Folge wiederholen soll, denn dann kommt 4x eine 
1 hintereinander...

[zitter_ned_aso (Gast)]

n=20  => 1,1,1,1.....
m=2   => 0,0

2 Pärchen:  01  01 (Reihenfolge wichtig)

noch 20-2=18 "single digits".

=> single digits vor jedem Pärchen einfügen: 101 101
und an das letzte Pärchen anhängen: 101 1011 --->max. Länge =2

noch 20-5=15 "single digits" zu verteilen.

Wieder vorne, vorne, hinten einfügen:  1101 110111 --> max. Länge =3 (besser geht's nicht)

20-8=12

vorne, vorne, hinten: 11101 11101111 ----> max=4 

20-11=9

vorne, vorne, hinten: 111101 1111011111 --->max=5

20-14=6

vorne, vorne, hinten: 1111101 111110111111 --->max=6

20-17=3

vorne, vorne, hinten: 11111101 11111101111111 --->max=7

Vielleicht so. Es sieht zumindest besser aus.

[Niklas G. (erlkoenig)]

zitter_ned_aso schrieb:
> und für die Parameter 2 6 kriegst du auch "1, 0, 1, 1, 1, 0, 1, 1"
>
> Dabei wäre 11011011 besser.

Warum eigentlich? Die Anforderung war, dass möglichst wenige gleiche 
Ziffern aufeinander folgen sollen. In beiden Fällen ist die Anzahl der 
Ziffern, die auf eine gleiche Ziffer folgt, 3.

[zitter_ned_aso (Gast)]

Ich habe es so verstanden:

1 0  111 0 1 1

--> max. Länge = 3

11 0 11 0 11

--> max. Länge = 2

[Niklas G. (erlkoenig)]

zitter_ned_aso schrieb:
> Ich habe es so verstanden:

Okay, das wäre das Maximum der Folgen-Längen, dann sieht das ganze 
anders aus.

[Teo D. (teoderix)]

Es geht doch um x Fps, und davon möglichst gleichmäßig, y Frames raus 
zuwerfen?!

[K. S. (the_yrr)]

Quixy schrieb:
> PS: Worum geht es hier eigentlich? Es sollen aus Blöcken von
> Video-Frames einige Frames entfernt werden.
das heißt aber dass es nicht nur einmal stattfindet sondern Ende=Anfang 
ist

zitter_ned_aso schrieb:
> Ich habe es so verstanden:
>
> 1 0  111 0 1 1
>
> --> max. Länge = 3
>
> 11 0 11 0 11
>
> --> max. Länge = 2

damit stimmt das nicht mehr, dann ist:

10111011-10111011
-> max Länge = 3

11011011-11011011
-> max Länge = 4

zitter_ned_aso schrieb:
> Denn n=6, m=2 würde 10111011 liefern. Und 11011011 wäre besser!  Meine
> Güte, das ist vielleicht eine Aufgabe....
ist dann auch nicht mehr so schlecht, denn:
10111011-10111011
-> immer noch max Länge 3
und das "bessere":
11011011-11011011 hat dann max Länge 4

von weiter oben:
zitter_ned_aso schrieb:
> wenn ich dein Programm mit Parametern 3 4 aufrufe, dann bekomme ich als
> Lösung:0, 1, 1, 0, 1, 0, 1,
>
> Hier stehen zwei Einsen direkt nebeneinander. Man kann aber die
> Kombination
> 1010101
wenn man die Lösungen "Ringförmig" betrachtet sind sie wieder identisch

heut ist mir zu spät um darüber weiter nachzudenken, aber ich glaube die 
Lösung schlägt hier grad nen falschen Weg ein. Außer ein Block 
entspricht dem gesammten Video, aber dafür sind die Zahlen etwas klein, 
niemand hat nur 20 Frames in einem Video. Wenn es nur 2-3 Blöcke gibt 
sollte man natürlich Anfang+Ende als solche betrachtet optimieren, aber 
bei mehreren Sekunden-Minuten Video ist es ausreichend davon auszugehen 
dass jeder Block einen Vorgänger und Nachfolger hat.

[zitter_ned_aso (Gast)]

ja