Power set: Difference between revisions
Content added Content deleted
Line 1,773: | Line 1,773: | ||
<lang ruby># Based on http://johncarrino.net/blog/2006/08/11/powerset-in-ruby/ |
<lang ruby># Based on http://johncarrino.net/blog/2006/08/11/powerset-in-ruby/ |
||
# See the link if you want a shorter version. This was intended to show the reader how the method works. |
# See the link if you want a shorter version. This was intended to show the reader how the method works. |
||
class Array |
class Array |
||
# Adds a power_set method to every array, i.e.: [1, 2].power_set |
# Adds a power_set method to every array, i.e.: [1, 2].power_set |
||
def power_set |
def power_set |
||
# Injects into a blank array of arrays. |
# Injects into a blank array of arrays. |
||
Line 1,781: | Line 1,781: | ||
# you is each element of the array |
# you is each element of the array |
||
inject([[]]) do |acc, you| |
inject([[]]) do |acc, you| |
||
ret = [] # Set up a new array to add into |
|||
⚫ | |||
acc.each do |i| # For each array in the injected array, |
|||
⚫ | |||
ret = [] |
|||
⚫ | |||
# For each array in the injected array, |
|||
acc.each do |i| |
|||
⚫ | |||
ret << i |
|||
⚫ | |||
ret << i + [you] |
|||
end |
end |
||
⚫ | |||
⚫ | |||
ret |
|||
end |
end |
||
end |
end |
||
⚫ | |||
# A more functional and even clearer variant. |
# A more functional and even clearer variant. |
||
def func_power_set |
def func_power_set |
||
Line 1,812: | Line 1,801: | ||
#A direct translation of the "power array" version above |
#A direct translation of the "power array" version above |
||
require 'set' |
|||
class Set |
class Set |
||
def powerset |
|||
inject(Set[Set[]]) do |ps, item| |
|||
ps.union ps.map {|e| e.union (Set.new [item])} |
|||
end |
|||
end |
end |
||
end |
end |
||
end |
|||
p [1,2,3,4].power_set |
|||
p %w(one two three).func_power_set |
|||
p Set[1,2,3].powerset</lang> |
|||
{{out}} |
|||
<pre> |
|||
[[], [4], [3], [3, 4], [2], [2, 4], [2, 3], [2, 3, 4], [1], [1, 4], [1, 3], [1, 3, 4], [1, 2], [1, 2, 4], [1, 2, 3], [1, 2, 3, 4]] |
|||
[[], ["one"], ["two"], ["one", "two"], ["three"], ["one", "three"], ["two", "three"], ["one", "two", "three"]] |
|||
#<Set: {#<Set: {}>, #<Set: {1}>, #<Set: {2}>, #<Set: {1, 2}>, #<Set: {3}>, #<Set: {1, 3}>, #<Set: {2, 3}>, #<Set: {1, 2, 3}>}> |
|||
</pre> |
|||
=={{header|Scala}}== |
=={{header|Scala}}== |