[ruby-core:72363] [Ruby trunk - Feature #11815] Proposal for method `Array#difference`

[duerst@it.aoyama.ac.jp]

Issue #11815 has been updated by Martin Dürst.


Ryan Beltran wrote:

> I think I have a pretty good example. I'm implementing a function in Ruby that finds triples in an array for use in a pokerbot (recognizes if a hand is a triple). I already defined a function to check for doubles (which is relatively trivial to implement by comparing the original array to array.uniq), but triples are a little bit harder. There are several ways I could implement checking for triples, but a concise and efficient option would be to simply call:
> 
> `getDoubles(array.difference(array.uniq))` 

> 
> ~~~ ruby
> doubles = array.difference(array.uniq)
> triples = doubles.difference(doubles)
> fours   = triples.difference(triples)
> ~~~

An even more straightforward way is to use group_by:

~~~ ruby
n_tuples = array.group_by {|e| e}.values.group_by(&:length)

doubles = n_tuples[2]
triples = n_tuples[3]
fours   = n_tuples[4]
# and so on
~~~ ruby

We need group_by two times because the first one groups items with the same value, and the second organizes these by numbers. As an example, if we start with [1,2,2,3,3,3,4,4,4,4,5,5,5,7,8,8] then after the first group_by, we have
{1=>[1], 2=>[2, 2], 3=>[3, 3, 3], 4=>[4, 4, 4, 4], 5=>[5, 5, 5], 7=>[7], 8=>[8, 8]}.
Of this, we only need the values: [[1], [2, 2], [3, 3, 3], [4, 4, 4, 4], [5, 5, 5], [7], [8, 8]].
Then we group by length and get:
{1=>[[1], [7]], 2=>[[2, 2], [8, 8]], 3=>[[3, 3, 3], [5, 5, 5]], 4=>[[4, 4, 4, 4]]}
To get an unique value (i.e. 3 instead of [3, 3, 3]), just use .map(&:first).

----------------------------------------
Feature #11815: Proposal for method `Array#difference`
https://bugs.ruby-lang.org/issues/11815#change-55656

* Author: Cary Swoveland
* Status: Open
* Priority: Normal
* Assignee: 
----------------------------------------
I propose that a method `Array#difference` be added to the Ruby core. It is similar to [Array#-](http://ruby-doc.org/core-2.2.0/Array.html#method-i-2D) but for each element of the (array) argument it removes only one matching element from the receiver. For example:

    a = [1,2,3,4,3,2,2,4]
    b = [2,3,4,4,4]

    a - b #=> [1]
    c = a.difference b #=> [1, 3, 2, 2] 

As you see, `a` contains three `2`'s and `b` contains `1`, so the first `2` in `a` has been removed from `a` in constructing `c`. When `b` contains as least as many instances of an element as does `a`, `c` contains no instances of that element. 

It could be implemented as follows:

     class Array
       def difference(other)
         dup.tap do |cpy|
           other.each do |e|
             ndx = cpy.index(e)
             cpy.delete_at(ndx) if ndx
            end
          end
        end
      end

Here are a few examples of its use:

*Identify an array's unique elements*

      a = [1,3,2,4,3,4]
      u = a.uniq #=> [1, 2, 3, 4]
      u - a.difference(u) #=> [1, 2]

*Determine if two words of the same size are anagrams of each other*

      w1, w2 = "stop", "pots"
      w1.chars.difference(w2.chars).empty?
        #=> true

*Identify a maximal number of 1-1 matches between the elements of two arrays and return an array of all elements from both arrays that were not matched*

      a = [1, 2, 4, 2, 1, 7, 4, 2, 9] 
      b = [4, 7, 3, 2, 2, 7] 
      a.difference(b).concat(b.difference(a))
        #=> [1, 1, 4, 2, 9, 3, 7] 
  
To remove elements from `a` starting at the end (rather the beginning) of `a`:

    a = [1,2,3,4,3,2,2,4]
    b = [2,3,4,4,4]

    a.reverse.difference(b).reverse #=> [1,2,3,2]

`Array#difference!` could be defined in the obvious way.



-- 
https://bugs.ruby-lang.org/