Permutationsalgorithmus in Form von

Question

R= repeats allowed -> 2
A= alphabet (1-10)
S= space = 4;

Wir wollen also ein Beispiel:

[1][1][4][5]
[1][7][4][5]
[5][1][4][5]

Aber brauchen Sie eine ausgeklügelte mathematische Formel, um dies und alle Kombinationen zu berechnen?

Answer 1

So wie ich es verstehe, ist Ihr Alphabet 1 ... 10, wobei jeder "Buchstabe" möglicherweise zweimal vorkommt. Was Sie also wirklich haben, ist ein Alphabet, das ...

1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10

Sie hat eine Länge von 20, nicht 10.

Das Problem wird nun 20 permute 4.

Ich hoffe, das hilft.

EDIT: Gemäß Ihren zusätzlichen Kommentaren zu Ihrer Frage können Sie dann jede generierte Permutation daraufhin überprüfen, ob sie die Form XXYY hat, denn das wäre nach dem, was Sie geschrieben haben, ungültig.

Answer 2

Die Gesamtzahl beträgt
N * [ (S wähle 1) * ((N-1) permute (S-1)) + (S wählen 2) * ((N-1) permutieren (S-2)) + ... + (S wählt R) * ((N-1) permutieren (S-R)) ]

• Mit anderen Worten, wahrscheinlich ist es am besten, 1 zu reparieren des wiederholten Elements an Ort und Stelle zu fixieren ( S choose 1 verschiedene Arten des Handelns ) und permutieren die übrigen N-1 Artikel über die S-1 verbleibende Leerzeichen; (wie bei normalen N permute S )

• dann fixieren Sie 2 Ihrer identischen Artikel in Platz ( S choose 2 verschiedene Arten von dies zu tun) und permutieren die übrigen N-1 Artikel über die verbleibenden S-2 Räume.

• usw. für jede mögliche Anzahl von Wiederholungen, von 1 bis zu R

• Und dann gibt es noch N Auswahlmöglichkeiten für Ihr mögliches wiederholtes Element.

Sie können diesen Algorithmus auch zur Aufzählung der Möglichkeiten verwenden.

bearbeiten

Oh je. Danke @blueraja, Sie haben absolut Recht! Der Fall der n-fachen Wiederholung lässt sich nicht auf 1 Element verallgemeinern!

Die korrigierte Formel lautet daher

(N permute S)
+ N * [ (S choose 2) * ((N-1) permute (S-2)) 
      + (S choose 3) * ((N-1) permute (S-3)) 
      + ... 
      + (S choose R) * ((N-1) permute (S-R)) ]

Answer 3

Eine korrekte allgemeine Antwort erfordert eine Summierung. Ich zeige Ihnen, wie Sie dies für diese speziellen Werte tun können, und überlasse es Ihnen, dies zu verallgemeinern.

Es gibt zwei Fälle:

• Permutationen, die keine Duplikate enthalten. Dies ist nur 10 P 4
• Permutationen, die genau ein Duplikat enthalten:
  • Wählen Sie, welche Nummer das Duplikat ist: 10 C 1
  • Wählen Sie dafür zwei Orte aus: 4 C 2
  • Wählen Sie die Zahlen aus, die in die verbleibenden zwei Plätze passen: 9 P 2

Die Antwort auf diesen speziellen Fall lautet also 9360.

Answer 4

Es gibt relativ wenige mögliche Lösungen (< 10000), so dass es in Ordnung sein sollte, alle Wörter in A^4 zu erzeugen und dann die Wörter mit mehr als 2 Wiederholungen zu entfernen.

OR

• Erzeugen Sie die (geordneten) Kombinationen von N verschiedenen Wörtern

• Erzeugen Sie die Permutationen dieser Teilmenge, um alle Möglichkeiten ohne Duplikate zu erhalten

• Machen Sie dasselbe mit N-1 Wörtern

• Fügen Sie für jedes Element in diesen Wörtern ein Duplikat an allen Positionen außer der Position des genannten Zeichens hinzu.

Answer 5

Ich gehe davon aus, dass sich nur ein Punkt wiederholen kann, und dieser Punkt ist nicht vorgegeben.

Hier ist eine Formel, die mit A (Alphabetgröße), S (Größe der Zeichenketten) und R (maximale Wiederholungszahl) arbeitet:

f(A,S,R) = (A perm S) + A Summe[r=2 bis R] ( (S wähle r) (A-1 perm S-r) )

Zum Beispiel ergibt sich für R=1 (einfache Permutation) erwartungsgemäß f(A,S,R)=(A perm S). Für A=S=R=2 haben wir f(A,S,R)=4, was dem entspricht:

1,2

2,1

1,1

2,2

Der Fall, den Sie in der Frage beschreiben, ist A=10, R=2, S=4, und dann haben wir:

f(A,S,R) = 9360

(Genau wie BlueRaja berechnet hat)