sagivo/algorithms

algorithms playground for common questions

algorithms's Issues

Link Request: Similar Project in Swift

Greetings;

Feel to review my Github repository with similar content in Swift!

https://github.com/waynewbishop/SwiftStructures

As part of this, I've listed your project on my page as an additional resource. I would be glad if you could mention my project as well. If you have any questions just let me know.

Regards;

doktor

Identity

should be @parent[y] = rx

algorithms/src/kruskal.rb

Line 27 in fd06fba

@parent[rx] += @parent[ry]

and my suggestion:

#!/usr/bin/env ruby

# DisjointSet - Union-Find Data Structure
#   - root(x): find the leader of the set where x in
#   - connected?(x, y): check if x and y are in the same set
#   - union(x, y): union x and y if x and y which are not in the same set

# here the index of array is the data and rank weight
# the value of the array is the parent data

class DisjointSet
  def initialize(n)
    @parent = Array.new(n, -1)
  end

  def root(x)
    @parent[x] < 0 ? x : root(@parent[x])
  end

  def union(x, y)
    rx = root(x)
    ry = root(y)
    if rx < ry
      @parent[rx] = ry
      return true
    elsif rx > ry
      @parent[ry] = rx
      return true
    else
      return false
    end
  end
end

Edge = Struct.new(:from, :to, :weight) do
  def <=> rhs
    self.weight <=> rhs.weight
  end
end


# minimum spanning tree
# the label of the vertex is between 0 and n - 1
def kruskal(n, edges)
  ret = []
  dsu = DisjointSet.new(n)
  edges.sort.each{ |e| ret << e if dsu.union(e.from, e.to) }
  ret
end

# test
edges = [
    Edge.new(0, 1, 1), Edge.new(1, 2, 2), Edge.new(2, 3, 9),
    Edge.new(3, 0, 7), Edge.new(0, 2, 2), Edge.new(1, 3, 6)
]

p kruskal(4, edges)

Let's make friends!

Hello, @sagivo.

I am one of the contributors to similar repository: EKAlgorithms - Objective-C implementations of common algorithms.

Few days ago I discovered this your repository and decided to add a link to it on EKAlgorithms main page. I suggest you doing the same. Let's make friends!

Thanks,

Stanislaw

the logic of min_insertions_for_palidrom is wrong

You can see with the test:

p min_insert 'asd' # ans should be 2
p min_insert 'apga' #ans should be 2

I'm thinking how to correct this.

perm() doesn't return the permutations of a string

This is what I'm seeing in your code:

def perm arr, i=0
  return arr if i == arr.size  
  (i..arr.size-1).each do |j|  
    arr[i], arr[j] = arr[j], arr[i]    
    perm arr, i+1    
    arr[i], arr[j] = arr[j], arr[i]    
  end    
end  
p perm 'ABC'
#=> 0..2

You can use this instead if you want to list all permutations of a string:

class String
  def perms
    self.chars.permutation.map{|x| x.join}
  end
end
"ABC".perms
#=> ["ABC", "ACB", "BAC", "BCA", "CAB", "CBA"]

More questions?

How do you decide on new questions? Can we contribute with questions?
Or you can put up questions in a to-do list in readme and we can contribute.