Permutation mit wiederholungen

Hallo,
ich mache gerade etwas Theorycrafting für ein Spiel und komme mit der Kombinatorik nicht ganz klar

Ich habe ein Array an Items und 6 Slots, jedes Item kann auch mehrfach getragen werden, Position ist dabei egal.

Also z.B.
111111
111112 = 111121 = 211111 gibt in der Berechnung das gleiche also unnötig
111122

wobei jede Position ein Array ist damit ich besser weiter Rechnen kann (Itemwerte usw.)
evtl geht ja auch das eine Position nicht aus allen Werten bestehen kann sondern nur aus ein paar : /
300 Items 6 Slots wobei 1 der 6 Slots nur aus 10 Items bestehen kann und nicht aus allen.

_ArrayCombinations und Permutation helfen mir nicht weiter da dort Wiederholung nicht möglich ist, ich hoffe ich konnte halbwegs verständlich die Sache schildern.

Zitat von Christoph54

Hey,
ich habe dein Problem zwar nicht ganz verstanden, aber ich habe vor einigen Monaten mal einen Permutations-Algorithmus geschrieben. Bin mir noch sicher ob es das ist was du suchst, aber vielleicht hilft dir mein Script ja...

Spoiler anzeigen

[autoit]

#region Array
Dim $ABC[63]
$ABC[0] = 62
$ABC[1] = "a"
$ABC[2] = "b"
$ABC[3] = "c"
$ABC[4] = "d"
$ABC[5] = "e"
$ABC[6] = "f"
$ABC[7] = "g"
$ABC[8] = "h"
$ABC[9] = "i"
$ABC[10] = "j"
$ABC[11] = "k"
$ABC[12] = "l"
$ABC[13] = "m"
$ABC[14] = "n"
$ABC[15] = "o"
$ABC[16] = "p"
$ABC[17] = "q"
$ABC[18] = "r"
$ABC[19] = "s"
$ABC[20] = "t"
$ABC[21] = "u"
$ABC[22] = "v"
$ABC[23] = "w"
$ABC[24] = "x"
$ABC[25] = "y"
$ABC[26] = "z"
$ABC[27] = "A"
$ABC[28] = "B"
$ABC[29] = "C"
$ABC[30] = "D"
$ABC[31] = "E"
$ABC[32] = "F"
$ABC[33] = "G"
$ABC[34] = "H"
$ABC[35] = "I"
$ABC[36] = "J"
$ABC[37] = "K"
$ABC[38] = "L"
$ABC[39] = "M"
$ABC[40] = "N"
$ABC[41] = "O"
$ABC[42] = "P"
$ABC[43] = "Q"
$ABC[44] = "R"
$ABC[45] = "S"
$ABC[46] = "T"
$ABC[47] = "U"
$ABC[48] = "V"
$ABC[49] = "W"
$ABC[50] = "X"
$ABC[51] = "Y"
$ABC[52] = "Z"
$ABC[53] = "0"
$ABC[54] = "1"
$ABC[55] = "2"
$ABC[56] = "3"
$ABC[57] = "4"
$ABC[58] = "5"
$ABC[59] = "6"
$ABC[60] = "7"
$ABC[61] = "8"
$ABC[62] = "9"
#endregion

[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

#region Test-Script
If FileExists("next1000.txt") Then FileDelete("next1000.txt")
$Last = ""
For $count = 1 To 1000
$back = _Next($ABC,$Last)
$Last = $back
FileWrite("next1000.txt",$back&@CRLF)
ToolTip($count&@CRLF&$Last,0,0)
Next
ShellExecute("next1000.txt")
Exit
#endregion

[/autoit] [autoit][/autoit] [autoit]

Func _Next($Array,$String)
$Return = ""
If $String <> "" Then
$Len = StringLen($String)
For $i = $Len To 1 Step -1
$Char = StringMid($String,$i,1)
$Numb = ""
For $y = 1 To $Array[0]
If $Char == $Array[$y] Then $Numb = $y
Next
If $Numb = "" Then Exit
If $Char <> $Array[$Array[0]] Then
$Return = StringLeft($String,$i - 1) &$Array[$Numb + 1] &$Return
ExitLoop
Else
$Return = $Array[1] &$Return
If $i = 1 Then
$Return = $Array[1] &$Return
ExitLoop
EndIf
EndIf
Next
Else
$Return = $Array[1]
EndIf
Return $Return
EndFunc

[/autoit]

LG
Christoph

Alles anzeigen

hmm ne leider nicht ganz, bei dir kommen als mögliche Lösung zwar aa raus was schon mal punkt 1 ist
aber leider auch die Dopplung wie z.B ai und ia als Lösung was ich nicht haben möchte

Zitat von BugFix

Wieviel Zustände können sich denn da ergeben? (Jetzt mit 1 und 2 angegeben)
Du könntest statt 1,2,3 (oder was vorgesehen ist, Dualzahlen verwenden (1,2,4,8..) und diese mit BitOR verknüpfen, mit BitXOr löschen, mit BitAnd auf Existenz prüfen. Somit hast du nur eine Zahl, die alle Statuswerte (oder was die 1,2 auch bedeuten) trägt.

hmm na 300 Items auf 6 Slots verteilt :> sind schon ne Menge Zustände.
z.B. 100,300,5,75,80,1
die Zahlen sind die Array Positionen wo die Items drin stehen mit ihren Werten

Zitat von BugFix

Versuche mal dein Ansinnen etwas verständlicher zu erklären.
Ich habe keine Ahnung, was du hier mit Slots meinst. Dieses Wort hat soviel Bedeutungen, wie es Graustufen gibt.
Sinnvoll ist immer ein Besipiel mit verschiedenen Zuständen. Vorher, nacher, Schrittweite von-bis, etc. pp.

Mit deiner bisherigen Fragestellung kann ich nur Raten, was du vorhast.

hmmm sry
also ich hab ein Array mit Gegenständen die ich einsetzen möchte in verschiedenen Kombinationen,
dabei kann ein Gegenstand 6 mal vorkommen, die Reihenfolge ist aber egal, so dass 5x Apfel+1x Birne das gleiche ist wie 1x Birne + 5x Apfel
111112
111122
111222
112222
122222
222222
222221 = haben wir bereits mit 122222 also muss es weg
111113
111133
113333
123456
usw usw

jede Zahl steht für 1 Gegenstand bzw für eine Array Position

[autoit]

#include <Array.au3>

[/autoit][autoit][/autoit][autoit]

Global $str = '11111122222233333344444455555566666'

[/autoit][autoit][/autoit][autoit]

Local $list = StringSplit($str, '', 2)
Local $tuples[1] = [0], $tmp
For $i = 6 to 6
$tmp = _ArrayCombinations($list, $i, '')
_ArrayDelete($tmp, 0)
_ArrayConcatenate($tuples, $tmp, 0)
Next
_ArrayDelete($tuples, 0)
_ArrayDisplay($tuples)

[/autoit]

so muss es aussehen aber wenn ich die Zahlen 1-300 verwenden will und jede Stelle 6x also Global $str = '11111122222233333344444455555566666 -> 300'
bekomme ich sowieso ein Array maximum size exceeded (ja ein paar doppelte Zeilen sind drin aber wenigstens nicht in der Reihenfolge Doppelt)
in der Kombinatorik ist das glaube ich was ich suche, Reihenfolge egal+mit Wiederholungen:
(n+r-1)! / r!(n-1)!

Da mir keine Helfen kann, hier ne neue Frage zu dem Thema:

so wie die Funktion von Christoph54, danach jedoch zusätzlich jede Zeile Sortieren nach Größe d.h.
111112
211111 -> wird beim Sortieren zu 111112
doppelte Zeilen jetzt löschen und wieder zurück sortieren zum Ursprung :s
findet dazu jemand eine Lösung, bekomme selbst das nicht hin

/e ok auch das hab ich einigermaßen hinbekommen:

[autoit]

#include <Array.au3>
#include <file.au3>

[/autoit][autoit][/autoit][autoit]

Local $aarray[18] = [1,1,1,1,1,1,2,2,2,2,2,2,3,3,3,3,3,3]

[/autoit][autoit][/autoit][autoit]

For $i = 1 To UBound($aArray)
Local $aArrayCombo = _ArrayCombinations($aArray, 6, ",")
Next

[/autoit][autoit][/autoit][autoit][/autoit][autoit]

_ArraySort($aArrayCombo)
Local $aNewArray =_ArrayUnique($aArrayCombo)
_filewritefromarray("test.txt", $anewarray)

[/autoit]

hab damit nur nen kleines Problem a) sehr langsam, b) 2 Zeilen die nicht dazu gehören :s c) mein start Array muss ich händisch eingeben 6x die Zahlen 1->100

bei 5x 100 Kombinationen komme ich auf 75.287.520 Möglichkeiten, was über dem Autoit maximum ist

Stimmen die 300 Items und 6 Slots noch? Da hast du dann mehr als 1 Billion Möglichkeiten für eine "ungeordnete Stichprobe mit zurücklegen". Wozu musst du die alle berechnen?

Zitat von progandy

Wozu musst du die alle berechnen?

Ihr habt doch bestimmt auch schon mal ein Spiel gespielt wo es Items gibt die bestimmte Attribute geben z.B Kraft, Geschwindigkeit usw usw.,
wenn ich aber nur 6 davon tragen kann aber eine große Auswahl habe, möchte ich gerne wissen was die beste Kombination ist.....

Zitat von progandy

Stimmen die 300 Items und 6 Slots noch? Da hast du dann mehr als 1 Billion Möglichkeiten für eine "ungeordnete Stichprobe mit zurücklegen".

nein sind mir auch zu viele Möglichkeiten, ich werde es auf Maximal 65 Items und 5 Slots beschränken, dann sind es 11.238.513.
Da das wahrscheinlich auch zu viel ist werde ich es nochmal splitten in 3 Teile, 5 Slots a 22 Items (65.780) und danach Filtern und noch einmal die besten nehmen.
Oder falls jemand nen guten Vorschlag hat würde ich auch 6 Slots nehmen a 22 Items (296.010)

Zitat von Christoph54

Polarfrau ist das mit dem Speil nur ein Beispiel oder ist das der richtige Verwendungszweck?! Wenn man bei dem Beispiel? mit dem Spiel bleibt, nehme ich mal an, dass jedes dieser 'Items' seine Auswirkungen nach sich zieht. Wenn du am Ende nur die Attribute überprüfen willst, könnte man doch einfach eine ganz normale Permutation benutzen... Dies lässt sich einfach an diesem Beispiel erklären:

Spoiler anzeigen

Wir haben 3 Items:
Item A verändert unser Attribut um +2
Item B verändert das Attribut um +5
Item C verändert das Attribut um +10
Im laufe der Permutation treten jetzt zwar 'doppelte' Elemente in den Kombinationen auf, aber dies macht nichts:
A+B+C = 2+5+10 = +17
C+B+A = 10+5+2 = +17
Also ist es im Endeffekt egal, welche Kombination gewählt wird...?!

LG
Christoph

Alles anzeigen

naja ich komme aber übers Array Limit
hab gedacht wenn die doppelten raus sind,das es dann geht weil es ja nicht nur ein paar sind sonders mehrere tausend doppelte.
Aber ich entferne sie ja am Ende und nicht vorher :s

Aber ja ist nicht nur ein Bsp sondern auch der Zweck wieso ich das so mache.

Kann ich das in mehreren schritten machen? also 3x22+2x22 und dann das array zusammenbauen, weil es ja wie gesagt später viel kleiner ist als vorher