Lors de la résolution de problèmes de programmation compétitifs, j'avais parfois besoin de ** créer et traiter des états pour chaque cas, plutôt que de simplement compter le nombre de cas. Dans Ruby, [ʻArray # combination](https://docs.ruby-lang.org/ja/latest/method/Array/i/combination.html) et [ʻArray # repeat_permutation](https: // docs.ruby-lang.org/ja/latest/method/Array/i/repeated_permutation.html) etc. sont disponibles, mais quand je veux autre chose, je ne peux pas l'assembler rapidement et cela prend du temps.
Je vais donc essayer de faire la méthode que je voulais à ce moment-là, également en tant que pratique.
Il y a des moments où vous voulez ** couvrir des modèles qui sont inclus / non inclus pour chaque élément, par exemple lorsque vous voulez les résoudre tous en même temps. Le nombre de cas est "2 ** ary.size".
Le nombre d'éléments peut être de «0» à «ary.size », vous pouvez donc lister les combinaisons pour chacun. C'est facile et ** c'est rapide car l'essentiel du traitement est laissé à l'implémentation interne de Ruby **.
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]
Essayons de faire l'ordre d'énumération «k» (à partir de 0) en notation binaire que «1» «0» correspond à l'inclusion / exclusion de chaque élément tel quel.
Si vous le faites docilement, cela ressemble à ceci. Ruby obtient la valeur du bit ʻiavec [ʻInteger # []](https://docs.ruby-lang.org/ja/latest/method/Integer/i/=5b=5d.html) ça peut.
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]
Puisque le premier élément «0» de «ary »correspond au bit le moins significatif (= pair / impair), la présence / absence est commutée à chaque fois, tandis que le dernier élément« 2 »correspond au bit le plus significatif, il n'est donc figé que dans la seconde moitié. Il apparaît.
Comme vous pouvez le voir, l'implémentation est une double boucle avec un nombre fixe de fois, et le temps de calcul est O (2 N </ sup> N). 2 A partir de N </ sup>, N n'est pas un gros problème, il ne devrait donc pas y avoir de problème d'utilisation pratique (le nombre d'éléments est d'environ 16). Si quoi que ce soit, je suis plus préoccupé par le fait que j'évalue simplement avec # select.
Essayez O (2 N </ sup>) pour le moment. Implémentez-le récursivement et déposez-le dans le processus quand il y en a un de moins.
each_subset.rb
def each_subset(ary, selected = [], &block)
if ary.empty?
block.call(selected.dup) #Dupliquer car c'est trop dangereux si le tableau est le même objet
return
end
ary = ary.dup #Dupliquer pour ne pas interrompre la séquence d'entrée
elem = ary.pop
each_subset(ary, selected, &block) #n'inclut pas d'élem
selected.unshift(elem)
each_subset(ary, selected, &block) #Y compris elem
selected.shift
# ary << elem #Non requis si dupliqué
return #Renvoie nul pour le moment
end
if $0 == __FILE__
each_subset([*0..2]) { |subset| p subset }
end
Version non récursive, et enregistre en interne tous les modèles dans un tableau avant de s'exécuter (car c'est facile).
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
-->
Pour ʻary = [0, 1, 2, 3, 4] , je veux créer, par exemple, [[0, 1], [2], [3, 4]] `.
D'un point de vue différent, le nombre de cas est 2 ** (ary.size -1) car cela signifie qu '"un délimiteur est inséré / non inséré pour ** entre ** éléments du tableau". Puisqu'il s'agit d'un mystère de ce qu'il faut renvoyer lorsqu'il s'agit d'un tableau vide, faites-en une forme pratique pour l'implémentation.
Ceci est également implémenté de manière récursive. Si vous groupez et extrayez certains de ʻary`, vous pouvez créer un autre groupe avec les autres.
each_split.rb
def each_split(ary, selected = [], &block)
if ary.empty?
block.call(selected.map(&:dup)) #Dupliquer car c'est trop dangereux si le tableau est le même objet
return
end
# ary == part1 +Opérer pour garder part2
part1 = []
part2 = ary.dup #Dupliquer pour ne pas interrompre la séquence d'entrée
selected << part1
until part2.empty?
part1 << part2.shift #Déplacer la position de division vers la droite
each_split(part2, selected, &block)
end
selected.pop
# ary.replace(part1) #Non requis si dupliqué
return #Renvoie nul pour le moment
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