Eine Harte Nuss

Thorsten83 · Beiträge: 191 Erhaltene Danke: 1

@Martok: Gute Argumentation

@hui: Woher kommt diese Fragestellung eigentlich?

Du musst nur bedenken dass 1 Millarde 30 Bits sind, nicht 1024...

Was die bekannte Anzahl der Einsen angeht, bei m Einsen gibt es 1024 über m Kombinationen die die Bedingung erfüllen, das ist auch schon eine ganze Menge.

Mein Ansatz wäre ja schon dass man erstmal die Bedingungen auswertet und diese damit recht erheblich reduziert, damit kriegt man "Schnippsel" die beliebig aneinander gehängt die ursprünglichen Bedingungen erfüllen, aber n Schnippsel beliebig aneinander zu hängen geht halt wieder auf n! verschiedene Arten bzw. ergibt so viele Permutationen.

Nochmal zu der Überlegung ob solche Aufgenstellungen sinnvoll sind:
Ich hab mal eine Aufgabe gesehen bei der es darum ging, ein Programm zu schreiben, das alle Möglichkeiten liefert x€ mit 1, 2, 5, 10(usw)-Cent-Stücken zu bezahlen, von der Überlegung her eine schöne Aufgabe, wenn man das für 10€ ausrechnen will hat der Rechner aber schon was zu tun

Für 5€ mit maximal 50c ergeben sich z.B. 2426955 Möglichkeiten...

hui1991 · Verfasst: Di 14.10.08 21:45

So ungefähr habe ich angefangen bin aber nicht fertig geworden, da schon weider 22:45 ist:

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:

00100100000001001010111000001000:
               1:    9           1
              11:    1           
             111:    1      
               0:   23          0
              01:    7          01
             011:    1          
            0111:    1          
              00:    9         00
             001:    5         001
             000:    4        000
            0001:    2        0001
            0000:    2       0000
           00001:    2       00001
           00000:    2      00000
          000001:    2      000001
          000000:    1     000000
         0000001:    1     0000001
         0000000:    1    0000000
        00000001:    1    00000001
Es wurden 19 vorkommen gefunden.

Oben stehen jetzt welche aufjedenfall zusammengehören.
Jetzt muss man nur noch die Felder so weit ausfüllen und von der menge subtrahieren um den rest zu berechnen.

               1:    9-1         1
              11:    1           
             111:    1      
               0:   23-7  0*0*0*0
              01:    7-1        01
             011:    1          
            0111:    1          
              00:    9-3   00**00
             001:    5-1       001
             000:    4-2   ***000
            0001:    2-1      0001
            0000:    2-1     0000
           00001:    2-1     00001
           00000:    2-1    00000
          000001:    2-1    000001
          000000:    1-1   000000
         0000001:    1-1   0000001
         0000000:    1-1  0000000
        00000001:    1-1  00000001


00000001 muss irgendwo sein.

Ergebnis:
               1:    8-1         1
              11:    1           
             111:    1      
               0:   16-5    0*0*0
              01:    6-1              01
             011:    1          
            0111:    1          
              00:    6-2     **00
             001:    4-1       001
             000:    2-1      000
            0001:    1-1      0001
            0000:    1-1     0000
           00001:    1-1     00001
           00000:    1-1    00000
          000001:    1-1    000001

Es ist sicher das irgendwo 000001 stehen muss aber nicht in 00000001.

Ergebnis:
               1:    7           
              11:    1           
             111:    1      
               0:   11-2       *0
              01:    5 
             011:    1          
            0111:    1          
              00:    4-1       00
             001:    3        
             000:    1-1      000

Irgendwo muss 000 sein.

Ergebnis:
               1:    7-3   1*1   
              11:    1-1    11   
             111:    1-1   111  
               0:    9-1       0
              01:    5-1  01
             011:    1-1  011      
            0111:    1-1  0111      
              00:    3       
             001:    3  

Irgendwo muss 0111 stehen

Ergebnis:
               1:    4-1      1  
               0:    8-1      0  
              01:    4-1     01
              00:    3-1    00  
             001:    3-1    001

Irgendwo muss 001 stehen.


Ergebnis:
               1:    3-1      1  
               0:    7-1      0  
              01:    3-1     01
              00:    2-1    00  
             001:    2-1    001

Irgendwo ist noch eine 001.

Ergebnis:
               1:    2-1      1  
               0:    6-1      0  
              01:    2-1     01
              00:    1-1    00  
             001:    1-1    001

Irgendwo ist noch eine 001.

Ergebnis:
               1:    2-1      1  
               0:    6-1      0  
              01:    1-1     01

Irgendwo ist 01.

Es bleiben 1x'1' und 5x'0' die nicht gefunden werden konnten

Möglichkeiten der Sortierung:
01,001,001,001,000,000001,00000001,1,0,0,0,0,0

Edit bin etz weiter gekommen hier das ergebnis, muss noch testen ob das noch passt.

Martok · Verfasst: Di 14.10.08 22:53

Alternativ kann man auch die Bedingungen als Wörterbücher verwenden und daraus die Permutationen generieren (bzw ausfiltern), die die Bedingungen erfüllen. Gibt zwar massiv Ausschuss, aber weniger als Bruteforce.

_________________
"The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."

Thorsten83 · Beiträge: 191 Erhaltene Danke: 1

Nein, genau das ist ja der Trick, es gibt keinen Überschuss!
Die Reduzierung der Bedingungen auf Sequenzen, die es so geben muss, führt dazu, dass man nur noch unterscheidbare Permutationen der Sequenzen auflisten muss, was zwar trivial machbar ist, aber aufgrund der blöden Tatsache, dass eine n-Elementige Menge n! Permutationen erzeugt nicht in einer vernünftigen Laufzeit machbar sein wird.

BenBE · Verfasst: Mi 15.10.08 10:31

@

hui1991: Kannst Du mal bitte kurz nen Code-Schnipsel zur Zählung anhängen (also nur einen, der allein für einen Eingabestring die Zählung macht)? Es sind nämlich ein paar kleine Details unklar, die sich anhand von etwas Source besser erklären lassen ;-)

Bin nämlich am Überlegen, inwiefern man den in die Generierung korrekt inlinen kann ;-)

Bei der von mir angefragten Zählweise der Strings hätt man nämlich einige Vorteile bzgl. der Generierung, aber nun gut ;-)

Aber soweit ich deine Zwischenergebnisse überblicke, sollte sich die Optimierung, die mir da vorschwebt auch ausführen lassen ...

Ich setz mich da am Wochenende mal hin: Bis dahin werd ich mir zumindest schon mal was überlegen, wie ich meine Idee möglichst optimal implementiere. Wird aber wahrscheinlich zweiteilig werden ;-)

_________________

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

Thorsten83 · Beiträge: 191 Erhaltene Danke: 1

Hey,

habt ihr belastbare Begründungen warum die Anzahl der möglichen Lösungen nicht in O(n!) liegen sollte? (Und wir uns damit mit einem NP-Problem herumärgern...)

Als Beispiel mal eine kürzere Zahl:
001001000000010010101110000010001011

Das Tool gibt folgende Sequenzen aus:

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:

               1:   12
              11:    2
             111:    1
               0:   24
              01:    9
             011:    2
            0111:    1
              00:    9
             001:    6
             000:    4
            0001:    3
            0000:    2
           00001:    2
           00000:    2
          000001:    2
          000000:    1
         0000001:    1
         0000000:    1
        00000001:    1
Es wurden 19 vorkommen gefunden.

Wenn man die zusammenkürzt kommt folgendes dabei heraus:

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:

00000001: 1
0000001: 0
0000000: 0
000001: 1
000000: 0
00001: 0
00000: 0
0111: 1
0001: 1
0000: 0
111: 0
011: 1
001: 3
000: 0
11: 0
01: 1
00: 0
1: 0
0: 0

Also 6 Sequenzen, die einmal vorkommen, und eine, die dreimal vorkommt.
Ich sehe bei den Vorgaben keine Möglichkeit das weiter zu kürzen, und das bedeutet halt mehr als (genau kann ich das leider gerade nicht quantifizieren...) 7! = 5040 Möglichkeiten...

hui1991 · Verfasst: Mi 15.10.08 18:17

Okay ich hänge den Source meines Programms dran.
Ist unoptimiert da es in dem moment nicht nötig war.
Man klickt drauf und es ist praktisch das Ergebnis da. ^^

Achja von mir aus können das auch andere eigenschaften sein die vllt. besser zum zurückrechnen sind. Hab für den Anfang nur sowas einfaches genommen.

Aber so macht man ja aus einem 36 langen Code der mit Bruteforce 68.719.476.736 (69 Milliarden) möglichkeiten hat in einen Code der zum zurückrechnen nur 362880 Möglichkeiten mit Bruteforce zu berechnen hat. Das schränkt es schon gut ein so. Man sollte da aber noch paar Informationen weglassen und andere reinsetzen, wobei so kann man überprüfen das garantiert keine 01 drin ist wenn nur 001 ist.

Sind 6*1+3*1 nicht 9 also 9! -> 362880
Das sind ja 9 verschiedene Stellen.

Einloggen, um Attachments anzusehen!

Thorsten83 · Beiträge: 191 Erhaltene Danke: 1

Hey,
ne, so einfach ist das leider nicht...

Nimm mal an du hättest 2 A' und 1B,
dann gibt das die Kombinationen

AAB
ABA
BAA

da AA und AA (A's vertauscht

) ja nicht unterscheidbar sind.

Die Reduzierung die aus diesem Kürzen entsteht ist schon immens, aber imho nicht ausreichend.

BenBE · Verfasst: Mi 15.10.08 21:58

Thorsten83 hat folgendes geschrieben :

Nimm mal an du hättest 2 A's und 1B,
dann gibt das die Kombinationen

AAB
ABA
BAA

da AA und AA (A's vertauscht

) ja nicht unterscheidbar sind.

Die Reduzierung die aus diesem Kürzen entsteht ist schon immens, aber imho nicht ausreichend.

Bitte schau mal kurz hier:

Thorsten83 hat folgendes geschrieben :

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:

00000001: 1
0000001: 0
0000000: 0
000001: 1
000000: 0
00001: 0
00000: 0
0111: 1
0001: 1
0000: 0
111: 0
011: 1
001: 3
000: 0
11: 0
01: 1
00: 0
1: 0
0: 0

Also 6 Sequenzen, die einmal vorkommen, und eine, die dreimal vorkommt.
Ich sehe bei den Vorgaben keine Möglichkeit das weiter zu kürzen, und das bedeutet halt mehr als (genau kann ich das leider gerade nicht quantifizieren...) 7! = 5040 Möglichkeiten...

k, warum 7 und nicht 9 als Grundlage für die Permutationsanzahlberechnung? Ganz einfach, weil es 7 verschiedene (unterscheidbare) Gruppen gibt, nicht 9 teilweise ununterscheidbare.

_________________

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

Tilo · Verfasst: Do 16.10.08 10:54

Auch Falsch gerechnet. Wenn in einer Permutation nichtunterscheidbare Element sich errechnet sich meines Wissen die Anzahl unterschiedlicher Varianten so:
(Anzahl aller Elemente)! / (Produkt aller Permutation der nichtunterscheidbaren Elemente)

Hier: 9 Elemente, davon 1 Gruppe mit 3 nichtunterscheidbaren Elemente:
Anz.Varianten: 9!/3!=60480

Anderes Beispiel 6 Elemente, 1 Gruppe mit 3 Elemente, 1 Gruppe mit 2 Elemente und 1 einzelnes Element:
Anz.Varianten=6!/(3!*2!*1!)=60

Thorsten83 · Beiträge: 191 Erhaltene Danke: 1

Wo du Recht hast...

Eigentlich ganz logisch, hätte man auch selber drauf kommen können...

Martok · Verfasst: Do 16.10.08 19:01

Gibts das Ruleset irgendwo als Text? Hab keine Lust das abzutippen und tesseract mag diesen Font nicht....

_________________
"The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."

Tilo · Verfasst: Do 16.10.08 19:25

Ich habs abgetippt,
keine Garantie für Fehlerfreiheit.

Einloggen, um Attachments anzusehen!

hui1991 · Verfasst: Do 16.10.08 19:35

Ne leider hab ich ihn nicht

Kannst dir ja einen eigenen erstellen zum testen. ^^
Ich bin sowieso am überlegen das dieses Programm nur die gekürzte Version ausgibt, weil das ist einmal unnötig gerechnet. ^^
Mir ging es nur darum wie schnell allgemein sowas berechnet werden kann und wie viele möglichkeiten das sind bei 2^200 das sind schon ziemlich viele ^^
Außerdem kommt man mit einer gekürzten Version schneller auf die Maximaleanzahl (n Fakultät) ^^
Ich schreib erstmal ein Programm das aus den 1024er Werten die minimaleigenschaften raussucht ^^

Edit ich hab etz geschaut auf der gekürzten Version wie viel mir angezeigt werden.
Max. 259! kombinationen sind es am Ende geworden

Tabelle sieht so aus:

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:

               1:   1
            1111:   1
              01:  50
             011:  28
            0111:  22
           01111:   6
          011111:   6
       011111111:   1
             001:  38
            0011:  20
           00111:   9
          001111:   3
         0011111:   2
        00111111:   1
      0011111111:   1
            0001:  17
           00011:  10
          000111:   7
         0001111:   1
           00001:  12
          000011:   6
         0000111:   1
       000011111:   2
          000001:   2
         0000011:   2
        00000111:   2
         0000001:   1
        00000001:   1
      0000000111:   1
        00000000:   3
Es wurden 30 vorkommen gefunden.

Ich habe nur die Button-Procedur geändert ^^
Sry das ich goto verwendet habe ^^

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:

procedure TForm1.Button1Click(Sender: TObject);
var
  s, wert: string;
  x, anzahl, l, r: Integer;
  erg: array[0..8, 0..8] of Integer;
label
  Ergebnis, weiter;
begin
  s := Edit1.Text;
  Listbox1.Clear;
  for l := 0 to 8 do
    for r := 0 to 8 do
      erg[l, r] := 0;
  l := 0;
  r := 0;
  x := 1;
  while x < length(s) do begin
    if r = 0 then begin
      if s[x] = '0' then begin
        inc(l);
        inc(x);
      end;
      if l = 9 then begin
        dec(x);
        dec(l);
        goto Ergebnis;
      end;
      if s[x] = '1' then begin
        inc(r);
        inc(x);
      end;   
    end else begin
      if s[x] = '1' then begin
        inc(r);
        inc(x);
      end;
      if (r = 9) then begin
        dec(x);
        dec(r);
        goto Ergebnis;
      end;
      if (s[x] = '0') then begin
          goto Ergebnis;
      end;
    end;
    //l und r sind Ergebnis
    goto weiter;
    Ergebnis:
    inc(erg[l, r]);
    r := 0;
    l := 0;
    weiter:
  end;
  inc(erg[l, r]);
    r := 0;
    l := 0;
  for l := 0 to 8 do begin
    for r := 0 to 8 do begin
      if l + r > 0 then begin
        if erg[l,r]>0 then
          ListBox1.Items.Add(FuegeZeichenVorStringBisCountErreicht(CreateAnzahl('0',l)+CreateAnzahl('1',r),' ',16)+':'+FuegeZeichenVorStringBisCountErreicht(inttostr(erg[l,r]),' ',4));
      end;
    end;
end;
  ListBox1.Items.Add('Es wurden ' + IntToStr(ListBox1.Count) + ' vorkommen gefunden.');
end;

Hidden · Verfasst: Do 16.10.08 20:05

Hi,

Die generelle Grenze ließe sich ja einmal leicht ermitteln. Versucht doch einfach mal, wie viel Text ein Programm maximal in einer Stunde ausgeben kann(das ist viel :lol:

muss man wahrscheinlich hochrechnen). Ich möchte nämlich vermuten, dass ihr auch ohne Rechnen schon grob abschätzen könnt, ob euer Vorhaben überhaupt(heute schon) möglich ist.

mfG,

_________________
Centaur spears can block many spells, but no one tries to block if they see that the spell is a certain shade of green. For this purpose it is useful to know some green stunning hexes. (HPMoR)

Thorsten83 · Beiträge: 191 Erhaltene Danke: 1

Hey,
die Frage ist imho schon geklärt und die Antwort heißt nein

Martok · Verfasst: Fr 17.10.08 07:38

Ich verrat meine Lösung nicht... falls es doch nicht klappt^^
Aber auf die von BenBE könnt ihr euch freuen. Die wird lustig

@eigenes Ruleset: glaub ich kaum, woher soll ich wissen ob ich da ein gültiges baue^^

_________________
"The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."

hui1991 · Verfasst: Fr 17.10.08 12:13

Ich hab ja dessen Source + Binary hier reingehängt ^^
Das Programm müsste immer ein gültiges RuleSet machen ^^

Thorsten83 · Beiträge: 191 Erhaltene Danke: 1

@Hui: machst du das jetzt so ähnlich wie ich?
Oder hast du einen ganz anderen Ansatz?

Martok · Verfasst: Fr 17.10.08 15:23

Ok, mein Programm hat jetzt genau 60 Minuten über 64 Zeichen gegrübelt, Regeln erstellt aus deinem Programm mit willkürlichem Grund-String.

markieren

Ruleset

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:

    (Content: '1'; Count: 37),
    (Content: '11'; Count: 10),
    (Content: '111'; Count: 5),
    (Content: '0'; Count: 27),
    (Content: '01'; Count: 21),
    (Content: '011'; Count: 10),
    (Content: '0111'; Count: 5),
    (Content: '00'; Count: 5),
    (Content: '001'; Count: 5),
    (Content: '0011'; Count: 3),
    (Content: '000'; Count: 1),
    (Content: '0001'; Count: 1)

Rund 340k Ergebnisse bis jetzt. Ein Ende seh ich da nicht....

EDIT: Moment. 340k? Ist eigentlich recht wenig. Ich glaube, da muss ich nochmal ran. Immerhin hab ich schon ein Framework für massiv paralleles Verarbeiten nebenbei gebastelt.

EDIT 2: 340k war eher zu viel, der Validator war kaputt.

_________________
"The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme