CODEWITHSUNDEEP
rubyarraysstringalgorithmnumbers
hken27
hken27

Reputation: 413

Find all subsets in an array

I need help with solving this ruby array question.

Get all the subsets of an array. Unique set only. No repeats of any number. num_subset([1,2,3]) ==> result should be [[], ["1"], ["1", "2"], ["1", "2", "3"], ["1", "3"], ["2"], ["2", "3"], ["3"]]

def num_subset(arr)
    holder =[]
    order_subset = [[]]

    (arr.length).times do |m|  
        arr.map do |n|
            holder += [n]  
            order_subset << holder
        end
    holder =[]  # resets holder
    arr.shift  # takes the first element out
    end
    order_subset
end

My result ==> [[], ["1"], ["1", "2"], ["1", "2", "3"], ["2"], ["2", "3"], ["3"]. My problem is that I am missing one result ["1", "3"]

Need some help pointing me to the right direction. Spent hours on this already. Do not use #combination short cut. I need to work this out manually.

Upvotes: 4

Views: 6984

Answers (6)

gorn
gorn

Reputation: 5340

Recursive solution

def subsets(arr)
  (l = arr.pop) ? subsets(arr).map{|s| [s,s+[l]]}.flatten(1) : [[]]
end

or in a more descriptive way

def subsets(arr)
  return [[]] if arr.empty?
  last = arr.pop
  subsets(arr).map{|set| [set, set + [last]]}.flatten(1)
end

Upvotes: 0

gorn
gorn

Reputation: 5340

I believe this is the most rubyish solution to find combinations

a = [1,2,3]

p (0..a.length).collect { |i|
  a.combination(i).to_a
}.flatten(1)

# [[], [1], [2], [3], [4], [1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4], [1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4], [1, 2, 3, 4]]

Upvotes: 3

Shanky Munjal
Shanky Munjal

Reputation: 671

I have created a method to find all subsets of an array. I am using binary number to make iteration of array very less.

def find_subset(input_array)
    no_of_subsets = 2**input_array.length - 1
    all_subsets = []
    expected_length_of_binary_no = input_array.length
    for i in 1..(no_of_subsets) do 
        binary_string = i.to_s(2)
        binary_string = binary_string.rjust(expected_length_of_binary_no, '0')
        binary_array = binary_string.split('')
        subset = []
        binary_array.each_with_index do |bin, index|
            if bin.to_i == 1
                subset.push(input_array[index]) 
            end
        end
        all_subsets.push(subset)
    end
    all_subsets
end

Output of [1,2,3] would be

[[3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]

Upvotes: 1

satnam
satnam

Reputation: 1425

My solution.

The basic idea over here is that subsets of an array are

Subsets of the array with one less element - let's call these old subsets

array of elements containing that one less element added each of the old subsets

For Example -

Subsets([1, 2, 3]) are -

Subsets([1, 2]) - old_subsets

Tack on 3 to each of old_subsets

def subsets(arr)
  return [[]] if arr.empty?
  old_subsets = subsets(arr.drop(1))
  new_subsets = []
  old_subsets.each do |subset|
    new_subsets << subset + [arr.first]
  end
  old_subsets + new_subsets
end

Upvotes: 0

Santhosh
Santhosh

Reputation: 29124

a = [1, 2, 3]
arr = []

for i in 0..(a.length) do
  arr = arr + a.combination(i).to_a
end

> arr
# [[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]

Upvotes: 9

SQB
SQB

Reputation: 4078

Looks like you're looking at a starting point somewhere in the array and then looking at all sub arrays from that starting point on, after which you move the starting point down. That way, you're missing the sub arrays with gaps. For [1,2,3], the only sub array with a gap is [1,3].

For example (ignoring [] since you've hardcoded that)

[(1),2,3,4] -> [1]
[(1,2),3,4] -> [1,2]
[(1,2,3),4] -> [1,2,3]
[(1,2,3,4)] -> [1,2,3,4]
[1,(2),3,4] -> [2]
[1,(2,3),4] -> [2,3]
[1,(2,3,4)] -> [2,3,4]
[1,2,(3),4] -> [3]
[1,2,(3,4)] -> [3,4]
[1,2,3,(4)] -> [4]

So I'd expect your output for [1,2,3,4] to be [[],[1],[1,2],[1,2,3],[1,2,3,4],[2],[2,3],[2,3,4],[3],[3,4],[4]].

You really need to rethink your algorithm. You could try recursion. Take the head of your array (1), construct all possible sub arrays of the tail ([2,3]), duplicate that, and prefix half of it with the head. Of course, to construct the sub arrays, you call the same function, all the way down to an empty array.

[1,2,3] ->
....[2,3] ->
........[3] ->
............[] ->
................# an empty array is its own answer
................[]
............# duplicating the empty array and prefixing one with 3
............[3], []
........# duplicating the result from the last step and prefixing half with 2
........[2,3], [2], [3], []
....# duplicating the result from the last step and prefixing half with 1
....[1,2,3], [1,2], [1,3], [1], [2,3], [2], [3], []

Upvotes: 1

Related Questions