Bei der Lösung wettbewerbsfähiger Programmierprobleme musste ich manchmal ** Zustände für jeden Fall erstellen und verarbeiten, anstatt nur die Anzahl der Fälle zu zählen. In Ruby Array # Kombination und [ Array # wiederholte_permutation](https: // docs.ruby-lang.org/ja/latest/method/Array/i/repeated_permutation.html) usw. sind verfügbar, aber wenn ich etwas anderes möchte, kann ich es nicht schnell zusammenbauen und es braucht Zeit.
Also werde ich versuchen, die Methode, die ich damals wollte, auch als Übung zu machen.
Es gibt Zeiten, in denen Sie ** Muster abdecken möchten, die für jedes Element enthalten / nicht enthalten sind, z. B. wenn Sie sie alle gleichzeitig lösen möchten. Die Anzahl der Fälle beträgt "2 ** ary.size".
Die Anzahl der Elemente kann von "0" bis "ary.size" reichen, sodass Sie die Kombinationen für jedes Element auflisten können. Es ist einfach und schnell, da ** der größte Teil der Arbeit der internen Implementierung von Ruby ** überlassen bleibt.
each_subset.rb
def each_subset(ary, &block)
0.upto(ary.size) { |n| ary.combination(n, &block) }
end
if $0 == __FILE__
each_subset([*0..2]) { |subset| p subset }
end
output
[]
[0]
[1]
[2]
[0, 1]
[0, 2]
[1, 2]
[0, 1, 2]
Versuchen wir, die Reihenfolge der Aufzählung k (beginnend mit 0) in binärer Notation festzulegen, dass 1`` 0 direkt dem Einschluss / Ausschluss jedes Elements entspricht.
Wenn Sie es gehorsam tun, sieht es so aus. Ruby erhält den Wert des i-Bits mit Integer # [] es kann.
each_subset.rb
def each_subset(ary, &block)
(1 << ary.size).times do |k|
subset = ary.select.with_index { |_, i| k[i] == 1 }
block.call(subset)
end
end
if $0 == __FILE__
each_subset([*0..2]) { |subset| p subset }
end
output
[]
[0]
[1]
[0, 1]
[2]
[0, 2]
[1, 2]
[0, 1, 2]
Da das erste Element "0" von "ary" dem niedrigsten Bit (= gerade / ungerade) entspricht, wird das Vorhandensein / Fehlen jedes Mal umgeschaltet, während das letzte Element "2" dem höchstwertigen Bit entspricht, so dass es nur in der zweiten Hälfte eingefroren wird Es erscheint.
Wie Sie sehen können, ist die Implementierung eine Doppelschleife mit einer festen Anzahl von Malen, und der Zeitaufwand für die Berechnung beträgt O (2 N). 2 Von N </ sup> ist N keine große Sache, daher sollte es im praktischen Gebrauch kein Problem geben (die Anzahl der Elemente beträgt ungefähr 16). Wenn überhaupt, mache ich mir mehr Sorgen darüber, dass ich nur mit "# select" auswerte.
Versuchen Sie vorerst O (2 N). Implementieren Sie es rekursiv und fügen Sie es in den Prozess ein, wenn es weniger "ary" gibt.
each_subset.rb
def each_subset(ary, selected = [], &block)
if ary.empty?
block.call(selected.dup) #Duplizieren, da es zu gefährlich ist, wenn das Array dasselbe Objekt ist
return
end
ary = ary.dup #Duplizieren Sie, um die Eingabesequenz nicht zu unterbrechen
elem = ary.pop
each_subset(ary, selected, &block) #schließt elem nicht ein
selected.unshift(elem)
each_subset(ary, selected, &block) #Einschließlich elem
selected.shift
# ary << elem #Nicht erforderlich, wenn dupliziert
return #Gibt vorerst null zurück
end
if $0 == __FILE__
each_subset([*0..2]) { |subset| p subset }
end
Nicht rekursive Version und zeichnet intern alle Muster in einem Array auf, bevor sie ausgeführt werden (weil es einfach ist).
each_subset.rb
def each_subset(ary, &block)
subsets = [[]]
ary.each do |elem|
subsets.concat(subsets.map { |ss| [*ss, elem] })
end
return subsets.each(&block)
end
if $0 == __FILE__
each_subset([*0..2]) { |subset| p subset }
end
-->
Für ary = [0, 1, 2, 3, 4] möchte ich zum Beispiel [[0, 1], [2], [3, 4]] erstellen.
Unter einem anderen Gesichtspunkt beträgt die Anzahl der Fälle "2 ** (ary.size -1)", da dies bedeutet, dass "ein Trennzeichen für ** zwischen ** Elementen des Arrays eingefügt / nicht eingefügt wird". Da es ein Rätsel ist, was zurückgegeben werden soll, wenn es sich um ein leeres Array handelt, sollten Sie es als praktisches Formular für die Implementierung verwenden.
Dies wird auch rekursiv implementiert. Wenn Sie einige gruppieren und aus "ary" extrahieren, können Sie eine weitere Gruppe mit den verbleibenden erstellen.
each_split.rb
def each_split(ary, selected = [], &block)
if ary.empty?
block.call(selected.map(&:dup)) #Duplizieren, da es zu gefährlich ist, wenn das Array dasselbe Objekt ist
return
end
# ary == part1 +Bedienen Sie, um Teil2 zu behalten
part1 = []
part2 = ary.dup #Duplizieren Sie, um die Eingabesequenz nicht zu unterbrechen
selected << part1
until part2.empty?
part1 << part2.shift #Verschieben Sie die geteilte Position nach rechts
each_split(part2, selected, &block)
end
selected.pop
# ary.replace(part1) #Nicht erforderlich, wenn dupliziert
return #Gibt vorerst null zurück
end
if $0 == __FILE__
each_split([*0..4]) { |sp| p sp }
end
output
[[0], [1], [2], [3], [4]]
[[0], [1], [2], [3, 4]]
[[0], [1], [2, 3], [4]]
[[0], [1], [2, 3, 4]]
[[0], [1, 2], [3], [4]]
[[0], [1, 2], [3, 4]]
[[0], [1, 2, 3], [4]]
[[0], [1, 2, 3, 4]]
[[0, 1], [2], [3], [4]]
[[0, 1], [2], [3, 4]]
[[0, 1], [2, 3], [4]]
[[0, 1], [2, 3, 4]]
[[0, 1, 2], [3], [4]]
[[0, 1, 2], [3, 4]]
[[0, 1, 2, 3], [4]]
[[0, 1, 2, 3, 4]]
Recommended Posts