Permutationen erzeugen

Neue Frage »

Dopap Auf diesen Beitrag antworten »
Permutationen erzeugen
Ich soll rechnerisch auf einem grafikfähigen TR ( HP 50g) immer wieder neue Permutationen erzeugen, ohne die schon verwendeten abzuspeichern. --> Speicherplatz.

Sagen wir mal : hier im Beispiel für n=5 Stellen mit den Ziffern 0...9

dazu habe ich eine HILL-Matrix berechnet:



die wird jetzt der Reihe nach mit (0,0,0,0,1)^T ; (0,0,0,0,2)^T ... (9,9,9,9,9)^T multipliziert und der Ergebnisvektor modulo 10 genommen.
Diese Vektoren, kurz Zahlen, genannt sind paarweise verschieden und überdecken lückenlos das Intervall 00001 ... 99999

Die Abbildungsfunktion des Beispiels ist sogar involutorisch.

Soweit so gut. Nun soll aber n deutlich grösser sein, und auch die die Anzahl der "Ziffern" anwachsen, z.B. N=26 für das Alphabet.

Die Hillmatrix wird nun leider unhandlich.

Frage: gibt es eine andere Methode die evtl. rechenintensiver, aber auf die Speicherung einer sehr grossen Matrix verzichten kann.

Zum TR: alle Modulo Rechenarten vorhanden, unbegrenzte Genauigkeit im Zehnersystem.

Beispiel
HAL 9000 Auf diesen Beitrag antworten »

Ich hab ja heute schon mal die GSL erwähnt, und wie alle GNU-Programme liegt die im Quelltext vor - so auch die relativ effiziente Erzeugung der "nächsten" Permutation:

code:
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:
int
gsl_permutation_next (gsl_permutation * p)
{
  /* Replaces p with the next permutation (in the standard lexicographical
   * ordering).  Returns GSL_FAILURE if there is no next permutation.
   */
  const size_t size = p->size;
  size_t i, j, k;

  if (size < 2)
    {
      return GSL_FAILURE;
    }

  i = size - 2;

  while ((p->data[i] > p->data[i+1]) && (i != 0))
    {
      i--;
    }

  if ((i == 0) && (p->data[0] > p->data[1]))
    {
     return GSL_FAILURE;
    }

  k = i + 1;

  for (j = i + 2; j < size; j++ )
    {
      if ((p->data[j] > p->data[i]) && (p->data[j] < p->data[k]))
        {
          k = j;
        }
    }

  /* swap i and k */

  {
    size_t tmp = p->data[i];
    p->data[i] = p->data[k];
    p->data[k] = tmp;
  }

  for (j = i + 1; j <= ((size + i) / 2); j++)
    {
      size_t tmp = p->data[j];
      p->data[j] = p->data[size + i - j];
      p->data[size + i - j] = tmp;
    }

  return GSL_SUCCESS;
}
(Quelle: aus permutation/permutation.c von gsl 1.15)

Zu beachten ist, dass hier nicht , sondern permutiert wird, also z.B. im Fall n=10 beginnend mit Permutation

0 1 2 3 4 5 6 7 8 9

produziert diese Funktion durch wiederholten Aufruf dann

0 1 2 3 4 5 6 7 9 8

0 1 2 3 4 5 6 8 7 9

0 1 2 3 4 5 6 8 9 7

0 1 2 3 4 5 6 9 7 8

0 1 2 3 4 5 6 9 8 7

0 1 2 3 4 5 7 6 8 9

usw.
Mystic Auf diesen Beitrag antworten »

Ergänzend das Gleiche nochmals in Maple:

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
nextperm:=proc(pp::list)
   local n:=nops(pp),i:=n-1,j:=n,p:=pp;
   # Bestimme maximales i, sodass p[i]<p[i+1]
   do
     if i<=0 then return false end if;
     if p[i]<p[i+1] then break end if;
     i:=i-1
   end do;
   # Bestimme maximales j, sodass p[i]<p[j]
   do
     if p[i]<p[j] then break end if;
     j:=j-1
   end; 
   # Austausch von p[i] und p[j]:
   p[i],p[j]:=p[j],p[i]; 
   # p aufsteigend sortieren ab Position i+1:
   [op(1..i,p),op(sort([op(i+1..n,p)]))]   
end:

seq((nextperm@@k)([1,2,3]),k=0..5);
[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]
Dopap Auf diesen Beitrag antworten »

ja, besten Dank für die Programme.
Man müsste das jetzt noch in UserRPL umschreiben.
Ich bin mir nicht sicher, vermute aber, dass "zufällige" Permutationen gewünscht sind, so wie es die Hill-Matrix bietet, d.h. 2 Folge-Permutationen haben im Mittel ungefähr denselben Abstand wie 2 rein zufällige Permutationen. Nicht umsonst eignet die sich gut zum Chiffrieren.

Aber: mal sehen...
Mystic Auf diesen Beitrag antworten »

Maple könnte dir in dieser Hinsicht alle Wünsche erfüllen und noch viel mehr... Hier ein kleines Beispiel:

code:
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
with(group); # Lädt Package für das Rechnen in Permutationsgruppen

pg:=permgroup(7,{[[1,2,3,4,5,6,7]],[[1,2]]}); #Erzeugt die symmetrische Gruppe S7

grouporder(pg); # Hier der "Beweis"
                              5040

RandElement(pg); # Ergibt Zufallspermutation in der Gruppe pg (in Zyklendarstellung)

                        [[1, 6, 3], [2, 5, 7, 4]]
HAL 9000 Auf diesen Beitrag antworten »

Wenn allerdings

Zitat:
Original von Dopap
immer wieder neue Permutationen erzeugen, ohne die schon verwendeten abzuspeichern.

so zu deuten ist, dass es keine Wiederholungen geben soll, dann sehe ich ziemlich schwarz für den Wunsch, die bisherigen Permutationen (in welcher Form auch immer) nicht zwischenzuspreichern zu wollen. verwirrt


P.S.: Entschuldigung dafür, dass ich oben deinen Beitrag so gedeutet hatte, dass du nur alle Permutationen erzeugen wolltest, statt (wie mir jetzt klar ist) zufällig ausgewürfelte Permutationen.
 
 
Mystic Auf diesen Beitrag antworten »

Ja, diese Forderung nach "immer wieder neuen" Permutationen hatte ich auch überlesen... Ich frage mich nur, ob man diese nicht "unter den Tisch fallen lassen" kann... Ist nämlich n klein, dann kann man ohnehin ohne Probleme alle Permutationen im Speicher halten und damit Wiederholungen vermeiden, ist n aber groß, dann ist die Wahrscheinlichkeit, dass bei einer Zufallsauswahl wirklich die exakt gleiche Permutation nochmals gewählt wird praktisch 0...
Dopap Auf diesen Beitrag antworten »

mmh, das ist aber schade.

Doppelte Permutationen gehen gar nicht, da anscheinend u.A. Identifikationsschlüssel vergeben werden.

Die Zwischenspeicherung scheidet aber auch aus, da hier noch mit kB Hauptspeicher gerechnet wird und das Überprüfen von z.B. Tausend Einträgen ewig dauert. Es sind schließlich Interpreterprogramme auf einem TR...

Das Gute an der Hill-Permutation oder Hill-Verschlüsselung ist ja gerade der Umstand, dass die Abbildung bijektiv ist - was für eine Verschlüsselung ja ziemlich sinnvoll ist- desweiteren sind die erzeugten Permutationen(*) so gut wie rein zufällig.

Beispiel:

(*)

(*) das sind jetzt keine Permutationen, dazu hätte ich im Beispiel eine 10x10 Hill-Matrix nehmen müssen oder den Ziffernbereich auf 0 bis 4 einschränken sollen.

Ich werde jetzt mal versuchen, eine andere Verschlüsselung zu finden die dasselbe leistet.
Ich denke da an RSA, Multiplikation und Invertieung über GF(q), Potenzierung über GF(p), Inverses Modulo.

bis dann..
Mystic Auf diesen Beitrag antworten »

Zitat:
Original von Dopap
Ich werde jetzt mal versuchen, eine andere Verschlüsselung zu finden die dasselbe leistet.
Ich denke da an RSA, Multiplikation und Invertieung über GF(q), Potenzierung über GF(p), Inverses Modulo.

bis dann..

Hört sich für mich sehr vielversprechend an... ElGamal sollte aber nicht fehlen, am besten über elliptischen Kurven...
Dopap Auf diesen Beitrag antworten »

@Mystik :
äh, ja, ich hab' das einfach mal abgeschrieben - und von GF(p) kenn ich auch nur den Namen verwirrt

,muss also noch Arbeit investieren.

Und den guten ElGamal ( obwohl eigentlich puplic key ) verwende ich zur privaten Verschlüsselung.

Das geht nur auf meinem Taschenrechner, und damit mir hier niemand die Keys klaut, werden die nach Eingabe meiner PIN jedesmal neu berechnet und nur lokal gespeichert. Schlau oder ? Big Laugh

ElGamal ist ja eigentlich eine polyalphabetische Blockchiffre. Ich verwende aber nur einen Charakter vom ASCII-Zeichensatz. Demnach eine polyalphabetische Zeichenchiffrierung. Diese werden in den Zahlenraum bis ca. 1 Mio abgebildet. Also Spreizung 1 char --> 6 Ziffern mit pseudozufälliger Wahl eines neuen Alphabets für jeden Chiffrierschritt.
Das müsste reichen. Da nützen übliche Angriffe wohl nix.

Äh, sorry ich verplaudere mich schon wieder, aber sonst will von meinen wenigen Bekannten keiner was davon wissen... Schiksal eben.
Dopap Auf diesen Beitrag antworten »

nach etwas Nachdenken ist mir leider Folgendes aufgefallen:

Auch meine Hill-Abbildungen erzeugen in der Regel keine Permutationen. Hammer

Das hätte mir auch gleich jemand sagen können. unglücklich

( aber nach boardprinzip bekommt der Fragesteller nur Hilfestellungen. Wenn er aber selbst seine Fehler korrigiert ist das pädagogisch und mathematisch viel wertvoller . Lol )

Dann bleibt es also bei:

1.) entweder Permutationen mit erkennbarer Folge

2.) Zufallspermutationen mit der geringen Wahrscheinlichkeit von Duplikaten.

aber Vorsicht: beim "Geburtstagsparadoxon" genügen schon 23 Personen damit p>0.5 für Duplikate.
Bei 20!=2.433E18 müsste aber schon reichlich Luft sein, bis p>0.001 gilt.

Habe ich was übersehen ?

Wenn nicht, dann werde ich so berichten.

Gruss Dopap
Mystic Auf diesen Beitrag antworten »

Zitat:
Original von Dopap
Auch meine Hill-Abbildungen erzeugen in der Regel keine Permutationen. Hammer

Das hätte mir auch gleich jemand sagen können. unglücklich

Naja, ich denke, HAL und ich sind schon davon ausgegangen, dass du den Kern des Problems bereits für uns herausgeschält hast, sodass wir uns um das ganze Drumherum nicht mehr zu kümmern brauchten... Augenzwinkern

Zitat:
Original von Dopap
aber Vorsicht: beim "Geburtstagsparadoxon" genügen schon 23 Personen damit p>0.5 für Duplikate.
Bei 20!=2.433E18 müsste aber schon reichlich Luft sein, bis p>0.001 gilt.

Allgemein ist es so, das bei einer Ziehung mit Zurücklegen aus n Objekten nach Ziehungen Duplikate zu erwarten sind... Beim Geburtstagsproblem wäre das also



während der Median aufgrund der Rechtschiefheit der Verteilung leicht darunter liegt, also dann bei etwa 23 Personen... Insbesondere sieht man, dass bei 20! erst nach rund 2 Milliarden "Ziehungen" ein Duplikat zu erwarten ist... Augenzwinkern
Dopap Auf diesen Beitrag antworten »

Zitat:
Original von Mystic
Naja, ich denke, HAL und ich sind schon davon ausgegangen, dass du den Kern des Problems bereits für uns herausgeschält hast, sodass wir uns um das ganze Drumherum nicht mehr zu kümmern brauchten... Augenzwinkern


ja, da hast du natürlich vollkommen recht. Wenn man so kompetent (?) wie ich auftritt, dann hat man eben einen Bonus. Augenzwinkern

Erinnert mich an Politker ! Big Laugh

Hat trotzdem Spass gemacht!
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »