8

I'm not quite sure how to articulate this, so I'll just give examples.

If I write:

some_method(["a", "b"], 3)

I'd like it to return some form of

[{"a" => 0, "b" => 3},
 {"a" => 1, "b" => 2},
 {"a" => 2, "b" => 1},
 {"a" => 3, "b" => 0}]

If I pass in

some_method(%w(a b c), 2)

The expected return value should be

[{"a" => 2, "b" => 0, "c" => 0},
 {"a" => 1, "b" => 1, "c" => 0},
 {"a" => 1, "b" => 0, "c" => 1},
 {"a" => 0, "b" => 2, "c" => 0},
 {"a" => 0, "b" => 1, "c" => 1},
 {"a" => 0, "b" => 0, "c" => 2}]

Describing this is hard, so thanks in advance if you answer this question!

4
  • 1
    @smarx I'm not even sure where to start, so nothing yet.
    – clapp
    Sep 26, 2016 at 5:10
  • 2
    Well, come back when you have something! Stack Overflow isn't a great place to ask questions like this. See stackoverflow.com/help/how-to-ask.
    – user94559
    Sep 26, 2016 at 5:20
  • 1
    Is there any logic to expected output? For instance, why the first output does not have {"a" => 1, "b" => 3}
    – Wand Maker
    Sep 26, 2016 at 6:26
  • 1
    Seems to be a subset sum problem
    – Stefan
    Sep 26, 2016 at 7:22

2 Answers 2

7

Here is one way to do this:

def some_method ary, num
 permutations = (0..num).to_a.repeated_permutation(ary.size).select do |ary| 
    ary.reduce(:+) == num 
 end

 return permutations.map { |a| (ary.zip a).to_h }
end

p some_method ["a", "b"], 3
#=> [{"a"=>0, "b"=>3}, {"a"=>1, "b"=>2}, {"a"=>2, "b"=>1}, {"a"=>3, "b"=>0}]
p some_method %w(a b c), 2
#=> [{"a"=>0, "b"=>0, "c"=>2}, {"a"=>0, "b"=>1, "c"=>1}, {"a"=>0, "b"=>2, "c"=>0}, {"a"=>1, "b"=>0, "c"=>1}, {"a"=>1, "b"=>1, "c"=>0}, {"a"=>2, "b"=>0, "c"=>0}]

Updated the answer based on tip by @seph

4
  • 2
    Nice. I think if you use repeated_permutation you're there.
    – seph
    Sep 26, 2016 at 7:04
  • Thanks @seph - I did not know about that method. It seems to be working fine now.
    – Wand Maker
    Sep 26, 2016 at 7:09
  • @CarySwoveland - I sometime like the explicit return statement - it makes me comfortable while reading code. I agree that its optional.
    – Wand Maker
    Sep 26, 2016 at 7:11
  • 1
    Very nice. My first attempt was something along these lines, but it wasn't working out so I switched to doing a recursion. btw, we get the same answers for my second example. Sep 26, 2016 at 7:14
5

This method uses recursion.

def meth(keys_remaining, total_remaining)
  first_key, *rest_keys = keys_remaining
  return [{ first_key=>total_remaining }] if rest_keys.empty?
  (0..total_remaining).flat_map { |n|  
    meth(rest_keys, total_remaining-n).map { |g| { first_key=>n }.merge(g) } }
end

meth ["a", "b", "c"], 2
  #=> [{"a"=>0, "b"=>0, "c"=>2}, {"a"=>0, "b"=>1, "c"=>1}, {"a"=>0, "b"=>2, "c"=>0},
       {"a"=>1, "b"=>0, "c"=>1}, {"a"=>1, "b"=>1, "c"=>0}, {"a"=>2, "b"=>0, "c"=>0}]

meth ["a", "b", "c", "d"], 4
  #=> [{"a"=>0, "b"=>0, "c"=>0, "d"=>4}, {"a"=>0, "b"=>0, "c"=>1, "d"=>3},
  #    {"a"=>0, "b"=>0, "c"=>2, "d"=>2}, {"a"=>0, "b"=>0, "c"=>3, "d"=>1},
  #    {"a"=>0, "b"=>0, "c"=>4, "d"=>0}, {"a"=>0, "b"=>1, "c"=>0, "d"=>3},
  #    {"a"=>0, "b"=>1, "c"=>1, "d"=>2}, {"a"=>0, "b"=>1, "c"=>2, "d"=>1},
  #    {"a"=>0, "b"=>1, "c"=>3, "d"=>0}, {"a"=>0, "b"=>2, "c"=>0, "d"=>2},
  #    {"a"=>0, "b"=>2, "c"=>1, "d"=>1}, {"a"=>0, "b"=>2, "c"=>2, "d"=>0},
  #    {"a"=>0, "b"=>3, "c"=>0, "d"=>1}, {"a"=>0, "b"=>3, "c"=>1, "d"=>0},
  #    {"a"=>0, "b"=>4, "c"=>0, "d"=>0}, {"a"=>1, "b"=>0, "c"=>0, "d"=>3},
  #    {"a"=>1, "b"=>0, "c"=>1, "d"=>2}, {"a"=>1, "b"=>0, "c"=>2, "d"=>1},
  #    {"a"=>1, "b"=>0, "c"=>3, "d"=>0}, {"a"=>1, "b"=>1, "c"=>0, "d"=>2},
  #    {"a"=>1, "b"=>1, "c"=>1, "d"=>1}, {"a"=>1, "b"=>1, "c"=>2, "d"=>0},
  #    {"a"=>1, "b"=>2, "c"=>0, "d"=>1}, {"a"=>1, "b"=>2, "c"=>1, "d"=>0},
  #    {"a"=>1, "b"=>3, "c"=>0, "d"=>0}, {"a"=>2, "b"=>0, "c"=>0, "d"=>2},
  #    {"a"=>2, "b"=>0, "c"=>1, "d"=>1}, {"a"=>2, "b"=>0, "c"=>2, "d"=>0},
  #    {"a"=>2, "b"=>1, "c"=>0, "d"=>1}, {"a"=>2, "b"=>1, "c"=>1, "d"=>0},
  #    {"a"=>2, "b"=>2, "c"=>0, "d"=>0}, {"a"=>3, "b"=>0, "c"=>0, "d"=>1},
  #    {"a"=>3, "b"=>0, "c"=>1, "d"=>0}, {"a"=>3, "b"=>1, "c"=>0, "d"=>0},
  #    {"a"=>4, "b"=>0, "c"=>0, "d"=>0}] 

Your Answer

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

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