4

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.

2
  • 1
    "Subsets of an array" does not make sense. "Subsets of a set" or "Sub-arrays of an array" would make sense. In other words, would [1, 1, 2, 3] be allowed as an argument? If it is, then would that be equivalent to [1, 2, 3]? If not, then what result would be expected?
    – sawa
    Nov 18, 2013 at 12:17
  • @sawa, it is a unique set only. no repeats.
    – hken27
    Nov 18, 2013 at 12:31

6 Answers 6

9
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]]
5
  • 1
    I know that already. Trying to working out the problem instead of using #combination short cut.
    – hken27
    Nov 18, 2013 at 12:37
  • 3
    @hken27 You didn't write that in the question. You should have.
    – sawa
    Nov 18, 2013 at 12:38
  • @Santosh Close, but yours is wrong. The i should start at 0.
    – sawa
    Nov 18, 2013 at 12:38
  • 1
    @sawa, Thanks for pointing it out. I didnt notice the [] in the qs. It was not easily readable. Corrected my answer
    – Santhosh
    Nov 18, 2013 at 16:06
  • Having [] is the normal definition. Assuming otherwise should require special motivation. Readability should not matter. Good that you corrected it.
    – sawa
    Nov 18, 2013 at 16:09
3

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]]
1

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], []
2
  • Yes, that is what I expect. Any thoughts?
    – hken27
    Nov 18, 2013 at 12:29
  • Yes, I am missing something in the algorithm that's why I need some help. If using ([1,2,3,4]) missing [1,3,4] , [2,4], etc
    – hken27
    Nov 18, 2013 at 12:48
1

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]]
0

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
0

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.